The Multi-Mode Resource-Constrained Multi-Project Scheduling Problem

Abstract

Scheduling projects is a difficult and time consuming process, and has far-reaching implications for any organization’s operations. By generalizing various aspects of project scheduling, decision makers are enabled to capture reality and act accordingly. In the context of the MISTA 2013 conference, the first MISTA challenge, organized by the authors, introduced such a general problem model: the Multi-Mode Resource-Constrained Multi-Project Scheduling Problem (MRCMPSP). The present paper reports on the competition and provides a discussion on its results. Furthermore, it provides an analysis of the submitted algorithms, and a study of their common elements. By making all benchmark datasets and results publicly available, further research on the MRCMPSP is stimulated.

1 Introduction

Project scheduling is well known in operations research and management, and has been the subject of intensive research since the late fifties. It has seen many practical applications, ranging from high-level scheduling of software projects and construction projects to fine-grained scheduling of machine operations on a production floor [e.g. scheduling orders in a food production facility (Wauters et al. 2012)]. However, the classical Resource-Constrained Project Scheduling Problem (RCPSP) is not general enough to model all aspects of a real-world problem. Therefore, many extensions to the RCPSP have been presented in the literature, such as min/max time lags, multi-mode, multi-skill, etc.

The MISTA 2013 challenge, organized along with the MISTA 2013 conference, tries to encourage research on a new general project scheduling problem: the Multi-Mode Resource-Constrained Multi-Project Scheduling Problem (MRCMPSP). Multiple projects have to be scheduled simultaneously, while taking into account the availability of local and global resources. The MRCMPSP has a considerable practical relevance, especially in the construction and production sectors. The challenge results in a new benchmark for the MRCMPSP by releasing public instances, a solution validator, an instance generator and state-of-the-art results. The MRCMPSP is attractive for its simple problem description and the lack of complicated constraints to express and evaluate. It therefore requires relatively limited modelling effort, which enables competitors and future researchers to focus on developing powerful algorithms and on the intrinsic scheduling complexity. The MISTA 2013 challenge is, as far as the authors know, the first academic project scheduling competition. A large international audience has been reached (Fig. 1): 21 teams from 14 countries and 3 continents submitted algorithms. Teams were compared on a benchmark PC with a fixed time limit.

Fig. 1

World map of MISTA challenge website visits by country (image courtesy of Google Analytics)

Challenges/competitions are important for stimulating research on particular problems or problem domains. Examples of such challenges are the international timetabling competitions (ITC 2002, ITC 2007, ITC 2011) (McCollum et al. 2007; Post et al. 2013), the nurse rostering competition (Haspeslagh et al. 2012), the ROADEF challenge series (Solnon et al. 2008) and the cross-domain heuristic search challenge (CHeSC 2011) (Burke et al. 2011).

The present paper is structured as follows: Section 2 introduces the MRCPSP and gives a formal definition of the problem, its constraints and objectives. Section 3 describes the competition format, the different phases, test setup and final ranking. Section 4 provides a detailed analysis and discussion of the competition results and submitted algorithms. A conclusion and future perspectives are given in Sect. 5.

2 Problem description

The MRCMPSP is a generalization of the (single-mode) RCPSP in two ways (Fig. 2). First, jobs can be executed in multiple modes (MRCPSP), and second, multiple projects have to be scheduled simultaneously while sharing resources (RCMPSP). These modes allow including time/cost, time/resource and resource/resource trade-offs. The RCPSP was proven to be NP-hard (Blazewicz et al. 1983), consequently the MRCMPSP is also NP-hard. Moreover, the problem of finding a feasible mode assignment subject to more than one non-renewable resource constraint is NP-complete (Kolisch and Drexl 1997).

Fig. 2

RCPSP generalization hierarchy

2.1 Projects and activities

