Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

The multi-mode resource-constrained project scheduling problem (MRCPSP) is an extension of the well-studied resource-constrained project scheduling problem (RCPSP), which comprises a set of non-preemptive activities, a set of resources with a constant capacity over time, and precedence relations between pairs of activities. For both problems, a start-time schedule for the activities is sought that respects the precedence relations, does not overload a resource at any point in time, while minimising the project duration (makespan). The differences between these problems are that activities can be executed in different modes and resources can be non-renewable in MRCPSP, while activities have a single mode and all resources are renewable in RCPSP. Different modes for an activity model time-resource and resource-resource trade-offs. These scheduling problems are NP-hard and have numerous applications, such as production planning, manufacturing, chemical processing, and project management [16].

An excellent overview of different and state of the art methods can be found in [5]. Most exact solution methods for solving MRCPSP are based on integer programming using branch-and-bound or branch-and-cut. The best methods were published in [1, 16]. Zhu et al. [16] present an exact branch-and-cut algorithm based on integer linear programming (ILP). They apply several pre-processing steps in order to reduce the number of variables in their models, pre-compute cuts from resource conflicts and precedence relations. In addition, a dedicated branching rule is developed for taking the different modes into account. To the best of our knowledge, it is the best exact method so far. Coelho et al. [1] propose a solution approach that decomposes the problem into two sub-problems. The first sub-problem consists of the assignment of the modes of execution solved by a Boolean Satisfiability (SAT) solver. The second sub-problem considers the fixed modes from the first sub-problem and solves the remaining problem using a local search method.

Closely related problems to MRCPSP are RCPSP and MRCPSP with generalised precedence relations (MRCPSP/max). In both cases, the best exact solution methods are based on constraint programming (CP) technologies incorporating nogood learning. For RCPSP, [12, 13] present a branch-and-bound approach that is based on lazy clause generation (LCG) [2, 7]. LCG is a CP solver that incorporates, amongst others, conflict analysis, conflict-driven search, and unit propagation on conjunction of clauses from SAT solvers. Exact solution approaches based on LCG are the best exact solution methods for various scheduling and packing problems [4, 10, 11, 13–15].

For MRCPSP/max, [8] recently proposed a branch-and-bound approach formulated as a constraint integer program and implemented in the SCIP framework, which also has nogood learning facilities. In order to solve the problem, they implemented two new global constraints for generalised precedence relations and renewable resources, taking the multiple modes of an activity into account. The latter one is an extension of the global constraint cumulative. Their method is the best exact solution method for MRCPSP/max.

Surprisingly, no CP technology with nogood learning has been applied to MRCPSP. This paper addresses this gap and not only shows such a method outperforms the state of the art in [16], but also discusses different models and search strategies. In addition, we close all remaining open instances from the well-established benchmark library PSPLib.

2 MRCPSP Model

MRCPSP consists of a set of non-preemptive activities \(V= \{1, 2, \dots , n\}\), a set of precedence relations \(E\subseteq V\times V\), and a set of resources \(\mathcal {R}\). The set of resources is partitioned into the set of renewable resources \(\mathcal {R}^{R}\) and the set of non-renewable resources \(\mathcal {R}^{N}\). A resource \(k\in \mathcal {R}\) has a discrete resource capacity \(R_{k}\). An activity i has a fixed set of modes \(\mathcal {M}_{i}\). For each mode \(m\in \mathcal {M}_{i}\), the activity has a discrete non-negative duration (processing time) \(p_{i}^{m}\) and a discrete non-negative resource requirement \(r_{ik}^{m}\) for each resource \(k\in \mathcal {R}\) over the planning horizon. The discrete non-negative start time \(S_{i}\) and the mode of execution \(M_{i}\) must be determined by the solution approach. The planning horizon starts at time period 0.

Definition 1

(Solution of MRCPSP). A solution of MRCPSP is an assignment of start times \(S_{i}\) and modes of executions \(M_{i}\) for each activity i such that the following constraints hold

$$\begin{aligned} \nonumber \forall i\in V&: 0 \le S_{i} \quad \wedge \quad M_{i} \in \mathcal {M}_{i}\\ \forall (i, j) \in E&: S_{i} + p_{i}^{M_{i}} \le S_{j}\end{aligned}$$
(1)
$$\begin{aligned} \forall k\in \mathcal {R}^{R}, \forall \tau \ge 0&: \sum \nolimits _{i \in V: S_{i} \le \tau < S_{i} + p_{i}^{M_{i}}} r_{ik}^{M_{i}} \le R_{k}\end{aligned}$$
(2)
$$\begin{aligned} \forall k\in \mathcal {R}^{N}&: \sum \nolimits _{i \in V} r_{ik}^{M_{i}} \le R_{k} \end{aligned}$$
(3)

where constraint (1) ensures the satisfaction of the precedence constraints and constraints (2–3) respectively guarantee a non-overload of renewable and non-renewable resources. An optimal solution additionally minimises the project duration (makespan), i.e., \(\min \max _{i \in V} (S_{i} + p_{i}^{M_{i}})\).

