Flow-based formulations for operational fixed interval scheduling problems with random delays
Result description
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.
Keywords
Integer programmingArchimedean copulaFlow-based formulationStochastic programmingRandom delaysFixed interval scheduling
The result's identifiers
Result code in IS VaVaI
Result on the web
DOI - Digital Object Identifier
Alternative languages
Result language
angličtina
Original language name
Flow-based formulations for operational fixed interval scheduling problems with random delays
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
Jimp - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10103 - Statistics and probability
Result continuities
Project
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Computational Management Science
ISSN
1619-697X
e-ISSN
—
Volume of the periodical
14
Issue of the periodical within the volume
1
Country of publishing house
DE - GERMANY
Number of pages
17
Pages from-to
161-177
UT code for WoS article
000411375200009
EID of the result in the Scopus database
2-s2.0-84982149343
Basic information
Result type
Jimp - Article in a specialist periodical, which is included in the Web of Science database
OECD FORD
Statistics and probability
Year of implementation
2017