Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/178271 
Erscheinungsjahr: 
2017
Quellenangabe: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 4 [Publisher:] Elsevier [Place:] Amsterdam [Year:] 2017 [Pages:] 1-11
Verlag: 
Elsevier, Amsterdam
Zusammenfassung: 
In our paper, we analyze new exact approaches for the multi-mode resource-constrained project scheduling (MRCPSP) problem with the aim of makespan minimization. For the single-mode RCPSP (SRCPSP) recent exact algorithms combine a Branch and Bound algorithm with principles from Constraint Programming (CP) and Boolean Satisfiability Solving (SAT). We extend the above principles for the solution of MRCPSP instances. This generalization is on the one hand achieved on the modeling level. We propose three CP-based formulations of the MRCPSP for the G12 CP platform and the optimization framework SCIP which both provide solution techniques combining CP and SAT principles. For one of the latter we implemented a new global constraint for SCIP, which generalizes the domain propagation and explanation generation principles for renewable resources in the context of multi-mode jobs. Our constraint applies the above principles in a more general way than the existing global constraint in SCIP. We compare our approaches with the state-of-the-art exact algorithm from the literature on MRCPSP instances with 20 and 30 jobs. Our computational experiments show that we can outperform the latter approach on these instances. Furthermore, we are the first to close (find the optimal solution and prove its optimality for) 628 open instances with 50 and 100 jobs from the literature. In addition, we improve the best known lower bound of 2815 instances and the best known upper bound of 151 instances.
Schlagwörter: 
Multi-mode resource-constrained project scheduling
Constraint programming
SAT solving
SCIP
Lazy clause generation
Exact algorithm
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by-nc-nd Logo
Dokumentart: 
Article

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.