2.1 Solver Independent Model

For the sake of readability, we present a “simplified” model and the “user-defined” searches using the solver-independent modelling language MiniZinc [6].

An MRCPSP instance is represented by the following parameters, whose meaning is given in the comment next to them where the arrays mact and mode respectively map a mode to its activity and an activity to its set of modes.

figure a

Variables. Three variables are created for each activity i reflecting its start time start[i], its duration adur[i], and its resource requirements arreq[k,i] for each resource k. The duration and resource requirements are determined by the mode of execution. A Boolean variable mrun[m] models whether the mode m is executed in the final schedule. Lastly, the objective variable is defined as makespan.

figure b

The variables in start and the variable makespan have an initial domain 0..UB where UB is the initial upper bound on the objective. Unless otherwise stated, UB is initialised by sum(i in Act)(max([mdur[m] | m in mode[i]]));.

Activities and mode constraints. The duration and resource requirements of an activity are linked via a set of linear constraints, encapsulated in the first two constraints below. The last constraint ensures that exactly one mode is executed for each activity.

figure c

Alternatively, we can create an auxiliary variable mi and replace the first two constraints above by element constraints (elem) for modelling adur and arreq.

figure d

Precedence constraints. The precedence constraints are modelled as usual using the start time and duration variables.

figure e

Renewable resource constraints. There are two options for modelling renewable resources using the global constraint cumulative. The first option (ract) creates one activity in the cumulative constraint for each activity, in which the durations and resource requirements are variables.

figure f

The second option (rmode) creates one activity for each mode, resulting in a greater number of activities generated in the cumulative constraint, but having only the resource requirements as variables. These variables can be created as a variable view on the Boolean variables in mrun.

figure g

On the one hand, a cumulative propagator can exploit the knowledge of the duration-resource-requirement pairing in rmode. On the other hand, it loses the knowledge that exactly one mode has to be executed. Note that [8] extended the cumulative propagator for taking multi-modes for activities into account. However, the considered solvers in this paper do not provide this extension.

Non-renewable resource constraints. Non-renewable resources are simply modelled by linear constraints. As for the renewable resource constraints, there are again two options. The first option (nact) models it via the activities using the variables for the resource requirements,

figure h

whereas the second option (nmode) models via the modes using the Boolean variables mrun.

figure i

Pairwise non-overlapping constraints. Pairwise non-overlapping constraints for activities might speed up the solution process and be advantageous for learning solvers. These are redundant constraints with respect to the renewable resource constraints. Two activities i and j cannot be run concurrently and are disjunct iff \(\forall m_i \in \mathcal {M}_{i}, \forall m_j \in \mathcal {M}_{j}, \exists k \in \mathcal {R}^{R}: r_{ik}^{m_i} + r_{jk}^{m_j} > R_{k}\). The next constraint (disj) ensures that one of such activities is run before the other one.

figure j

Other pairs of activities that might be a disjunct in some modes are modelled by following half-reified constraints.

figure k

The predicate post_noc_mode (nocm) models non-overlapping constraints for each mode pair, while post_noc_rres (nocr) only for each renewable resource.

Objective constraints. The objective variable is constrained by the latest end time of an activity as follows.

figure l

Search strategies. We investigated different search strategies including the default ones of the considered solvers.

figure m

The search modeThenStart splits the search into two stages. First, it assigns the mode to each activity and then solves the remaining RCPSP by searching on the start times. The next three searches arreqThenMode, arreqThenStart and arreqThenModeThenStart assign the smallest resource requirements of activities for non-renewable resources first, before continuing the search on the modes and/or the start times. The last two searches assign the shortest duration of each activity before assigning the mode and/or the start times. Note that if a search does not assign all variables, then the solver uses its default search to assign the remaining variables.

3 Experiments

We conducted experiments on the well-studied MRCPSP benchmark set from the PSPLib available at www.om-db.wi.tum.de/psplib/. The benchmark set contains different test sets, which differ in their characteristics. Except for the test set j30, all instances are closed. In the remainder of this paper, we concentrate on j20 and j30. Instances from these test sets are composed of 20 and 30 activities having between one and three modes, two renewable resources, two non-renewable resources, and a number of precedence relations.

All experiments were run on machines operating CentOS 6.5 with AMD 6-Core Opteron 4334 clocking 3.1 GHz, and 64 GB memory. A runtime limit of 10 min was imposed unless otherwise stated. For compiling the MiniZinc model into the solver-specific FlatZinc format, we used MiniZinc 2.0.13 downloaded from www.minizinc.org. The following CP solvers were investigated Gecode 4.4.1 (gecode), Opturion CPX 1.0.2 (ocpx), G12/LazyFD (lazyfd), and Chuffed rev. 885 (chuffed) where the last three are LCG solvers.

3.1 Comparison of Models

