Journal
COMPUTERS & INDUSTRIAL ENGINEERING
Volume 172, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cie.2022.108586
Keywords
Scheduling; Parallel machines; Sequence-dependent setups; Servers; Constraint Programming
Funding
- EU
- Ministry of Education, Youth and Sport of the Czech Republic [CZ.02.1.01/0.0/0.0/16_026/0008432]
- Ministry of Industry and Trade of the Czech Republic [CZ.01.1.02/0.0/0.0/20_321/0024399]
Ask authors/readers for more resources
This paper examines the scheduling problem of P|(seq), ser|C(max) and proposes a Constraint Programming (CP) model and constructive heuristics suitable for large-scale instances. The experimental comparison shows that our approach outperforms existing methods in terms of computation time and solution quality.
This paper examines scheduling problem denoted as P|(seq), ser|C(max )in Graham's notation; in other words, scheduling of tasks on parallel identical machines (P) with sequence-dependent setups (seq) each performed by one of the available servers (ser). The goal is to minimize the makespan (C-max). We propose a Constraint Programming (CP) model for finding the optimal solution and constructive heuristics suitable for large problem instances. These heuristics are also used to provide a feasible starting solution to the proposed CP model, significantly improving its efficiency. This combined approach constructs solutions for benchmark instances of up to 20 machines and 500 tasks in 10 s, with makespans 3 % to 115 % greater than the calculated lower bounds with a 5% average. The extensive experimental comparison also shows that our proposed approaches outperform the existing ones.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available