ИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ ОПТИМАЛЬНЫХ РАСПИСАНИЙ
Abstract
Перечислены основные результаты по исследованию устойчивости оптимальных расписаний относительно возможных вариаций числовых исходных данных. Рассматриваются многостадийные системы обслуживания, в которых технологические маршруты фиксированы. Основное внимание уделено вычислению радиуса устойчивости оптимального расписания. Приведен обзор различных подходов к анализу устойчивости решений задач дискретной оптимизации.
References
1. Tanaev V.S., Sotskov Yu.N., Strusevich V.A. Teoriya raspisanii. Mnogostadiinye sistemy. - M.: Nauka, 1989. - 328 c.
2. Sotskov Yu.N., Sotskova N.Yu. Teoriya raspisanii. Sistemy s neopredelennymi chislovymi parametrami. - Mn: OIPI NAN Belarusi, 2004. - 290 c.
3. Alyushkevich V.B., Sotskov Yu.N. Ustoichivost' v zadachakh kalendarnogo planirova-niya // Izvestiya AN BSSR. Ser. fiz.-mat. nauk. - 1989. - № 3. - S. 102-107.
4. Sotskov Yu.N. Ustoichivost' optimal'nogo raspisaniya vypolneniya mnozhestva operatsii // Izvestiya AN BSSR. Ser. fiz.-mat. nauk. - 1988. - № 6. - S. 99-104.
5. Sotskov Yu.N., Alyushkevich V.B. Ustoichivost' optimal'noi orientatsii reber smeshannogo grafa // Doklady NAN Belarusi. - 1988. - T. 32. - № 2. - C. 108-111.
6. Sotskov Yu.N. Ispol'zovanie ustoichivosti optimal'nykh raspisanii dlya sinteza informatsionno-vychislitel'nykh setei // Avtomatika i vychislitel'naya tekhnika. - 1990. - № 3. - C. 12-19.
7. Sotskov Yu.N. Stability of an optimal schedule // European Journal of Operational Re-search. - 1991. - V. 55. - P. 91-102.
8. Sotskov Yu.N. The stability of high-speed optimal schedules // U.S.S.R. Comput. Math. and Math. Phys. - 1989. - V. 29. - № 3. - P. 57-63.
9. Brasel H., Sotskov Yu.N., Werner F. Stability of a schedule minimizing mean flow time // Mathematical and Computer Modelling. - 1996. - V. 24. - № 10. - P. 39-53.
10. Optimal makespan schedule with given bounds of processing times / T.-C. Lai, Yu.N. Sotskov, N. Sotskova, F. Werner // Mathematical and Computer Modelling. - 1997. - V. 26. - № 3. - P. 67-86.
11. Sotskov Yu.N., Sotskova N., Werner F. Stability of an optimal schedule in a job shop // OMEGA - International Journal of Management Science. - 1997. - V. 25. - № 4. - P. 397-414.
12. Mel'nikov O.I. Ustoichivost' optimal'nogo raspisaniya zadachi Bellmana-Dzhonsona // Izvestiya AN BSSR. Ser. fiz.-mat. nauk. - 1978. - № 6. - S. 99-101.
13. Sotskova N. Optimal scheduling with uncertainty in the numerical data on the basis of a stability analysis. - Magdeburg: Faculty of Mathematics. Otto-von-Gericker-University, 2001. http: // diglib.uni-magdeburg.de/Dissertationen/2001/nadsotskova.pdf.
14. Sotskov Yu.N., Shilak A.N. Minimizatsiya setevoi modeli pri zadannykh granitsakh dopustimykh znachenii dlitel'nostei operatsii // Izvestiya AN BSSR. Ser. fiz.-mat. nauk. - 2004. - № 6. - S. 99-104.
15. Sotskova N.Yu., Tanaev V.S. O realizatsii optimal'nogo raspisaniya v usloviyakh neopredelennosti dlitel'nostei operatsii // Doklady NAN Belarusi. - 1998. - T. 42. - № 5. - C. 8-12.
16. Kravchenko S.A., Sotskov Yu.N. Optimal'noe po bystrodeistviyu raspisanie s beskonechnym radiusom ustoichivosti // Izvestiya AN BSSR. Ser. fiz.-mat. nauk. - 1993. - №. 4. - S. 85-91.
17. Kravchenko S.A., Sotskov Yu.N., Werner F. Optimal schedules with infinitely large stabi-lity radius // Optimization. - 1995. - V. 33. - R. 271-280.
18. Stability of Johnson's schedule with respect to limited machine availability / O. Braun, T.-C. Lai, G. Schmidt, Yu.N. Sotskov // International Journal of Production Research. - 2002. - V. 40. - № 17. - P. 4381-4400.
19. Sotskov Yu.N., Wagelmans A.P.M., Werner F. On the calculation of the stability radius of an optimal or an approximate schedule // Annals of Operations Research. - 1998. - V. 83. - P. 213-252.
20. Sotskov Yu.N., Tanaev V.S., Werner F. Stability radius of an optimal schedule: A survey and recent developments // Industrial Applications of Combinatorial Optimization. V. 16. - Boston: Kluwer Academic Publishers, 1998. - P. 72-108.
21. Mean flow time minimization with given bounds of processing times / T.-C. Lai, Yu.N. Sotskov, N. Sotskova, F. Werner // European Journal of Operational Research. - 2004. - V. 33. - № 159. - P. 558-573.
22. Kovalev M.Ya., Sotskov Yu.N., Ustoichivost' ε-priblizhennykh reshenii bulevykh zadach minimizatsii lineinoi formy // Izvestiya AN BSSR. Ser. fiz.-mat. nauk. - 1990. - № 2. - S. 111-116.
23. Sotskov Yu.N. The stability of the approximate Boolean minimization of a linear form // U.S.S.R. Comput. Math. and Math. Phys. - 1993. - V. 33. - № 5. - P. 699-707.
24. Sotskov Yu.N., Dolgui A., Portmann M.-C. Stability analysis of optimal balance for assembly line with fixed cycle time // European Journal of Operational Research. - 2004.
25. Sotskov Yu.N., Leontev V.K., Gordeev E.N. Some concepts of stability analysis in combinatorial optimization // Discrete Applied Mathematics. - 1995. - V. 58. - P. 169-190.
26. Leont'ev V.K. Ustoichivost' zadachi kommivoyazhera // Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki. - 1975. - T. 15. - № 5. - C. 1293-1309.
27. Gordeev E.N. Algorithms of polynomial complexity for computing the stability radius in two classes of trajectory problems // U.S.S.R. Comput. Maths. Math. Phys. - 1987. - V. 27. - № 4. - P. 14-20.
28. Gordeev E.N. Ob ustoichivosti zadach na uzkie mesta // Zhurnal vychislitel'noi matematiki i matematicheskoi fiziki. - 1993. - T. 33. - № 9. - P. 1391-1402.
29. Gordeev E.N., Leontev V.K., Sigal I.Ch. Computational algorithms for finding stability radius in choice problems // U.S.S.R. Comput. Maths. Math. Phys. - 1983. - V. 23. - № 4. - P. 128-132.
30. Stability of a vector problem of integer programming / V.A. Emelichev, E. Girlih, Yu.V. Nikulin, D.P. Podkopaev // Optimization. - 2002. - V. 51. - № 4. - P. 645-676.
31. Jones C.V. The stability of solution to the Euclidean traveling salesman problem. Part I, II: Experimental results // Technical report. - 1997. http://www.chesapeake2.com/cvj/tsp.
32. Libura M. On accuracy of solutions for discrete optimization problems with perturbed coefficients of the objective function // Annals of Operations Research. - 1999. - V. 86. - P. 53-62.
33. Chakravarti N., Wagelmans A.P.M. Calculation of stability radii for combinatorial optimization problems // Operations Research Letters. - 1998. - V. 23. - № 1. - P. 1-7.
34. Blair C.E. Sensitivity analysis for knapsack problems: A negative results // Discrete Applied Mathematics. - 1998. - V. 81. - № 1-3. - P. 133-139.
35. Woeginger G.J., Sensitivity analysis for knapsack problems: Another negative result // Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science. - 1999. - V. 92. - № 2-3. - P. 247-251.
36. Ramaswamy R., Chakravarti N. Complexity of determining exact tolerances for min-sum and min-max combinatorial optimization problems // Technical Report WPS-247/95. - Calcutta: Indian Institute of Management, 1995.
37. Gordeev E.N. Solution stability of the shortest path problem // Discrete Mathematics. - 1989. - V. 1. - № 3. - P. 45-56.
38. Van Hoesel S., Wagelmans A. On the complexity of postoptimality analysis of 0/1 programs // Discrete Applied Mathematics. - 1999. - V. 91. - P. 251-263.
39. Stability aspects of the traveling salesman problem based on k-best solutions / M. Libura, E.S. van der Poort, G. Sierksma, J.A.A. van der Veen // Discrete Applied Mathematics. - 1998. - V. 87. - P. 159-185.
40. Libura M. Optimality conditions and sensitivity analysis for combinatorial optimization problems // Control and Cybernetics. - 1996. - V. 25. - № 6. - P. 1165-1180.
41. Van Hoesel S., Wagelmans A. Sensitivity analysis of the economic lot-sizing problem // Discrete Applied Mathematics. - 1993. - V. 45. - № 3. - P. 291-312.
42. Emelichev V.A., Girlikh E., Yanushkevich O.A. Leksikograficheskie optimumy mnogokriterial'noi zadachi // Diskretnyi analiz i issledovanie operatsii. - 1997. - T. 4. - № 2. - C. 3-14.
43. Greenberg H.J. A bibliography for the development of an intelligent mathematical pro-gramming system // Annals of Operations Research. - 1996. - V. 65. - P. 55-90. http:// orcs.bus.okstate.edu/itorms.
44. Sensitivity analysis of list scheduling algorithms / A.W.H. Kolen, A.H.G. Rinnooy Kan, C.P.M. van Hoesel, A.P.M. Wagelmans // Discrete Applied Mathematics. - 1994. - V. 55. - P. 145-162.
45. Wagelmans A.P.M. Sensitivity analysis in combinatorial optimization // PhD thesis. - Econometric Institute, Erasmus University. The Netherlands, 1990.
46. Wagner H.M. Global sensitivity analysis // Operations Research. - 1995. - V. 43. - P. 948-969.
47. Kouvelis P., Daniels R.L., Vairaktarakis G. Robust scheduling of a two-machine flow shop with uncertain processing times // IIE Transactions. - 2000. - V. 32. - P. 421-432.
48. Brasel H., Harboth M., Tautenhahn T. On the hardness of the classical job shop problem // Annals of Operations Research. - 1999. - V. 92. - P. 265-279.
49. Brasel H., Harboth M., Tautenhahn T. On the set of solutions of the open shop problem // Annals of Operations Research. - 1999. - V. 92. - P. 241-263.
50. Leon V.J., Wu S.D., Storer R.H. Robustness measures and robust scheduling for job shops // IIE Transactions. - 1994. - V. 26. - P. 32-43.
51. Wu S.D., Byeon E.-S., Storer R.H. A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness // Operations Research. - 1999. - V. 47. - № 1. - P. 241-263.
Review
For citations:
. Informatics. 2004;(4(04)):65-75. (In Russ.)
Views: 538
ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)
ISSN 2617-6963 (Online)
Email this article 