Stability of an optimal schedule in a job shop

What is it about?

This paper is devoted to the calculation of the stability radius of an optimal schedule for a job shop problem, when the objective is to minimize mean or maximum flow times. The approach used 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 as do not destroy the optimality of the schedule at hand. This paper investigates the influence of errors and possible changes of the processing times on the optimality of a schedule. To this end, extensive numerical experiments with randomly generated job shop scheduling problems are performed and discussed.

Featured Image

Why is it important?

The developed software provides the possibility of comparing 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 generated job shop problems.