A set $\fancyscript{P}$ of $n$ projects has to be scheduled, under the restriction of several time and resource constraints. The projects are identified by their index $i\in \fancyscript{P}$, with $\fancyscript{P}=\{0,\dots ,n-1\}$. Each project $i\in \fancyscript{P}$ consists of a set of non-preemptive jobs or activities $J_i$. For each activity $j \in \left\{ 1,\ldots ,|J_i| \right\}$ of project $i$, a start time $s_{ij} \ge 0$ has to be determined. The first and last activities of the projects ($j=0$, resp. $j=|J_i|+1$) are dummy activities, which have a zero duration and no resource requirements. Each project $i\in \fancyscript{P}$ has a release date $r_i$, i.e. the earliest time at which the activities of project $i$ can start ($s_{i0} \ge r_i$).

2.2 Local and global resources

A set $L_i=L_i^\rho \cup L_i^\nu$ of resources is associated with each project $i\in \fancyscript{P}$, where the subset $L_i^\rho =\{1,\dots ,|L_i^\rho |\}$ denotes the local renewable resources and $L_i^\nu =\{|L_i^\rho |+1,\dots ,|L_i^\rho |+|L_i^\nu |\}$ the non-renewable resources. Renewable resources have a fixed capacity per time unit, while the non-renewable resources have a fixed capacity over the entire project duration. Each resource $l\in L_i$ has a fixed capacity of $c_{il}$.

Finally, a set $G^\rho$ of global renewable resources is shared among the projects. Similar to the local resources, the availability of the global resources is limited by $c_g^\rho ,\, g\in G^\rho$. There are no global non-renewable resources.

2.3 Execution modes

For each activity $j\in J_i,\, i\in \fancyscript{P}$, one or more execution modes are available. The execution mode in which an activity is performed determines both the time required to complete the activity, as well as the specific resource requirements. Let $M_{ij}=\{1,\dots ,|M_{ij}|\}$ be the set of possible modes in which activity $j\in J_i,\, i\in \fancyscript{P}$, can be performed, and $d_{ijm}$ the processing time of activity $j\in J_i$ in mode $m\in M_{ij}$. The constants $r_{ijml}^\rho ,\, r_{ijml}^\nu$ and $r_{ijmg}^\rho$, respectively, define the consumption of local renewable, non-renewable and global renewable resources when activity $j\in J_i$ is processed in mode $m\in M_{ij}$.

Note that a feasible schedule must always adhere to the following resource constraints:

$$\begin{aligned}&\sum _{j \in J_i}\sum _{m \in M_{ij}}{x_{ijt}\ y_{ijm}\ r_{ijml}^\rho \le c_{il}}&\forall i \in \fancyscript{P}, l\in L_i^\rho , \nonumber \\&t\in [0,T] \end{aligned}$$

(1)

$$\begin{aligned}&\sum _{j \in J_i}\sum _{m \in M_{ij}}{y_{ijm}\ r_{ijml}^\nu \le c_{il}}&\forall i \in \fancyscript{P}, l\in L_i^\nu \end{aligned}$$

(2)

$$\begin{aligned}&\sum _{i \in \fancyscript{P}}\sum _{j \in J_i}\sum _{m \in M_{ij}}{x_{ijt}y_{ijm}\ r_{ijmg}^\rho \le c_{g}}&\forall g\in G^\rho , t\in [0,T] \end{aligned}$$

(3)

$$\begin{aligned}&\sum _{m\in M_{ij}}y_{ijm}=1&\forall i\in \fancyscript{P}, j\in J_i \end{aligned}$$

(4)

$$\begin{aligned}&x_{ijt}\in \{0,1\}&\forall i\in \fancyscript{P}, j\in J_i, \nonumber \\&m\in M_{ij}, t \in [0,T] \end{aligned}$$

(5)

$$\begin{aligned}&y_{ijm}\in \{0,1\}&\forall i\in \fancyscript{P}, j\in J_i, \nonumber \\&m\in M_{ij} \end{aligned}$$

(6)

where binary variables $x_{ijt}$ indicate whether a particular activity $j\in J_i$ is performed at time $t\in [0,T]$, while binary variables $y_{ijm}$ denote whether activity $j\in J_i$ runs in mode $m\in M_{ij}$. $T$ is an upper bound on the time horizon of the scheduling problem.

2.4 Precedence constraints

Certain activities may require the completion of other tasks prior to their own start. In such a case, if activity $j\in J_i$ must precede activity $j'\in J_i$, a precedence relation $j\prec j'$ is defined. Feasible schedules must obey all precedence relations:

