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. Furthermore, 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. 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 our constructive algorithm. The results provided were compared with other well-known in the literature, evidencing that for different existing metrics, our 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 mentioned variants are 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. 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. 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. In addition, we identify that 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.