Stability of a schedule minimizing mean flow time
作者： H. Bräsel , Yu.N. Sotskov , F. Werner
DOI: 10.1016/S0895-7177(96)00163-X
关键词: Stability radius 、 Job shop scheduling 、 Scheduling (computing) 、 Disjunctive graph 、 Job shop 、 Mathematics 、 Mathematical optimization 、 Mean flow
摘要: This paper is devoted to the calculation of stability radius an optimal schedule for a general shop scheduling problem, where objective minimize mean flow time. The denotes largest quantity independent variations processing times operations such that problem remains optimal. We derive formulas calculating radius, and necessary sufficient conditions when it equal zero. Moreover, computational results on randomly generated job problems are discussed.
elsevier.com
sci-hub.se 参考文章(12)
V. A. Strusevich, Vi︠a︡cheslav Sergeevich Tanaev, I︠u︡. N. Sotskov, Scheduling Theory: Multi-Stage Systems ,(1994)
Yu.N. Sotskov, V.K. Leontev, E.N. Gordeev, Some concepts of stability analysis in combinatorial optimization Discrete Applied Mathematics. ,vol. 58, pp. 169- 190 ,(1995) , 10.1016/0166-218X(93)E0126-J
E.N. Gordeyev, V.K. Leont'ev, The complexity of the tabulation of trajectory problems Ussr Computational Mathematics and Mathematical Physics. ,vol. 25, pp. 199- 201 ,(1986) , 10.1016/0041-5553(85)90169-7
Y.N. Stoskov, Stability of an optimal schedule European Journal of Operational Research. ,vol. 55, pp. 91- 102 ,(1991) , 10.1016/0377-2217(91)90194-Z
Robert Endre Tarjan, Sensitivity analysis of minimum spanning trees and shortest path trees Information Processing Letters. ,vol. 14, pp. 30- 33 ,(1982) , 10.1016/0020-0190(82)90137-5
Marek Libura, Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems Discrete Applied Mathematics. ,vol. 30, pp. 197- 211 ,(1991) , 10.1016/0166-218X(91)90044-W
Yu.N. Sotskov, The stability of high-speed optimal schedules Ussr Computational Mathematics and Mathematical Physics. ,vol. 29, pp. 57- 63 ,(1990) , 10.1016/0041-5553(89)90147-X
S. A. Kravchenko, Yu.N. Sotskov, F. Werner, Optimal schedules with infinitely large stability radius Optimization. ,vol. 33, pp. 271- 280 ,(1995) , 10.1080/02331939508844080
A.W.J. Kolen, A.H.G. Rinnooy Kan, C.P.M. van Hoesel, A.P.M. Wagelmans, Sensitivity analysis of list scheduling heuristics Discrete Applied Mathematics. ,vol. 55, pp. 145- 162 ,(1994) , 10.1016/0166-218X(94)90005-1
Michael L. Pinedo, Scheduling: Theory, Algorithms, and Systems ,(1994)