On the efficient modeling and solution of the multi-mode resource-constrained project scheduling problem with generalized precedence relations
Alexander Schnell (alexander.schnell@univie.ac.at) and
Richard F. Hartl (richard.hartl@univie.ac.at)
Additional contact information
Alexander Schnell: University of Vienna
Richard F. Hartl: University of Vienna
OR Spectrum: Quantitative Approaches in Management, 2016, vol. 38, issue 2, No 2, 283-303
Abstract:
Abstract For variants of the single-mode resource-constrained project scheduling problem, state-of-the-art exact algorithms combine a Branch and Bound algorithm with principles from Constraint Programming and Boolean Satisfiability Solving. In our paper, we propose new exact approaches extending the above principles to the multi-mode RCPSP (MRCPSP) with generalized precedence relations (GPRs). More precisely, we implemented two constraint handlers cumulativemm and gprecedencemm for the optimization framework SCIP. With the latter, one can model renewable resource constraints and GPRs in the context of multi-mode activities, respectively. Moreover, they integrate domain propagation and explanation generation techniques for the above problem characteristics. We formulate three SCIP-models for the MRCPSP with GPRs, two without and one with our constraint handler gprecedencemm. Our computational results on instances from the literature with 30, 50 and 100 activities show that the addition of this constraint handler significantly strengthens the SCIP-model. Moreover, we outperform the state-of-the-art exact approach on instances with 50 activities when imposing time limits of 27 s. In addition, we close (find the optimal solution and prove its optimality for) 289 open instances and improve the best known makespan for 271 instances from the literature.
Keywords: Project scheduling; Constraint programming; Multi-mode; Generalized precedence relations; SAT solving (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (7)
Downloads: (external link)
http://link.springer.com/10.1007/s00291-015-0419-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
Related works:
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:spr:orspec:v:38:y:2016:i:2:d:10.1007_s00291-015-0419-6
Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291
DOI: 10.1007/s00291-015-0419-6
Access Statistics for this article
OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch
More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla (sonal.shukla@springer.com) and Springer Nature Abstracting and Indexing (indexing@springernature.com).