Preview

Информатика

Расширенный поиск

ИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ ОПТИМАЛЬНЫХ РАСПИСАНИЙ

Аннотация

Перечислены основные результаты по исследованию устойчивости оптимальных расписаний относительно возможных вариаций числовых исходных данных. Рассматриваются многостадийные системы обслуживания, в которых технологические маршруты фиксированы. Основное внимание уделено вычислению радиуса устойчивости оптимального расписания. Приведен обзор различных подходов к анализу устойчивости решений задач дискретной оптимизации.

Об авторе

Ю. Н. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Беларусь


Список литературы

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.

Просмотров: 440


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)