Otto-von-Guericke-Universität Magdeburg



The Dominance Graph as a Solution to the Two-Machine Flow-Shop Problem with Interval Processing Times

by Matsveichuk, N.; Sotskov, Y.; Werner, F.


Preprint series: 08-23, Preprints

90B35 Scheduling theory, See also {68M20}


Abstract: The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: Lower and upper bounds for the random processing time are given before scheduling, but its probability distribution between these bounds is unknown. For such a problem, there often does not exist a dominant schedule that remains optimal for all possible realizations of the job processing times, and we look for a minimal set of schedules that is dominant. Such a minimal dominant set of schedules may be represented by a dominance digraph. We investigate useful properties of such a digraph.

Keywords: Scheduling; Flow-Shop; Makespan; Uncertainty; Domination

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 10.02.2016 - Ansprechpartner: Pierre Krenzlin