The multi-mode resource-constrained project scheduling problem
The resource-constrained project scheduling problem with multiple modes (MRCPSP) is an extension of the well-known single-mode RCPSP and involves the selection of a time/resource combination for each activity such that the total project makespan is minimized. Various research results have been presented at the OR&S group which can be summarized along the following lines.
Benchmark your solutions!
Researchers who wish to compare their solution procedures with the state-of-the-art solution procedures from literature can rely on the benchmark solutions and data instances published in the European Journal of Operational Research entitled as "An Experimental Investigation of Meta-heuristics for the Multi-mode Resource-Constrained Project Scheduling on new Dataset Instances". In this paper, an overview is presented of the existing metaheuristic solution procedures to solve the multi-mode resource-constrained-project scheduling problem, in which multiple execution modes are available for each of the activities of the project. A fair comparison is made between the different metaheuristic algorithms on the existing benchmark datasets and on a newly generated dataset. Computational results are provided and recommendations for future research are formulated. The paper can be downloaded from the website of the publisher.
Project instances with multiple modes and resource constraints can be downloaded from the PSPLIB. This library contains the project instances J10, J12, J14, J16, J18, J20 and J30 (with and without the presence of the nonrenewable resources) and the well-known Boctor instances (Boctor50 and Boctor100) and can be downloaded here.
However, in the benchmark paper mentioned above, it has been shown that the PSPLIB dataset and the dataset of Boctor (Boctor, 1994) show some shortcomings given the recent evolution in the development of meta-heuristic solution procedures. It is for this reason that the new dataset for the multi-mode scheduling problem is proposed in the paper "An Experimental Investigation of Meta-heuristics for the Multi-mode Resource-Constrained Project Scheduling on new Dataset instances". The following four conditions were taken into account while generating the dataset:
- The generated projects are diverse with respect to the project (order strength) and resource characteristics (resource factor and resource strength).
- Every project has at least 1 feasible solution.
- No modes can be excluded.
- Both renewable and nonrenewable resources are taken into account.
The MMLIB dataset contains three subsets MMLIB50, MMLIB100 and MMLIB+ and can be downloaded from the project database webpage by clicking on the download picture below.
The best known solutions for each of the instances of the three sets can be downloaded here (15/07/2011). It's worth to visit the website of a colleague researcher here containing comparative results
The increasing interest in operations research for metaheuristics during the recent years has resulted in the development of several metaheuristic solution procedures for the MRCPSP. A wide variety of metaheuristic strategies, solution representations and schedule generation schemes were used to develop the most efficient algorithms. An extensive overview of all the metaheuristics currently available in the literature (15/07/2011) can be found in our benchmark paper.
In the OR&S research department, several heuristic optimization algorithms have been developed to solve the MRCPSP, such as a genetic algorithm with a fast and efficient local search procedure and the ability of coping with activity preemption, an artificial immune system approach, a combined approach of a scheduling algorithm with a SAT solver and a scatter search procedure that dynamically selects the local search methods based on resource specific information.
The results obtained from tests with the genetic algorithm on the PSPLIB data instances described above can be downloaded. For each instance, the critical path based lower bound (CPBLB), as well as the results for the case with and without preemption are shown (columns 'MRCPSP' and 'PMRCPSP' respectively). We also indicate the average deviation from the critical path based lower bound (CPBLB) in the columns '% dev. M' and '% dev. PM'. the column with label 'Av.Impr.' displays the average makespan improvement for the PMRCPSP relative to the MRCPSP. The columns with labels 'Better', 'Equal' and 'Worse' show the number of preempted solutions with a lower, equal or higher project makespan than the solutions found for the MRCPSP.
- Download Genetic Algorithm Results
- Buy the benchmark paper from EJOR for more results.
The OR&S references to our papers on the MMRCPSP can be summarized along the following lines:
- Van Peteghem, V. and Vanhoucke, M., 2009, “An Artificial Immune System for the multi-mode resource-constrained project scheduling problem”, Lecture Notes in Computer Science, 5482, 85-96.
- Van Peteghem, V. and Vanhoucke, M., 2010, “A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem”, European Journal of Operational Research, 201, 409 -418.
- Van Peteghem, V. and Vanhoucke, M., 2010, "An Experimental Investigation of Meta-heuristics for the Multi-mode Resource-Constrained Project Scheduling on new Dataset instances", European Journal of Operational Research, 235, 62-72.
- Van Peteghem, V. and Vanhoucke, M., 2010, “Using Resource Scarceness Characteristics to Solve the Multi-Mode Resource-Constrained Project Scheduling Problem”, Journal of Heuristics, 17, 705-728
- Coelho, J. and Vanhoucke, M., 2011, “Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers”, European Journal of Operational Research.
- Read the full list of publications here.