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

Martin Branda () and Štěpán Hájek
Additional contact information
Štěpán Hájek: Charles University in Prague

Computational Management Science, 2017, vol. 14, issue 1, No 9, 177 pages

Abstract: Abstract 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: Fixed interval scheduling; Random delays; Stochastic programming; Flow-based formulation; Archimedean copula; Integer programming; 90C15; 90B36; 90C10 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10287-016-0262-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:comgts:v:14:y:2017:i:1:d:10.1007_s10287-016-0262-5

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-016-0262-5

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().