Zurück zu den Preprints des Jahres 1995


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

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

Series: 1995-23, Preprints

90B35 Scheduling theory, deterministic

The main objective of this paper is to stimulate interest in stability analysis
for scheduling problems. Inspite of impressive theoretical results in sequencing
and scheduling, the implementation of scheduling algorithms with a rather
deep mathematical background in production planning, scheduling and in
other real-life sequencing problems is up to now limited. In scheduling theory,
deterministic systems are mainly considered and so the processing times of all
operations are supposed to be given in advance. Unfortunately, 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 on the computer, possible
errors within the practical realization of a schedule, machine breakdowns,
additionally arriving jobs with high priorities 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 a practical use. Moreover, first
computational results on the calculation of the stability radius for randomly
generated job shop scheduling problems are presented. Since the extreme
values of the stability radius are of particular importance for applications,
we consider these cases more in detail. At the end of the paper some open
questions and trends of stability analysis in scheduling theory are discussed.


This paper was published in:
Annals of Operations Research 83, 1998, 213 - 252.