Flow-based formulations for operational fixed interval scheduling problems with random delays

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10363665" target="_blank" >RIV/00216208:11320/17:10363665 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s10287-016-0262-5" target="_blank" >http://dx.doi.org/10.1007/s10287-016-0262-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10287-016-0262-5" target="_blank" >10.1007/s10287-016-0262-5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Flow-based formulations for operational fixed interval scheduling problems with random delays

Popis výsledku v původním jazyce

We deal with operational fixed interval scheduling problem with random delays in job processing times. We formulate two stochastic programming problems. In the first problem with a probabilistic objective, all jobs are processed on available machines and the goal is to obtain a schedule with the highest attainable reliability. The second problem is to select a subset of jobs with the highest reward under a chance constraint ensuring feasibility of the schedule with a prescribed probability. We assume that the multivariate distribution of delays follows an Archimedean copula, whereas there are no restrictions on marginal distributions. We introduce new deterministic integer linear reformulations based on flow problems. We compare the formulations with the extended robust coloring problem, which was shown to be a deterministic equivalent to the stochastic programming problem with probabilistic objective by Branda et al. (Comput Ind Eng 93: 45-54, 2016). In the numerical study, we report average computational times necessary to solve a large number of simulated instances. It turns out that the new flow-based formulation helps to solve the FIS problems considerably faster than the other one.

Název v anglickém jazyce

Flow-based formulations for operational fixed interval scheduling problems with random delays

Popis výsledku anglicky

We deal with operational fixed interval scheduling problem with random delays in job processing times. We formulate two stochastic programming problems. In the first problem with a probabilistic objective, all jobs are processed on available machines and the goal is to obtain a schedule with the highest attainable reliability. The second problem is to select a subset of jobs with the highest reward under a chance constraint ensuring feasibility of the schedule with a prescribed probability. We assume that the multivariate distribution of delays follows an Archimedean copula, whereas there are no restrictions on marginal distributions. We introduce new deterministic integer linear reformulations based on flow problems. We compare the formulations with the extended robust coloring problem, which was shown to be a deterministic equivalent to the stochastic programming problem with probabilistic objective by Branda et al. (Comput Ind Eng 93: 45-54, 2016). In the numerical study, we report average computational times necessary to solve a large number of simulated instances. It turns out that the new flow-based formulation helps to solve the FIS problems considerably faster than the other one.

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/GBP402%2F12%2FG097" target="_blank" >GBP402/12/G097: DYME-Dynamické modely v ekonomii</a><br>

Návaznosti

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

Rok uplatnění

2017

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

Computational Management Science

ISSN

1619-697X

e-ISSN

—

Svazek periodika

14

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

17

Strana od-do

161-177

Kód UT WoS článku

000411375200009

EID výsledku v databázi Scopus

2-s2.0-84982149343