Constraint Programming and constructive heuristics for parallel machine scheduling with sequence-dependent setups and common servers
Result description
This paper examines scheduling problem denoted as ???? |????????????, ????????????|???????????????? in Graham’s notation; in other words, scheduling of tasks on parallel identical machines (???? ) with sequence-dependent setups (????????????) each performed by one of the available servers (????????????). The goal is to minimize the makespan (????????????????). 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 11.5 % greater than the calculated lower bounds with a 5% average. The extensive experimental comparison also shows that our proposed approaches outperform the existing ones.
Keywords
SchedulingParallel machinesSequence-dependent setupsServersConstraint ProgrammingHeuristic
The result's identifiers
Result code in IS VaVaI
Alternative codes found
RIV/68407700:21730/22:00361840
Result on the web
DOI - Digital Object Identifier
Alternative languages
Result language
angličtina
Original language name
Constraint Programming and constructive heuristics for parallel machine scheduling with sequence-dependent setups and common servers
Original language description
This paper examines scheduling problem denoted as ???? |????????????, ????????????|???????????????? in Graham’s notation; in other words, scheduling of tasks on parallel identical machines (???? ) with sequence-dependent setups (????????????) each performed by one of the available servers (????????????). The goal is to minimize the makespan (????????????????). 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 11.5 % greater than the calculated lower bounds with a 5% average. The extensive experimental comparison also shows that our proposed approaches outperform the existing ones.
Czech name
—
Czech description
—
Classification
Type
Jimp - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
EF16_026/0008432: Cluster 4.0 - Methodology of System Integration
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Computers & Industrial Engineering
ISSN
0360-8352
e-ISSN
1879-0550
Volume of the periodical
172
Issue of the periodical within the volume
October
Country of publishing house
GB - UNITED KINGDOM
Number of pages
16
Pages from-to
—
UT code for WoS article
000864653000014
EID of the result in the Scopus database
2-s2.0-85137028802
Basic information
Result type
Jimp - Article in a specialist periodical, which is included in the Web of Science database
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Year of implementation
2022