ИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ ОПТИМАЛЬНЫХ РАСПИСАНИЙ
Аннотация
Перечислены основные результаты по исследованию устойчивости оптимальных расписаний относительно возможных вариаций числовых исходных данных. Рассматриваются многостадийные системы обслуживания, в которых технологические маршруты фиксированы. Основное внимание уделено вычислению радиуса устойчивости оптимального расписания. Приведен обзор различных подходов к анализу устойчивости решений задач дискретной оптимизации.
Список литературы
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.
Рецензия
Для цитирования:
Сотсков Ю.Н. ИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ ОПТИМАЛЬНЫХ РАСПИСАНИЙ. Информатика. 2004;(4(04)):65-75.
Просмотров: 536
ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)
ISSN 2617-6963 (Online)
Послать статью по эл. почте 