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