Section 2.1 presents two ways of modelling renewable resource, non-renewable resource and pairwise non-overlapping constraints. Since the behaviour of non-learning and learning solvers can be significantly different, we present the results for gecode and chuffed as representatives for each kind.

Table 1 shows the results for both solvers using the search modeThenStart in two parts. Part I shows the different combinations for the renewable (rres) and non-renewable (nres) resource constraints. For both solvers, the best combination in terms of number of optimal solutions (#opt), mean runtime in seconds (m.rt.), and mean number of explored nodes (m.#nodes) is to use the activity representation (act) for both constraints. Interestingly, chuffed performance drastically decays when using the mode representation (nmode) for non-renewable resource constraints, while gecode only worsens slightly. This could indicate that chuffed misses some propagation. Note that we also run the experiments with both activity and mode representations, but the runtime increased substantially while the number of explored nodes did not change significantly.

Table 1. Comparison of different models on 554 instances from test set j20.
Full size table
Table 2. Comparison of different search strategies on test set j30.
Full size table

Part II in Table 1 lists the results when the redundant non-overlapping constraints are used. In each setting, it is advantageous to use the redundant constraints. The best option is to use constraints for non-overlapping (disj, nocr) and activity representations (ract, nact), which gives the lowest mean runtimes for both solvers and the highest number of optimally solved instances in the case for gecode. Part III shows that using element constraints (elem) for the activity and mode constraints performs similar to the best option in Part II. For the remainder, we consider the model in Part III, which performs at best on the test set j30.

3.2 Comparison of Search Strategies

Table 2 presents the outcome of the different searches when the best model (see previous sub-section) is used. Searches starting with the assignment of duration variables (durThenStart and durThenModeThenStart) are the quickest and optimally solve the greatest number of instances. The next best search is modeThenStart, while the remaining searches, all of which assign the resource requirement variables for non-renewable resources first, perform worst. Interestingly, searching over mode variables is slightly worse than leaving them out. For instance, the mean runtime of durThenStart is slightly less than that of durThenModeThenStart. Similar results for the search strategies were obtained on the models presented in Table 1 in preliminary experiments. For chuffed, we also ran each search in combination with chuffed activity based search, in which chuffed alternates between the two searches at each restart. The results are similar, but with the alternating searches more instances were solved to optimality and the mean runtime and number of nodes were lower.

3.3 Comparison of Solvers

Table 3 shows the results of the different solvers for the best model in combination with the solver’s default search and the best search. Clearly, the default searches, which are conflict driven, of the nogood learning solvers drastically outperform the user-defined searches. Note that chuffed default search alternates between a conflict driven and the user-defined search. As expected, nogood learning solvers outperform gecode, because their derived nogoods avoid the re-exploration of similar search sub-trees proven to be infeasible and information retrieved by the conflict analysis is used to guide the search. The clear winner is chuffed. The big difference in the performance of the LCG solvers may be surprising at first, but can be explained by the differences in the cumulative constraints. All three LCG solvers implement the cumulative constraint using the time-table propagation from [13], but only lazyfd and chuffed allow for variable durations and resource requirements as input as described in [9]. In addition, MiniZinc does not provide an interface for the cumulative constraint of lazyfd. Hence, the cumulative constraint is mapped into the time-indexed decomposition when compiling the model for ocpx and lazyfd.

Table 3. Comparison of the different solvers on the test set j30.
Full size table

3.4 Comparison to the State of the Art

Zhu et al. [16] present—to the best of our knowledge—the best exact solution method for MRCPSP. This method is based on Integer Linear Programming using a branch-and-cut for minimizing the makespan. It is implemented in the Mixed Integer Programming solver CPLEX 7.5. They run their method on a Linux machine with 1.8 GHz Xeon processor. Within one hour, it could optimally solve 506 instances out of 552 feasible instances with a mean total runtime of 393.1 s. The average runtime was 125.25 s for finding the best solution. By constrast, the best set up of chuffed could optimally solve 540 instances (34 more) within 10 min. In addition, the runtimes of chuffed are drastically lower. Thus, chuffed outperforms the state of the art.

Closed instances. With respect to [5, 16], there are 46 open instances in the test set j30. Within the 10 min runtime limit, the presented solver was able to close 34 of them. In preliminary experiments, we ran chuffed without a runtime limit and were able to close all instances. The last instance was closed after 18 hours.

4 Conclusion

We investigated different CP models for solving MRCPSP. To our best knowledge, it is the first published CP model, on which an exact solution method with nogood learning was applied. The best model uses the activity representation for modelling the resource constraints via the constraint cumulative and pairwise non-overlapping constraints for activities that might be in disjunction. All the considered user-defined searches were inferior to the default search of the CP solvers. The LCG solver chuffed was the best performing solver, which also outperformed the state of the art ILP solver [16]. Within 10 min, all open instances were closed except 12. Relaxing the time limit, all remaining open instances were closed within 18 h.