Constraint Programming and constructive heuristics for parallel machine scheduling with sequence-dependent setups and common servers

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00361840" target="_blank" >RIV/68407700:21230/22:00361840 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/22:00361840

Výsledek na webu

<a href="https://doi.org/10.1016/j.cie.2022.108586" target="_blank" >https://doi.org/10.1016/j.cie.2022.108586</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.cie.2022.108586" target="_blank" >10.1016/j.cie.2022.108586</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Constraint Programming and constructive heuristics for parallel machine scheduling with sequence-dependent setups and common servers

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Constraint Programming and constructive heuristics for parallel machine scheduling with sequence-dependent setups and common servers

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

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í

2022

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 periodika

Computers & Industrial Engineering

ISSN

0360-8352

e-ISSN

1879-0550

Svazek periodika

172

Číslo periodika v rámci svazku

October

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

16

Strana od-do

—

Kód UT WoS článku

000864653000014

EID výsledku v databázi Scopus

2-s2.0-85137028802