Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/178271 
Year of Publication: 
2017
Citation: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 4 [Publisher:] Elsevier [Place:] Amsterdam [Year:] 2017 [Pages:] 1-11
Publisher: 
Elsevier, Amsterdam
Abstract: 
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.
Subjects: 
Multi-mode resource-constrained project scheduling
Constraint programming
SAT solving
SCIP
Lazy clause generation
Exact algorithm
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by-nc-nd Logo
Document Type: 
Article

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.