期刊
COMPUTERS & INDUSTRIAL ENGINEERING
卷 121, 期 -, 页码 139-149出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2018.05.014
关键词
Unrelated parallel machine scheduling; Constraint programming; Interval variables; Sequence dependent setup times; Machine dependent setup times
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据