The multi-mode resource constrained project scheduling problem (MRCPSP) is an important planning problem with applications in project management, production, and others. There is a number of activities to be scheduled, each of which comes with a set of execution modes of different duration and resource consumptions. In essence, the problem is twofold: select, for each activitiy, an execution mode, and subsequently schedule all activities such that the total duration of the project, i.e., the finish time of the last activitiy, is minimized. Obviously, resource constraints have to be respected, and therefore, and depending on those constraints, not all choices of execution modes are feasible. In fact, and in the general case, even finding a feasible mode assignment is a hard (sub-)problem.
MISTA 2013 Challenge
In 2013, we have contributed to the MISTA 2013 Challenge, an implementation competition on the Resource-Constrained Multi-Mode Multi-Project Scheduling Problem. The problem definition is rather close to the MRCPSP, as several projects have to be scheduled at once, and thus presents a generalization of the classical MRCPSP. A detailed description of the problem, incl. the (new) benchmark instances which have been created for this event, is available on the competition website.
Our algorithm combines ideas from Iterated Local Search with Variable Neighborhood Search into a running optimization system. Particular emphasis has been put on a efficient parallel/multi-threaded implementation. A detailed description of the approach, incl. the source-code of our implementation, have been published.
In this international competition, our approach ranked first in the qualification phase held from January 2013–April 2013) and second in the finals/ overall (held from April 2013–June 2013).
Applications to other benchmark instances (MMLIB50, MMLIB100, MMLIB+)
Recently, we did run the computer program of the MISTA 2013 Challenge on the MMLIB50, MMLIB100, and MMLIB+ benchmark instances of Van Peteghem and Vanhoucke (see http://www.projectmanagement.UGent.be). To our surprise and satisfaction, numerous best known results have been found, which can be downloaded from here.
The success of our work on the MMLIB-data sets gave rise for a joint project with Christian Stürck and Patrick Gerhards, both of who also contributed to the MRCPSP in the past. In a joint effort, numerous improved solutions have been computed for the MMLIB-instances, see http://www.mmlib.eu/. In fact, most of the best-known-solutions are, at the moment, based on our work.
Related key publications
Martin Josef Geiger (2017):
A multi-threaded local search algorithm and computer implementation for the multi-mode, resource-constrained multi-project scheduling problem.
European Journal of Operational Research, Volume 256, Issue 3, February 2017, Pages 729–741, ISSN 0377-2217.
[doi:10.1016/j.ejor.2016.07.024]
Martin Josef Geiger:
MISTA 2013 Challenge – sourcecode of my contribution.
[doi:10.17632/cw95t56hjv.1]
Letzte Änderung: 6. Dezember 2017