Multi-mode resource constrained pro ject scheduling using RCPSP and SAT solvers

J. Coelho and Mario Vanhoucke

Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium from Ghent University, Faculty of Economics and Business Administration

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 NPhard 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 efficient meta-heuristic procedure 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.

Keywords: project scheduling; SAT; multi-mode RCPSP (search for similar items in EconPapers)
Pages: 2 pages
Date: 2009-09
New Economics Papers: this item is included in nep-cmp and nep-ppm
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://wps-feb.ugent.be/Papers/wp_09_614.pdf (application/pdf)

Related works:
Journal Article: Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers (2011)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:rug:rugwps:09/614

Access Statistics for this paper

More papers in Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium from Ghent University, Faculty of Economics and Business Administration Contact information at EDIRC.
Bibliographic data for series maintained by Nathalie Verhaeghe ().