A constraint programming approach for solving unrelated parallel machine scheduling problem

被引:62
作者
Gedik, Ridvan [1 ]
Kalathia, Darshan [1 ]
Egilmez, Gokhan [1 ]
Kirac, Emre [2 ]
机构
[1] Univ New Haven, Dept Mech & Ind Engn, 300 Boston Post Rd, West Haven, CT 06516 USA
[2] Univ Houston Clear Lake, Dept Engn, 2700 Bay Area Blvd, Houston, TX 77058 USA
关键词
Unrelated parallel machine scheduling; Constraint programming; Interval variables; Sequence dependent setup times; Machine dependent setup times; COLONY OPTIMIZATION ALGORITHM; DEPENDENT SETUP TIMES; MAKESPAN; SEARCH; MINIMIZE;
D O I
10.1016/j.cie.2018.05.014
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This paper addresses the non-preemptive unrelated parallel machine scheduling problem (PMSP) with job sequence and machine dependent setup times. This is a widely seen NP-hard (non-deterministic polynomial-time) problem with the objective to minimize the makespan. This study provides a noval constraint programming (CP) model with two customized branching strategies that utilize CP's global constraints, interval decision variables, and domain filtering algorithms. The performance of the CP model is evaluated against the state-of-art algorithms. In addition, we compare the performance of the default branching method in the CP solver against the two customized variants. In terms of average solution quality, the computational results indicate that the CP model slightly outperforms all of the state-of-art algorithms in solving small problem instances, is able to prove the optimality of 283 currently best-known solutions. It is also effective in finding good quality feasible solutions for the larger problem instances.
引用
收藏
页码:139 / 149
页数:11
相关论文
共 31 条
[31]   Makespan minimization for scheduling unrelated parallel machines with setup times [J].
Ying, Kuo-Ching ;
Lee, Zne-Jung ;
Lin, Shih-Wei .
JOURNAL OF INTELLIGENT MANUFACTURING, 2012, 23 (05) :1795-1803