by Sotskov, Y.N., Wagelmans, A.P.M., Werner, F..

**Series:** 1997-19, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic
- 90C27 Combinatorial optimization

**Abstract:**

bility analysis for scheduling problems. In spite of impressive theoretical results

in sequencing and scheduling, up to now the implementation of scheduling al-

gorithms with a rather deep mathematical background in production planning,

scheduling and control, and in other real-life problems with sequencing aspects

is limited. In classical scheduling theory, mainly deterministic systems are con-

sidered and the processing times of all operations are supposed to be given in

advance. Such problems do not often arise in practice: Even if the processing

times are known before applying a scheduling procedure, OR workers are forced

to take into account the precision of equipment, which is used to calculate the

processing times, round-off errors in the calculation of a schedule, errors within

the practical realization of a schedule, machine breakdowns, additional jobs and

so on. This paper is devoted to the calculation of the stability radius of an

optimal or an approximate schedule. We survey some recent results in this field

and derive new results in order to make this approach more suitable for prac-

tical use. Computational results on the calculation of the stability radius for

randomly generated job shop scheduling problems are presented. The extreme

values of the stability radius are considered in more detail. The new results are

amply illustrated with examples.

**Keywords:**

Stability, Scheduling, Disjunctive graph, Linear binary programming

**This paper was published in:**

Annals of Operations Research 83, 1998, 213 - 252.