A Boolean satisfiability approach to the resource-constrained project scheduling problem

被引：0
作者：
Andrei Horbach
机构：
[1] Christian-Albrechts-Universität zu Kiel,Institute of Business Administration
来源：
Annals of Operations Research | 2010年 / 181卷
关键词：
Project management; Resource constraints; Production-scheduling; Complete algorithms; Propositional satisfiability;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We formulate the resource-constrained project scheduling problem as a satisfiability problem and adapt a satisfiability solver for the specific domain of the problem. Our solver is lightweight and shows good performance both in finding feasible solutions and in proving lower bounds. Our numerical tests allowed us to close several benchmark instances of the RCPSP that have never been closed before by proving tighter lower bounds and by finding better feasible solutions. Using our method we solve optimally more instances of medium and large size from the benchmark library PSPLIB and do it faster compared to any other existing solver.
引用
收藏
页码：89 / 107
页数：18
相关论文
共 62 条
[1]  
Achterberg T.(2007)Conflict analysis in mixed integer programming Discrete Optimization 4 4-20
[2]  
Baptiste P.(2004)Tight LP bounds for resource constrained project scheduling OR Spectrum 26 251-262
[3]  
Demassey S.(2000)A linear programming and constraint propagation-based lower bound for the RCPSP European Journal of Operational Research 127 355-362
[4]  
Brucker P.(1998)A branch and bound algorithm for the resource-constrained project scheduling problem European Journal of Operational Research 107 272-288
[5]  
Knust S.(1999)Resource-constrained project scheduling: notation, classification, models, and methods European Journal of Operational Research 112 3-41
[6]  
Brucker P.(1960)A computing procedure for quantification theory Journal of the ACM 7 201-215
[7]  
Knust S.(1962)A machine program for theorem-proving Communications of the ACM 5 394-397
[8]  
Schoo A.(2007)A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem Operations Research 55 457-469
[9]  
Thiele O.(1997)New benchmark results for the resource-constrained project scheduling problem Management Science 43 1485-1492
[10]  
Brucker P.(2000)A branch-and-bound algorithm for the resource-constrained project scheduling problem Mathematical Methods of Operations Research 52 413-439
1234567