A Constraint Programming-Based Branch and Bound Algorithm for Job Shop Problems
In recent years, constraint programming (CP) has been widely applied to solved scheduling problems. As one of the key elements in CP, constraint propagation has been proved to be an efficient methodology to speed up the search process. In this paper, we develop a hybrid branch and bound algorithm with CP technique, called HCPBAB, which focuses on branches cutting to achieve outstanding performance tuning and constraints handling ability compared with the original method. Moreover, we extend the popular input/output negation, input-or-output constraint propagation process into HCPBAB to extensively test our proposed method. Experimental results on 40 instances taken from standard job shop benchmarks show that 33 instances are optimally solved while HCPBAB obtains 11 better solutions compared with Rego C’s results in 2009.
Job Shop Scheduling Problem Branch-and-Bound Constraint Programming Constraint Propagation
Yuanyuan Tan Shixin Liu Dazhi Wang
School of Information Science & Engineering, Northeastern University; Key Laboratory off Integrated Automation of Process Industry Shenyang 110004, China
国际会议
The 22nd China Control and Decision Conference(2010年中国控制与决策会议)
徐州
英文
173-178
2010-05-26（万方平台首次上网日期，不代表论文的发表时间）