Makespan Minimization with Sequence-dependent Non-overlapping Setups
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00328781" target="_blank" >RIV/68407700:21230/19:00328781 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21730/19:00328781
Result on the web
<a href="http://www.scitepress.org/DigitalLibrary/Link.aspx?doi=10.5220/0007362700910101" target="_blank" >http://www.scitepress.org/DigitalLibrary/Link.aspx?doi=10.5220/0007362700910101</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5220/0007362700910101" target="_blank" >10.5220/0007362700910101</a>
Alternative languages
Result language
angličtina
Original language name
Makespan Minimization with Sequence-dependent Non-overlapping Setups
Original language description
This paper deals with a scheduling problem that emerges in the production of water tubes of different sizes that require reconfiguration of the machines. The reconfiguration of the machines leads to the notion of sequence-dependent setup times between tasks. These setups are often performed by a single person who cannot serve more than one machine at the same moment, i.e., the setups must not overlap. Surprisingly, the problem with non-overlapping setups has received only a little attention so far. To solve this problem, we propose an Integer Linear Programming formulation, Constraint Programming models and a hybrid heuristic that leverages the strength of Integer Linear Programming in the shortest Hamiltonian path problem and the efficiency of Constraint Programming at sequencing problems with makespan minimization. The experimental evaluation shows that among the proposed exact approaches, the Constraint Programming is a superior method being able to solve instances with 3 machines and up to 11 tasks on each machine to optimality within a few seconds. The proposed hybrid heuristic attains high-quality solutions for instances with 50 machines and up to 116 tasks on each machine.
Czech name
—
Czech description
—
Classification
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)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
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
Article name in the collection
Proceedings of the 8th International Conference on Operations Research and Enterprise Systems
ISBN
978-989-758-352-0
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
91-101
Publisher name
SciTePress
Place of publication
Madeira
Event location
Prague
Event date
Feb 19, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000668111400010