Abstract
The main objective of this paper is to stimulate interest in stability analysis for scheduling problems. In spite of impressive theoretical results in sequencing and scheduling, up to now the implementation of scheduling algorithms with a rather deep mathematical back-ground in production planning, scheduling and control, and in other real-life problems with sequencing aspects is limited. In classical scheduling theory, mainly deterministic systems are considered and the processing times of all operations are supposed to be given in advance. 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, errors within the practical realization of a schedule, machine breakdowns, additional jobs, 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 practical use. Computational results on the calculation of the stability radius for randomly generated job shop scheduling problems are presented. The extreme values of the stability radius are considered in more detail. The new results are amply illustrated with examples.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
H. Bräsel, Yu.N. Sotskov and F. Werner, Stability of a schedule minimizing mean flow time, Math. Comput. Modelling 24(1996)39–53.
M.J. Eisner and D.G. Severance, Mathematical techniques for efficient record segmentation in large shared databases, J. ACM 23(1976)619–635.
E. Girlich, Yu.N. Sotskov and F. Werner, Extreme values of the stability radius of an approximate solution of a linear Boolean minimization problem, Preprint 6 93, TU Magdeburg, 1993.
E.N. Gordeev and V.K. Leontev, The complexity of the tabulation of trajectory problems, U.S.S.R. Comput. Maths. Math. Phys. 25, No.4(1985)199–201.
E.N. Gordeev and V.K. Leontev, Stability in bottleneck problems, U.S.S.R. Comput. Maths. Math. Phys. 20, No.4(1980)275–280.
M.Y. Kovalyov and Yu.N. Sotskov, The stability of an ε-approximate solution of a minimization problem of Boolean linear forms, Vesti Akad. Navuk BSSR, Ser. Fyz.-Mat. Navuk 2(1990)111–116 (in Russian).
A.W.J. Kolen, A.H.G. Rinnooy Kan, C.P.M. van Hoesel and A.P.M. Wagelmans, Sensitivity analysis of list scheduling algorithms, Discrete Appl. Math. 55(1994)145–162.
S.A. Kravchenko, Yu.N. Sotskov and F. Werner, Optimal schedules with infinitely large stability radius, Optimization 33(1995)271–280.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, in: Logistics of Production and Inventory, Handbook in Operations Research and Management Science 4, eds. G.C. Graves, A.H.G. Rinnooy Kan and P.H. Zipkin, North-Holland, Amsterdam, 1993, pp. 445–522.
V.K. Leontev, The stability of the Traveling Salesman Problem, U.S.S.R. Comput. Maths. Math. Phys. 15, No.5(1975)199–213.
V.K. Leontev, Stability in combinatorial choice problems, Soviet Math. Dokl. 17(1976)635–638.
M. Libura, Sensitivity analysis for minimum Hamiltonian path and Traveling Salesman Problems, Discrete Appl. Math. 30(1991)197–211.
M. Libura, E.S. van der Poort, G. Sierksma and J.A.A. van der Veen, Sensitivity analysis based on k-best solutions of the Traveling Salesman Problem, Research Report 96A14, University of Groningen, The Netherlands, 1996, 27 pages.
M. Pinedo, Scheduling, Theory, Algorithms, and Systems, Prentice-Hall, Englewood Cliffs, 1995.
R. Ramaswamy and N. Chakravarti, Complexity of determining exact tolerances for min-sum and min-max combinatorial optimization problems, Working Paper WPS-247/95, Indian Institute of Management, Calcutta, India, 1995, 34 pages.
B. Roy and B. Sussmann, Problèmes d'ordonnancement avec contraints disjunctives, SEMA, Note DS, No. 9 bis Montrauge, 1964.
Yu.N. Sotskov, The stability of high-speed optimal schedules, U.S.S.R. Comput. Maths. Math. Phys. 29, No.3(1989)57–63.
Yu.N. Sotskov, Stability of an optimal schedule, European J. Oper. Res. 55(1991)91–102.
Yu.N. Sotskov, The stability of the approximate Boolean minimization of a linear form, Comput. Maths. Math. Phys. 33, No.5(1993)699–707.
Yu.N. Sotskov, V.K. Leontev and E.N. Gordeev, Some concepts of stability analysis in combinatorial optimization, Discrete Appl. Math. 58(1995)169–190.
Yu.N. Sotskov, N.Y. Sotskova and F. Werner, Stability of an optimal schedule in a job shop, OMEGA (1997), to appear.
B. Sussmann, Scheduling problems with interval disjunctions, Z. Oper. Res. 16(1972)165–178.
V.S. Tanaev, Yu.N. Sotskov and V.A. Strusevich, Scheduling Theory, Multi-Stage Systems, Kluwer Academic, 1994.
R.E. Tarjan, Sensitivity analysis of minimum spanning trees and shortest path trees, Inform. Processing Letters 14(1982)30–33.
C.P.M. van Hoesel and A.P.M. Wagelmans, On the complexity of postoptimality analysis of 0/1 programs, Report 9167 A, Econometric Institute, Erasmus University Rotterdam, Rotterdam, The Netherlands, 1991, 18 pages.
R.E. Wendell, The tolerance approach to sensitivity analysis in linear programming, Management Sci. 31(1985)564–578.
Rights and permissions
About this article
Cite this article
Sotskov, Y.N., Wagelmans, A.P. & Werner, F. On the calculation of the stability radiusof an optimal or an approximate schedule. Annals of Operations Research 83, 213–252 (1998). https://doi.org/10.1023/A:1018960030420
Issue Date:
DOI: https://doi.org/10.1023/A:1018960030420