Non-overlapping Sequence-Dependent Setup Scheduling with Dedicated Tasks

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00335589" target="_blank" >RIV/68407700:21230/20:00335589 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21730/20:00335589
Result on the web
<a href="https://link.springer.com/chapter/10.1007%2F978-3-030-37584-3_2" target="_blank" >https://link.springer.com/chapter/10.1007%2F978-3-030-37584-3_2</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-37584-3_2" target="_blank" >10.1007/978-3-030-37584-3_2</a>

Result language
angličtina
Original language name
Non-overlapping Sequence-Dependent Setup Scheduling with Dedicated Tasks
Original language description
The paper deals with a parallel machines scheduling problem with dedicated tasks with sequence-dependent setup times that are subject to the non-overlapping constraint. This problem emerges in the productions where only one machine setter is available on the shop floor. We consider that setups are performed by a single person who cannot serve more than one machine at the same moment, i.e., the setups must not overlap in time. We show that the problem remains NP-hard under the fixed sequence of tasks on each machine. To solve the problem, we propose an Integer Linear Programming formulation, five Constraint Programming models, and a hybrid heuristic algorithm LOFAS that leverages the strength of Integer Linear Programming for the Traveling Salesperson Problem (TSP) and the efficiency of Constraint Programming at sequencing problems minimizing makespan. Furthermore, we investigate the impact of the TSP solution quality on the overall objective value. The results show that LOFAS with a heuristic TSP solver achieves on average 10.5% worse objective values but it scales up to 5000 tasks with 5 machines.
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/EF16_026%2F0008432" target="_blank" >EF16_026/0008432: Cluster 4.0 - Methodology of System Integration</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)