A constraint programming approach for solving unrelated parallel machine scheduling problem. (July 2018)

• Record Type: Journal Article
• Authors: Gedik, Ridvan; Kalathia, Darshan; Egilmez, Gokhan; Kirac, Emre
• Is Part Of: Computers & industrial engineering. Volume 121(2018)
• Page Start: 139
• Page End: 149
• Publication Date: 2018-07
• Subjects: Unrelated parallel machine scheduling -- Constraint programming -- Interval variables -- Sequence dependent setup times -- Machine dependent setup times; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2018.05.014
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We propose a constraint programming (CP) model to solve the PMSP. Our model dominates state-of-art heuristics over small benchmark instances. It proves the optimality of 283 benchmark instances. Abstract: 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.