Non-overlapping Sequence-Dependent Setup Scheduling with Dedicated Tasks

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

Nalezeny alternativní kódy

RIV/68407700:21730/20:00335589

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Non-overlapping Sequence-Dependent Setup Scheduling with Dedicated Tasks

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Non-overlapping Sequence-Dependent Setup Scheduling with Dedicated Tasks

Popis výsledku anglicky

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.

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

<a href="/cs/project/EF16_026%2F0008432" target="_blank" >EF16_026/0008432: Klastr 4.0 - Metodologie systémové integrace</a><br>

Návaznosti

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

Rok uplatnění

2020

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

Operations Research and Enterprise Systems

ISBN

978-3-030-37583-6

ISSN

1865-0929

e-ISSN

—

Počet stran výsledku

24

Strana od-do

23-46

Název nakladatele

Springer

Místo vydání

Cham

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

—