$$\begin{aligned}&s_{ij} + \sum _{m\in M_{ij}}y_{ijm}d_{ijm}\le s_{ij'}&if\ j\prec j' \end{aligned}$$

(7)

$pred(j)$ denotes the predecessor set of activity $j$, i.e. $pred(j)=\{j'|j'\prec j\}$.

2.5 Objectives

The objective is to find a feasible schedule while minimizing the total project delay (TPD) (Sect. 2.5.1) and the total makespan (TMS) (Sect. 2.5.2). The two objectives are considered in lexicographical order, where TPD is the primary objective, while TMS is used as a tie breaker.

2.5.1 Total project delay (TPD)

The project delay is defined as the difference between the critical path duration (CPD), a theoretical lower bound on the earliest finish time of the project, and the actual project duration (makespan). More formally, the project delay ($\mathrm PD_i$) for a project $i\in \fancyscript{P}$ is defined as:

$$\begin{aligned} \mathrm{PD}_i=\mathrm{MS}_i-\mathrm{CPD}_i \end{aligned}$$

where $\mathrm{MS}_i$, the makespan of project $i$, is:

$$\begin{aligned} \mathrm{MS}_i = f_i - r_i \quad \mathrm{with}\ f_i = s_{i(|J_i|+1)}. \end{aligned}$$

and $\mathrm{CPD}_i$, the critical path duration¹ of project $i$, is:

$$\begin{aligned} \mathrm{CPD}_i=\mathrm{EF}_{i(|J_i|+1)}, \end{aligned}$$

where $\mathrm{EF}_{ij}$ is the earliest finish time of activity $j\in J_i$, which is recursively defined as:

$$\begin{aligned}&\mathrm{EF}_{i0}=0&\forall i\in \fancyscript{P}\\&\mathrm{EF}_{ij}=\mathop {\mathrm{max}}_{j'\in pred(j)} (EF_{ij'}) +\mathop {\mathrm{min}}_{m} (d_{ijm})&\forall i\in \fancyscript{P}, j>0 \end{aligned}$$

Finally, the TPD is expressed as:

$$\begin{aligned} \mathrm{TPD}=\sum _{i=1}^n{\mathrm{PD}_i} \end{aligned}$$

2.5.2 Total makespan (TMS)

The TMS is the duration of the whole multi-project schedule.

$$\begin{aligned} TMS = \mathop {\mathrm{max}}_{i\in \fancyscript{P}}(f_i) - \mathop {\mathrm{min}}_{i\in \fancyscript{P}}(r_i) \end{aligned}$$

3 Competition

The initial announcement of the MISTA 2013 challenge attracted 21 teams to register for the competition. The majority of participants were affiliated with academic institutions, whereas only three teams were affiliated with industry. The competition’s rules did not stipulate any restrictions on how an algorithm could obtain a solution. The only requirements for the approach were that the code was executable by the organizers, and that it was either completely free or free under academic licencing.

The competition consisted of three phases. The teams were provided with a first dataset to guide the initial development of their algorithms (A instances). Problem size in the first dataset ranged from 2 projects and 10 activities per project to 10 projects and 30 activities per project. Three months after the competition’s announcement, the teams were asked to submit their approach in order to determine the qualifying teams for the next phase. The qualification criteria consisted of executable software that was able to produce feasible solutions for the initial dataset within a time limit of 5 min. 16 out of the 21 registered teams qualified for the second phase.

After the announcement of the qualification results, a second set, containing larger instances, was published (B instances). The problem size varied between instances with 10 projects and 10 activities per project and instances with 20 projects and 30 activities per project. Again, the participants had 3 months to fine-tune their approaches, given the new dataset and the best obtained solutions from the qualifications phase. At the end of this second phase, 9 out of 16 teams submitted an algorithm for the final phase.

In the last phase, the performance of the final submissions was evaluated. The final ranking was determined by running each participant’s algorithm ten times on all instances from the second dataset and an additional hidden dataset (X instances), with instances of similar size as the B instances. These experiments were executed by the organizers on a recent desktop pc², with a time limit³ of 5 min per instance. For each instance, the algorithms were ranked based on the average of all runs. Finally, the ranks were averaged over all instances per team. Table 1 shows the final results.

