Zurück zu den Preprints des Jahres 1997


1997-19

On the Calculation of the Stability Radius of an Optimal or an Approximate Schedule

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.