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

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
A Lagrangian relaxation algorithm for stochastic fixed interval scheduling with non-identical machines and classes
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10103 - Statistics and probability

Project
<a href="/en/project/GA22-11867S" target="_blank" >GA22-11867S: Advanced operational research methods for optimal decision-making in waste management</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)