Table 1 Final ranking

Additional details on the competition rules, the datasets and general information regarding the competition can be found at the competition web page (Wauters et al. 2013).

3.1 Instance generation

Instances of this new MRCMPSP have been generated by combining multiple MRCPSP instances from PSPLIB. Release dates and global resources had to be added. The release dates are generated using a poisson process, i.e. the project inter arrival times are exponentially distributed with $\lambda =0.2$. The release date of the first project is always $r_0=0$. One of the two renewable resources is a global resource with a 2/3 probability. The capacity of the global renewable resources has been set to a value between 50 and 100% of the local renewable resource capacity. To guarantee feasibility the capacity should be at least 10, i.e. in the PSPLib files, there are jobs with a resource consumption of 10. The following formula is applied:

$$\begin{aligned} c_g^\rho = \mathrm{max}\left( CAP_\mathrm{max} \frac{5+rand(6)}{10},10\right) , \end{aligned}$$

where $CAP_\mathrm{max}$ is the maximum capacity of the corresponding local renewable resources and $rand(6)$ is a uniform random number between 0 (inclusive) and 6 (exclusive). The instance generator is available for download on the competition web page.

4 Discussion

4.1 Detailed results

Table 2 gives an overview of the detailed results per team and per instance, averaged over 10 runs. This produced the final ranking (by mean rank over all instances) shown in Table 3. It is clear that the competition’s final winner, team 11, produced the best average results over all instances, except for instances B-2 and X-1. The second and third ranking positions were more contested, with team 1, team 8 and team 20 alternatingly producing second and third best results (Table 4).

Figure 3 shows box plots of each team’s results per instance, giving an indication of the spread of the results. It is clear that teams 13, 14, 15, 17 and 21 in general have a larger spread of results per instance, indicating their methods are either more susceptible to random events or possibly not yet converged after the time limit is reached. Team 1, 8, 11 and 20 generally have a low spread of the results; in particular team 20 has a spread of 0 for all instances because the submission always produces the same result.

Fig. 3

Summarizing boxplots of participants’ results per instance

The final ranking method, by mean rank over all instances, was decided as the scoring system at the onset of the competition. Any scoring system is biased in one way or another, e.g. the ranking transformation discards information on the relative performance among submissions on each instance. In order to investigate how the scoring system influenced the final results, different scoring systems were tested. In addition to ranking by mean rank, the following systems were compared:

• Ranking by mean: ranks according to the mean of the averaged results over all instances. This system is biased by the difference in magnitude of the objective function value between instances: larger instances will typically have a higher magnitude of objective function value, and thus will contribute more to the mean. Scoring well on large instances is thus important. However, the relative performance among submissions per instance is not lost.

• Ranking by geometric mean: ranks according to the geometric mean of the averaged results over all instances. This system is less biased by the difference in magnitude of the instance objective function value, and also maintains information on relative performance between submissions per instance.

• Ranking by total F1-score: this scoring system is adopted from Formula 1 racing point system (before 2010), and was used by the CHeSC 2011 competition (Burke et al. 2011). For each instance, the submissions are attributed points from 10 to 0. The highest average result is attributed 10 points, the second highest 8, the third 6, and finally 5, 4, 3, 2 and 1 to the remaining results in that order. The total number of points over all instances is then used to rank the submissions. Since the attribution of points is essentially a ranking transformation, relative performance between submissions per instance is lost. Furthermore, the method is biased towards the best results per instance.

• Ranking by mean best rank: this method differs from the competition ranking method by computing the ranks per instance based on the best result produced by each submission, rather than their averaged result. Therefore, this method considers the ‘best’ results for any submission, but may be biased by ‘lucky results’, and also loses information on relative performance between teams per instance. A summary of the best results found for all instances and teams can be found in Table 5.

• Ranking by mean rank over all runs: this method attributes a rank per instance to each run of all teams (i.e. a rank between 1 and 90 as there were 9 fully feasible teams and 10 runs with different random seed per team). Next, a mean rank is computed per team by computing the average rank over all instances and all runs of this team.

