Thesis:

Resource-constrained multi-project scheduling problem: taxonomy, variants, and approaches

Project Management is becoming increasingly crucial in competitive environments such as manufacturing and the service industries. The resource-constrained multi-project scheduling problem (RCMPSP) consists of assigning start times to jobs corresponding to two or more projects that must be executed simultaneously while respecting the precedence between jobs and limited resources. The existing rise in the study of the RCMPSP resulted in numerous works on the topic while proposing different problem features. This thesis presented a study of the RCMPSP and its variants, the base problem is initially described, and the solution methods and benchmarks used to solve RCMPSPs are classified and analyzed. The implications of the RCMPS with practice and its connection are also discussed. In addition, this research analyzed different variants of the problem based on aspects related to jobs, projects, relationships, resources, and time management, and based on the problem variants considered in the reviewed works, a taxonomy allowing (i) the identification and positioning of each RCMPSP variant and (ii) the analysis of the current state-of-the-art of the problem was proposed. Subsequently, it delved into the research of one of the most studied variants in the literature, RCMPSP with local resources (RCMPSP-L), describing the problem in detail and exposing its corresponding mathematical formulation. To solve the RCMPSP-L, a hybrid algorithm that integrates ant colony optimization with a hill-climbing first-improvement algorithm was proposed, and the experimentation process was carried out using a set of instances taken from the MPSPLib. The proposed algorithm presented low variability values, the construction phase provided good-quality solutions, and the local search constantly improved the constructive algorithm, with the results compared with other well-known approaches in the literature, evidencing that for different existing metrics, the proposed approach presents competitive results. Later, new variants of the problem that consider resource mixed accessibility, total resource allocation, delay costs, and resource costs were presented: RCMPSP-MT-W and RCMPSP-MT-W+RC, respectively, both variants described and mathematically formulated. A hybrid algorithm that integrates priority rules, simulated annealing, and tabu search as part of an iterated local search was proposed to solve the variants, where simple perturbation and joint perturbation were proposed as different perturbation intensities as part of the ILS. To validate the model and the algorithm, 36 instances based on the MPSPLib library were modified, and the results show that the application of joint perturbation yields better or equal results than simple perturbation, making greater use of resources with global accessibility, and although it may not be the only factor, the global accessibility of resources may imply greater freedom of allocation, allowing better results to be obtained.

La gestión de proyectos cobra cada vez mayor importancia en entornos competitivos como la industria manufacturera y los servicios. El problema de programación multiproyecto con recursos limitados (RCMPSP) consiste en asignar tiempos de inicio a trabajos correspondientes a dos o más proyectos que deben ejecutarse simultáneamente, respetando la precedencia entre trabajos y recursos limitados. El auge del estudio del RCMPSP ha dado lugar a numerosos trabajos sobre el tema, proponiendo diferentes características del problema. Esta tesis presentó un estudio del RCMPSP y sus variantes, describiendo inicialmente el problema base y clasificando y analizando los métodos de solución y los puntos de referencia utilizados para resolverlos. También se discuten las implicaciones del RCMPS en la práctica y su conexión. Además, esta investigación analizó diferentes variantes del problema en función de aspectos relacionados con trabajos, proyectos, relaciones, recursos y gestión del tiempo. A partir de las variantes del problema consideradas en los trabajos revisados, se propuso una taxonomía que permite (i) la identificación y el posicionamiento de cada variante del RCMPSP y (ii) el análisis del estado actual del problema. Posteriormente, se profundizó en la investigación de una de las variantes más estudiadas en la literatura, RCMPSP con recursos locales (RCMPSP-L), describiendo el problema en detalle y exponiendo su correspondiente formulación matemática. Para resolver el RCMPSP-L, se propuso un algoritmo híbrido que integra la optimización de colonias de hormigas con un algoritmo de primera mejora de ascenso de colinas, y el proceso de experimentación se llevó a cabo utilizando un conjunto de instancias tomadas de MPSPLib. El algoritmo propuesto presentó bajos valores de variabilidad, la fase de construcción proporcionó soluciones de buena calidad y la búsqueda local mejoró constantemente el algoritmo constructivo. Los resultados se compararon con otros enfoques bien conocidos en la literatura, evidenciando que para diferentes métricas existentes, el enfoque propuesto presenta resultados competitivos. Posteriormente, se presentaron nuevas variantes del problema que consideran la accesibilidad mixta de recursos, la asignación total de recursos, los costos de retraso y los costos de recursos: RCMPSP-MT-W y RCMPSP-MT-W+RC, respectivamente, ambas variantes descritas y formuladas matemáticamente. Se propuso un algoritmo híbrido que integra reglas de prioridad, recocido simulado y búsqueda tabú como parte de una búsqueda local iterada para resolver las variantes. La perturbación simple y la perturbación conjunta se propusieron como diferentes intensidades de perturbación como parte del ILS. Para validar el modelo y el algoritmo, se modificaron 36 instancias basadas en la biblioteca MPSPLib. Los resultados muestran que la aplicación de la perturbación conjunta produce resultados mejores o iguales que la perturbación simple, lo que permite un mayor uso de recursos con accesibilidad global. Si bien puede no ser el único factor, la accesibilidad global de los recursos puede implicar una mayor libertad de asignación, lo que permite obtener mejores resultados.