A Lagrangian relaxation algorithm for stochastic fixed interval scheduling with non-identical machines and classes

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10484217" target="_blank" >RIV/00216208:11320/24:10484217 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8mP3auR6ik" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8mP3auR6ik</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

A Lagrangian relaxation algorithm for stochastic fixed interval scheduling with non-identical machines and classes

Popis výsledku v původním jazyce

This paper deals with operational fixed interval scheduling problems under uncertainty caused by random delays. This stochastic programming problem has a deterministic reformulation based on network flow under the assumption that the machines are identical and the multivariate distribution of random delays follows an Archimedean copula. In this paper, we focus on the problem with heterogeneous machines and jobs classes. The deterministic problem with no delays and more than one machine type has been shown to be NP-hard. We generalize the deterministic reformulation of the stochastic problem with random delays for non-identical (heterogeneous) machines. This formulation for more than one machine type loses an important property of total unimodularity that holds for identical machines reformulation using the network flow problem. Therefore, an algorithm based on the Lagrangian relaxation is derived and implemented together with an efficient upper bounding heuristic. Its efficiency is confirmed by solving a large number of simulated instances.

Název v anglickém jazyce

A Lagrangian relaxation algorithm for stochastic fixed interval scheduling with non-identical machines and classes

Popis výsledku anglicky

This paper deals with operational fixed interval scheduling problems under uncertainty caused by random delays. This stochastic programming problem has a deterministic reformulation based on network flow under the assumption that the machines are identical and the multivariate distribution of random delays follows an Archimedean copula. In this paper, we focus on the problem with heterogeneous machines and jobs classes. The deterministic problem with no delays and more than one machine type has been shown to be NP-hard. We generalize the deterministic reformulation of the stochastic problem with random delays for non-identical (heterogeneous) machines. This formulation for more than one machine type loses an important property of total unimodularity that holds for identical machines reformulation using the network flow problem. Therefore, an algorithm based on the Lagrangian relaxation is derived and implemented together with an efficient upper bounding heuristic. Its efficiency is confirmed by solving a large number of simulated instances.

Druh

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

CEP obor

—

OECD FORD obor

10103 - Statistics and probability

Projekt

<a href="/cs/project/GA22-11867S" target="_blank" >GA22-11867S: Pokročilé metody operačního výzkumu pro optimální rozhodování v odpadovém hospodářství</a><br>

Návaznosti

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

Rok uplatnění

2024

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 and Operations Research

ISSN

0305-0548

e-ISSN

1873-765X

Svazek periodika

2024

Číslo periodika v rámci svazku

164

Stát vydavatele periodika

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

Počet stran výsledku

22

Strana od-do

106542

Kód UT WoS článku

001166378400001

EID výsledku v databázi Scopus

2-s2.0-85182746366