These 6 different scoring systems produce the final ranks⁴ shown in Table 4. It is clear that the order of the best four submissions (Teams 1, 8, 11, and 20) is stable to the considered scoring mechanisms. However, there are some changes between positions 5 through 8, differentiating the teams ranking 5th according to the mean rank. It becomes apparent that team 17 produced better results than the other two teams at rank 5.

Table 2 Average results per instance for submissions to the MISTA competition

Table 3 Ranking per instance based on the averaged result per submission of the final phase

Table 4 Ranking results of final submissions by different ranking methods

Table 5 Best results per instance and per team for submissions to the MISTA competition

4.2 Properties of submitted algorithms

A variety of methods have been submitted to the MISTA 2013 challenge.

Toffolo et al. (2013) (Team 1) use a decomposition-based matheuristic. The approach considers resolution of several integer programming (IP) models, in three different stages. A feasible set of execution modes for the jobs is obtained, in the first stage. The second stage decomposes the problem into time windows. Each time window is solved with an IP model, considering the execution modes obtained from the first stage. The result of the second stage is a feasible solution, which is improved in the final stage by a hybrid local search based on forward-backward improvement (Lova et al. 2009; Valls et al. 2005) and an IP model to perform controlled changes to the solution.

Geiger (2013) (Team 8) proposes an iterated variable neighbourhood search with four different neighbourhoods: exchange, inversion, single mode change and double mode change. Random initial solutions are generated with an additional mode repair procedure. A serial schedule generation scheme (SSGS) constructs schedules with a given activity list and mode assignment.

Asta et al. (2013) (Team 11) apply a combination of Monte-Carlo Tree Search (MCTS) and hyper-heuristics. MCTS first partitions the projects from which their ordering is then determined. An initial solution is constructed by randomly scheduling the activities in each project, while only taking into account the precedence constraints. A multi-threaded hyper-heuristic with threshold acceptance is used to control 13 neighbourhood moves, which change mode assignments, activity ordering, and project ordering. Furthermore, hill climbing heuristics are used within the hyper-heuristic to intensify the search, similar to the local search part of memetic algorithms.

Borba et al. (2013) (Team 13) propose a stochastic local search procedure with two neighbourhoods (single mode change, swap). Dynamic programming determines the initial mode selection.

Bouly et al. (2013) (Team 14) make use of an evolutionary algorithm and local search. A triplet encoding including the sequence of jobs and the chosen modes combined with a SSGS and a repair procedure to produce feasible schedules. The local search applies three different neighbourhoods and is used as a post-processing procedure for the evolutionary algorithm.

Alonso-Pecina et al. (2013) (Team 15) propose a three-phase approach. First, feasible solutions are constructed for each project separately, which are afterwards combined into an initial feasible solution for the complete problem. The second phase improves the solution with a simulated annealing metaheuristic. It applies two neighbourhoods that change mode assignments and activity ordering. The solution is further improved in the third phase with a tabu search algorithm exploring the two previous neighbourhoods, and one additional neighbourhood that changes two mode assignments simultaneously.

López-Ibáñez et al. (2013) (Team 17) used an automatic design method to develop an algorithm for the MRCMPSP. The design method uses ‘irace’ to find the best combination of algorithm parameters out of a set. The proposed algorithm is an iterated local search with two neighbourhoods (single mode change, swap). Several initial solutions are generated using different construction heuristics.

Artigues and Hebrard (2013) (Team 20) introduce a hybrid approach, which focuses mainly on mode selection. It includes a MIP relaxation model for producing an initial mode assignment. The improvement method alternates between mode selection, conducted with large neighbourhood search, and fixed-mode optimization based on a standard Constraint Programming model.

Schnell extends SCIP (Schnell 2013) (Team 21) with a multi-mode cumulative constraint, enabling generation of optimal solutions for 2-project instances in less than 35 sec. For the larger instances, a steepest descent local search heuristic with four neighbourhoods is applied. An initial solution is constructed by solving all projects separately for minimal makespan, and sequencing the projects for a minimal total project delay. Sorting all activities in this sequence by increasing starting times results in the initial activity list to which a SSGS is applied. Two neighbourhoods relax up to two projects, enabling generation of a different solution. One randomly selects the projects, while the other selects projects based on the lower bound of the relaxed solution. A third neighbourhood relaxes some of the activities that are scheduled at the end of the current solution. A fourth relaxes the mode assignments in an effort to minimize the complete renewable resource energy. The resulting partially relaxed problem is solved with SCIP.

