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

Simple item page

datacite.subject.fos	Engineering and technology
datacite.subject.fos	Natural sciences::Computer and information sciences
dc.contributor.correferente	Riff Rojas, Maria Cristina
dc.contributor.department	Departamento de Informática
dc.contributor.guia	Lalla Ruiz, Eduardo (UT Enschede -The Netherlands)
dc.coverage.spatial	Campus Casa Central Valparaíso
dc.creator	Gómez Sánchez, Mariam
dc.date.accessioned	2025-09-09T14:20:05Z
dc.date.available	2025-09-09T14:20:05Z
dc.date.issued	2023-03-27
dc.description.abstract	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.	en_US
dc.description.abstract	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.	es
dc.description.degree	Doctorado en Ingeniería Informática
dc.description.sponsorship	Dirección de Postgrado y Programas Universidad Técnica Federico Santa María
dc.description.sponsorship	UT Enschede -The Netherlands
dc.description.sponsorship	ANID CONICYT-PFCHA Doctorado Nacional 2017- 21171857
dc.driver	info:eu-repo/semantics/doctoralThesis
dc.format.extent	144 páginas
dc.identifier.doi	10.71959/yrv0-6w62
dc.identifier.uri	https://cris.usm.cl/handle/123456789/4023
dc.identifier.uri	https://doi.org/10.71959/yrv0-6w62
dc.language.iso	en
dc.rights	Attribution-NonCommercial-NoDerivatives 4.0 International	en
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subject	project sheduling
dc.subject	scheduling
dc.subject	multi project
dc.subject	RCMPSP
dc.subject	heuristics
dc.subject	hybrid algorithms
dc.subject.ods	9 Industria, innovación e infraestructura
dc.subject.ods	8 Trabajo decente y crecimiento económico
dc.subject.ods	12 Producción y consumo responsables
dc.subject.ods	17 Alianzas para lograr los objetivos
dc.subject.ods	4 Educación de calidad
dc.title	Resource-constrained multi-project scheduling problem: taxonomy, variants, and approaches
dspace.entity.type	Tesis

Files

Original bundle

Now showing 1 - 1 of 1

Name:: DC_MG_2023.pdf
Size:: 7.47 MB
Format:: Adobe Portable Document Format

Collections

Tesis de Postgrado