ИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ ОПТИМАЛЬНЫХ РАСПИСАНИЙ
Перечислены основные результаты по исследованию устойчивости оптимальных расписаний относительно возможных вариаций числовых исходных данных. Рассматриваются многостадийные системы обслуживания, в которых технологические маршруты фиксированы. Основное внимание уделено вычислению радиуса устойчивости оптимального расписания. Приведен обзор различных подходов к анализу устойчивости решений задач дискретной оптимизации.
1. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. – М.: Наука, 1989. – 328 c.
2. Сотсков Ю.Н., Сотскова Н.Ю. Теория расписаний. Системы с неопределенными числовыми параметрами. – Мн: ОИПИ НАН Беларуси, 2004. – 290 c.
3. Алюшкевич В.Б., Сотсков Ю.Н. Устойчивость в задачах календарного планирова-ния // Известия АН БССР. Сер. физ.-мат. наук. – 1989. – № 3. – С. 102-107.
4. Сотсков Ю.Н. Устойчивость оптимального расписания выполнения множества операций // Известия АН БССР. Сер. физ.-мат. наук. – 1988. – № 6. – С. 99-104.
5. Сотсков Ю.Н., Алюшкевич В.Б. Устойчивость оптимальной ориентации ребер смешанного графа // Доклады НАН Беларуси. – 1988. – Т. 32. – № 2. – C. 108-111.
6. Сотсков Ю.Н. Использование устойчивости оптимальных расписаний для синтеза информационно-вычислительных сетей // Автоматика и вычислительная техника. – 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. Мельников О.И. Устойчивость оптимального расписания задачи Беллмана-Джонсона // Известия АН БССР. Сер. физ.-мат. наук. – 1978. – № 6. – С. 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. Сотсков Ю.Н., Шилак А.Н. Минимизация сетевой модели при заданных границах допустимых значений длительностей операций // Известия АН БССР. Сер. физ.-мат. наук. – 2004. – № 6. – С. 99-104.
15. Сотскова Н.Ю., Танаев В.С. О реализации оптимального расписания в условиях неопределенности длительностей операций // Доклады НАН Беларуси. – 1998. – Т. 42. – № 5. – C. 8-12.
16. Кравченко С.A., Сотсков Ю.Н. Оптимальное по быстродействию расписание с бесконечным радиусом устойчивости // Известия АН БССР. Сер. физ.-мат. наук. – 1993. – №. 4. – С. 85-91.
17. Kravchenko S.A., Sotskov Yu.N., Werner F. Optimal schedules with infinitely large stabi-lity radius // Optimization. – 1995. – V. 33. – Р. 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. Ковалев М.Я., Сотсков Ю.Н., Устойчивость ε-приближенных решений булевых задач минимизации линейной формы // Известия АН БССР. Сер. физ.-мат. наук. – 1990. – № 2. – С. 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. Леонтьев В.К. Устойчивость задачи коммивояжера // Журнал вычислительной математики и математической физики. – 1975. – Т. 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. Гордеев Э.Н. Об устойчивости задач на узкие места // Журнал вычислительной математики и математической физики. – 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. Емеличев В.А., Гирлих Э., Янушкевич О.А. Лексикографические оптимумы многокритериальной задачи // Дискретный анализ и исследование операций. – 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.