Table 6 shows the presence of different components in the nine feasible submissions. The following components and properties are shown:

• Search strategy: The reported search strategy: iterated local search (ILS), variable neighbourhood search (VNS), hyper-heuristic (HH), first improving local search (FILS), evolutionary algorithm (EA), simulated annealing (SA), tabu search (TS), large neighbourhood search (LNS) and steepest descent (SD).

• NN: number of neighbourhoods.

• Population: whether or not the approach is population based.

• SGS: if and which schedule generation scheme is used.

• FB: whether or not the forward-backward or double justification procedure is used (Lova et al. 2009; Valls et al. 2005).

• Solver: if and which (general purpose) solver is used.

• Parallel: parallel execution.

All teams submitted a heuristic procedure in which some included exact components. Some model elements are common to most approaches, namely an activity list and a mode assignment representation combined with a SSGS. The single mode change neighbourhood, where the mode assignment of a single job is changed, is part of most teams’ approaches. It is noteworthy that every team has a different approach to generate feasible initial solution(s), and especially to find a feasible mode assignment, e.g. random, monte-carlo tree search, multi-dimensional knapsack,$\ldots$ The teams do not all explicitly apply parallel execution. Some teams use a CP or MIP for solving subproblems to optimality or for conducting a large neighbourhood search.

Table 6 Properties of the nine algorithms in the competition final

5 Conclusion

This paper introduced the MRCMPSP, subject of the MISTA 2013 challenge. The submitted approaches and the results have been thoroughly analysed and discussed. The problem shows to be very challenging, and a large variety of algorithms and results can be observed. The challenge serves as a new benchmark platform for the MRCMPSP and stimulates research for this and related problems. Many instances and results are available for comparison and facilitate future research on the problem.

Future research can take advantage of the collected knowledge, for example by (1) exploring synergy by combining the key components of the feasible algorithms, (2) applying the collected set of algorithms in a portfolio approach.

Appendix 1: File formats

1.1 Instance input file format

All problem inputs are integer valued, and comply with the following file format. Each problem instance is defined by $n+1$ files, one global file and $n$ project files.

1.2 Global file

The global file contains the number of projects, the release dates, the path to the project files, and the global resource capacities. Values are space separated and should respect the following order:

1.3 Project files

Each project is defined in a separate file. The relative path to this file is given in the global file (e.g. j20.mm/j2010_1.mm). A project file contains the number of activities (including the dummy activities), the precedence relations between the activities, the execution modes, and the local resource capacities. The individual projects are represented in the PSPLIB⁵ MRCPSP file format.

Important note: In order to preserve compatibility with PSPLIB, the global resources always overwrite the local resources and their capacities. For example, consider the following global resource capacities (16,$-$1,$-$1,$-$1) and local resource capacities (RR1 = 14, RR2 = 18, NR1 = 60, NR2 = 68), then there exists one global renewable resource with capacity 16, one local renewable resource with capacity 18 and two non-renewable resources with capacities 60 and 68. The local renewable resource with capacity 14 can be ignored.

1.4 Solution output format

A solution for the MRCMPSP is defined as follows:

For each activity $j$ of project $i$,

• the selected mode $m_{ij}$,

• and the start time $s_{ij}$,

must be given.

An example is given in Table 7.

Table 7 Solution output format example

1.5 Solution validator

The validator checks feasibility of a solution, and computes the total objective cost. It is available for download at the MISTA challenge website (Wauters et al. 2013). The validator requires Java. It can be run as follows:

The validator was used for evaluating the quality of solutions produced by the algorithms submitted to the MISTA 2013 challenge. Note that the validator does not report validity of the instances.

1.6 Example

An example MRCMPSP instance and a corresponding feasible solution can be found on the challenge website. The instance has 2 projects, 10 jobs per project and 1 global renewable resource with capacity 12. The global file corresponding to this example is