96-15
Stability of an Optimal Schedule in a Job Shop
by Sotskov, Y.N.; Sotskova, N.Y.; Werner, F.
Preprint series: 96-15, Preprints
The paper is published: OMEGA, Vol. 25, 1997, No. 4, 397 - 414.
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 tominimize mean or maximum flow times. The used approach may be regardedas an a posteriori analysis, in which an optimal schedule has already beenconstructed and the question is to determine such changes in the processingtimes of operations, which do not destroy the optimality of the schedule athand. More precisely, the stability radius denotes the largest quantity ofindependent variations of the processing times of the operations such thatan optimal schedule of the problem remains optimal. Although in schedul-ing theory mainly deterministic problems are considered and the processingtimes are supposed to be given in advance, such scheduling problems do notoften arise in practice. Even if the processing times are known before ap-plying a scheduling procedure, OR workers are forced to take into accountpossible 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 other1 Supported by Deutsche Forschungsgemeinschaft (Project ScheMA) and by INTAS(Project 93-257)words, usually in practice a schedule has to be realized under conditions ofuncertainty. This paper investigates the influence of round-off errors of theprocessing times on the property of a schedule to be optimal. To this end, ex-tensive numerical experiments with randomly generated job shop schedulingproblems are performed and discussed. Due to the developed software, wehave the possibility to compare the values of the stability radii, the numbersof 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, onaverage, for randomly y generated job shop problems.2
Keywords: job shop scheduling, sequencing, stability analysis, sensitivity
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.