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

**Series:** 1996-15, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

- 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.

2

**Keywords:**

job shop scheduling, sequencing, stability analysis, sensitivity

**This paper was published in:**

OMEGA, Vol. 25, 1997, No. 4, 397 - 414.