Publication result detail

Fixed interval scheduling under uncertainty - A tabu search algorithm for an extended robust coloring formulation

NOVOTNÝ, J.; BRANDA, M.; OLSTAD, A.

Original Title

Fixed interval scheduling under uncertainty - A tabu search algorithm for an extended robust coloring formulation

English Title

Fixed interval scheduling under uncertainty - A tabu search algorithm for an extended robust coloring formulation

Type

WoS Article

Original Abstract

We propose several formulations of the fixed interval scheduling problem under uncertainty, where the risk is represented by random delays in processing times. We employ various stochastic programming and robust coloring problems to deal with the uncertainty. Our main goal is to introduce equivalent deterministic reformulations of the stochastic programming problems. We show that the minimization of the expected number of overlaps is equivalent to the deterministic robust coloring problem under particular choice of the penalties. Moreover, we extend the robust coloring problem to obtain equivalence with the stochastic programming problem with the schedule reliability objective under multivariate distribution of delays represented by an Archimedean copula. We show that small simulated instances of this problem can be solved to optimality by available software tools and we propose a tabu search algorithm suitable for larger instances.

English abstract

We propose several formulations of the fixed interval scheduling problem under uncertainty, where the risk is represented by random delays in processing times. We employ various stochastic programming and robust coloring problems to deal with the uncertainty. Our main goal is to introduce equivalent deterministic reformulations of the stochastic programming problems. We show that the minimization of the expected number of overlaps is equivalent to the deterministic robust coloring problem under particular choice of the penalties. Moreover, we extend the robust coloring problem to obtain equivalence with the stochastic programming problem with the schedule reliability objective under multivariate distribution of delays represented by an Archimedean copula. We show that small simulated instances of this problem can be solved to optimality by available software tools and we propose a tabu search algorithm suitable for larger instances.

Keywords

Fixed interval scheduling; Uncertainty; Stochastic programming; Robust coloring problem; Archimedean copula; Tabu search

Key words in English

Fixed interval scheduling; Uncertainty; Stochastic programming; Robust coloring problem; Archimedean copula; Tabu search

Authors

NOVOTNÝ, J.; BRANDA, M.; OLSTAD, A.

RIV year

2021

Released

01.03.2016

Publisher

PERGAMON-ELSEVIER SCIENCE LTD

Location

OXFORD

ISBN

0360-8352

Periodical

Computers & Industrial Engineering

Volume

93

Number

March

State

United Kingdom of Great Britain and Northern Ireland

Pages from

45

Pages to

54

Pages count

10

URL

https://www-sciencedirect-com.ezproxy.lib.vutbr.cz/science/article/pii/S036083521500501X

BibTex

@article{BUT171078,
  author="Jan {Novotný} and Martin {Branda} and Asmund {Olstad}",
  title="Fixed interval scheduling under uncertainty - A tabu search algorithm for an extended robust coloring formulation",
  journal="Computers & Industrial Engineering",
  year="2016",
  volume="93",
  number="March",
  pages="45--54",
  doi="10.1016/j.cie.2015.12.021",
  issn="0360-8352",
  url="https://www-sciencedirect-com.ezproxy.lib.vutbr.cz/science/article/pii/S036083521500501X"
}