Zurück zu den Preprints des Jahres 1996


Stability of an Optimal Schedule in a Job Shop

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

Series: 1996-15, Preprints

90B35 Scheduling theory, deterministic

- This paper is devoted to the calculation of the stability ra-
dius of an optimal schedule for a job shop problem, when the objective is to
minimize mean or maximum flow times. The used approach may be regarded
as an a posteriori analysis, in which an optimal schedule has already been
constructed and the question is to determine such changes in the processing
times of operations, which do not destroy the optimality of the schedule at
hand. More precisely, the stability radius denotes the largest quantity of
independent variations of the processing times of the operations such that
an optimal schedule of the problem remains optimal. Although in schedul-
ing theory mainly deterministic problems are considered and the processing
times are supposed to be given in advance, such scheduling problems do not
often arise in practice. Even if the processing times are known before ap-
plying a scheduling procedure, OR workers are forced to take into account
possible changes and errors within the practical realization of a schedule,
e.g. additionally arriving jobs, machine breakdowns, the precision of equip-
ment, which is used to calculate the processing times, and so on. In other
1 Supported by Deutsche Forschungsgemeinschaft (Project ScheMA) and by INTAS
(Project 93-257)
words, usually in practice a schedule has to be realized under conditions of
uncertainty. This paper investigates the influence of round-off errors of the
processing times on the property of a schedule to be optimal. To this end, ex-
tensive numerical experiments with randomly generated job shop scheduling
problems are performed and discussed. Due to the developed software, we
have the possibility to compare the values of the stability radii, the numbers
of optimal schedules and some other 'numbers' for two often used criteria.
The main question we try to answer is how large the stability radius is, on
average, for randomly y generated job shop problems.

job shop scheduling, sequencing, stability analysis, sensitivity

This paper was published in:
OMEGA, Vol. 25, 1997, No. 4, 397 - 414.