Name
Abstract | ||
|---|---|---|
This paper reports on a new solution approach for the well-known multi-mode resource-constrained project scheduling problem (MMRCPSP). This problem type aims at the selection of a single activity mode from a set of available modes in order to construct a precedence and a (renewable and non-renewable) resource feasible project schedule with a minimal makespan. The problem type is known to be NP- hard and has been solved using various exact as well as (meta-)heuristic procedures. The new algorithm splits the problem type into a mode assignment and a single mode project scheduling step. The mode assignment step is solved by a satisfiability (SAT) problem solver and returns a feasible mode selection to the project scheduling step. The project scheduling step is solved using a e!cient meta-heuristic proce- dure from literature to solve the resource-constrained project scheduling problem (RCPSP). However, unlike many traditional meta-heuristic methods in literature to solve the MMRCPSP, the new approach executes these two steps in one run, relying on a single priority list. Straightforward adaptations to the pure SAT solver by using pseudo boolean non-renewable resource constraints has led to a high quality solution approach in a reasonable computational time. Computational results show that the PSPLIB problem instances can be solved better than the current best procedures from literature. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ejor.2011.03.019 | European Journal of Operational Research |
Keywords | Field | DocType |
Project scheduling,SAT,Multi-mode RCPSP | Schedule (project management),Mathematical optimization,Job shop scheduling,Fair-share scheduling,Scheduling (computing),Computer science,Boolean satisfiability problem,Solver,Dynamic priority scheduling,Operations management,Project management | Journal |
Volume | Issue | ISSN |
213 | 1 | 0377-2217 |
Citations | PageRank | References |
35 | 1.23 | 33 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José Coelho | 1 | 110 | 7.94 |
| M Vanhoucke | 2 | 919 | 55.85 |