Makespan Minimization with Sequence-dependent Non-overlapping Setups

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21730/19:00328781

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Makespan Minimization with Sequence-dependent Non-overlapping Setups

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Makespan Minimization with Sequence-dependent Non-overlapping Setups

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the 8th International Conference on Operations Research and Enterprise Systems

ISBN

978-989-758-352-0

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

91-101

Název nakladatele

SciTePress

Místo vydání

Madeira

Místo konání akce

Prague

Datum konání akce

19. 2. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000668111400010