Multi-mode resource constrained pro ject scheduling using RCPSP and SAT solvers
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.
|Date of creation:||Sep 2009|
|Date of revision:|
|Contact details of provider:|| Postal: |
Phone: ++ 32 (0) 9 264 34 61
Fax: ++ 32 (0) 9 264 35 92
Web page: http://www.ugent.be/eb
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:rug:rugwps:09/614. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Nathalie Verhaeghe)
If references are entirely missing, you can add them using this form.