Zurück zu den Preprints des Jahres 2008


2008-23

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

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


Series: 2008-23, Preprints

MSC:
90B35 Scheduling theory, deterministic

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