informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-855Research ArticleАВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯCOMPUTER AIDED DESIGNИССЛЕДОВАНИЕ УСТОЙЧИВОСТИ ОПТИМАЛЬНЫХ РАСПИСАНИЙСотсковЮ. Н.Объединенный институт проблем информатики НАН БеларусиBelarus20041403201904(04)6575Copyright © Сотсков Ю.Н., 20192019Сотсков Ю.Н.Сотсков Ю.Н.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/855ReferencesТанаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. – М.: Наука, 1989. – 328 c.Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. – М.: Наука, 1989. – 328 c.Сотсков Ю.Н., Сотскова Н.Ю. Теория расписаний. Системы с неопределенными числовыми параметрами. – Мн: ОИПИ НАН Беларуси, 2004. – 290 c.Сотсков Ю.Н., Сотскова Н.Ю. Теория расписаний. Системы с неопределенными числовыми параметрами. – Мн: ОИПИ НАН Беларуси, 2004. – 290 c.Алюшкевич В.Б., Сотсков Ю.Н. Устойчивость в задачах календарного планирова-ния // Известия АН БССР. Сер. физ.-мат. наук. – 1989. – № 3. – С. 102-107.Алюшкевич В.Б., Сотсков Ю.Н. Устойчивость в задачах календарного планирова-ния // Известия АН БССР. Сер. физ.-мат. наук. – 1989. – № 3. – С. 102-107.Сотсков Ю.Н. Устойчивость оптимального расписания выполнения множества операций // Известия АН БССР. Сер. физ.-мат. наук. – 1988. – № 6. – С. 99-104.Сотсков Ю.Н. Устойчивость оптимального расписания выполнения множества операций // Известия АН БССР. Сер. физ.-мат. наук. – 1988. – № 6. – С. 99-104.Сотсков Ю.Н., Алюшкевич В.Б. Устойчивость оптимальной ориентации ребер смешанного графа // Доклады НАН Беларуси. – 1988. – Т. 32. – № 2. – C. 108-111.Сотсков Ю.Н., Алюшкевич В.Б. Устойчивость оптимальной ориентации ребер смешанного графа // Доклады НАН Беларуси. – 1988. – Т. 32. – № 2. – C. 108-111.Сотсков Ю.Н. Использование устойчивости оптимальных расписаний для синтеза информационно-вычислительных сетей // Автоматика и вычислительная техника. – 1990. – № 3. – C. 12-19.Сотсков Ю.Н. Использование устойчивости оптимальных расписаний для синтеза информационно-вычислительных сетей // Автоматика и вычислительная техника. – 1990. – № 3. – C. 12-19.Sotskov Yu.N. Stability of an optimal schedule // European Journal of Operational Re-search. – 1991. – V. 55. – P. 91-102.Sotskov Yu.N. Stability of an optimal schedule // European Journal of Operational Re-search. – 1991. – V. 55. – P. 91-102.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.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.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.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.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.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.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.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.Мельников О.И. Устойчивость оптимального расписания задачи Беллмана-Джонсона // Известия АН БССР. Сер. физ.-мат. наук. – 1978. – № 6. – С. 99-101.Мельников О.И. Устойчивость оптимального расписания задачи Беллмана-Джонсона // Известия АН БССР. Сер. физ.-мат. наук. – 1978. – № 6. – С. 99-101.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.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.Сотсков Ю.Н., Шилак А.Н. Минимизация сетевой модели при заданных границах допустимых значений длительностей операций // Известия АН БССР. Сер. физ.-мат. наук. – 2004. – № 6. – С. 99-104.Сотсков Ю.Н., Шилак А.Н. Минимизация сетевой модели при заданных границах допустимых значений длительностей операций // Известия АН БССР. Сер. физ.-мат. наук. – 2004. – № 6. – С. 99-104.Сотскова Н.Ю., Танаев В.С. О реализации оптимального расписания в условиях неопределенности длительностей операций // Доклады НАН Беларуси. – 1998. – Т. 42. – № 5. – C. 8-12.Сотскова Н.Ю., Танаев В.С. О реализации оптимального расписания в условиях неопределенности длительностей операций // Доклады НАН Беларуси. – 1998. – Т. 42. – № 5. – C. 8-12.Кравченко С.A., Сотсков Ю.Н. Оптимальное по быстродействию расписание с бесконечным радиусом устойчивости // Известия АН БССР. Сер. физ.-мат. наук. – 1993. – №. 4. – С. 85-91.Кравченко С.A., Сотсков Ю.Н. Оптимальное по быстродействию расписание с бесконечным радиусом устойчивости // Известия АН БССР. Сер. физ.-мат. наук. – 1993. – №. 4. – С. 85-91.Kravchenko S.A., Sotskov Yu.N., Werner F. Optimal schedules with infinitely large stabi-lity radius // Optimization. – 1995. – V. 33. – Р. 271-280.Kravchenko S.A., Sotskov Yu.N., Werner F. Optimal schedules with infinitely large stabi-lity radius // Optimization. – 1995. – V. 33. – Р. 271-280.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.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.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.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.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.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.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.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.Ковалев М.Я., Сотсков Ю.Н., Устойчивость ε-приближенных решений булевых задач минимизации линейной формы // Известия АН БССР. Сер. физ.-мат. наук. – 1990. – № 2. – С. 111-116.Ковалев М.Я., Сотсков Ю.Н., Устойчивость ε-приближенных решений булевых задач минимизации линейной формы // Известия АН БССР. Сер. физ.-мат. наук. – 1990. – № 2. – С. 111-116.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.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.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.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.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.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.Леонтьев В.К. Устойчивость задачи коммивояжера // Журнал вычислительной математики и математической физики. – 1975. – Т. 15. – № 5. – C. 1293–1309.Леонтьев В.К. Устойчивость задачи коммивояжера // Журнал вычислительной математики и математической физики. – 1975. – Т. 15. – № 5. – C. 1293–1309.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.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.Гордеев Э.Н. Об устойчивости задач на узкие места // Журнал вычислительной математики и математической физики. – 1993. – T. 33. – № 9. – P. 1391-1402.Гордеев Э.Н. Об устойчивости задач на узкие места // Журнал вычислительной математики и математической физики. – 1993. – T. 33. – № 9. – P. 1391-1402.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.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.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.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.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.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.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.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.Chakravarti N., Wagelmans A.P.M. Calculation of stability radii for combinatorial optimization problems // Operations Research Letters. – 1998. – V. 23. – № 1. – P. 1-7.Chakravarti N., Wagelmans A.P.M. Calculation of stability radii for combinatorial optimization problems // Operations Research Letters. – 1998. – V. 23. – № 1. – P. 1-7.Blair C.E. Sensitivity analysis for knapsack problems: A negative results // Discrete Applied Mathematics. – 1998. – V. 81. – № 1–3. – P. 133-139.Blair C.E. Sensitivity analysis for knapsack problems: A negative results // Discrete Applied Mathematics. – 1998. – V. 81. – № 1–3. – P. 133-139.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.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.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.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.Gordeev E.N. Solution stability of the shortest path problem // Discrete Mathematics. – 1989. – V. 1. – № 3. – P. 45-56.Gordeev E.N. Solution stability of the shortest path problem // Discrete Mathematics. – 1989. – V. 1. – № 3. – P. 45-56.Van Hoesel S., Wagelmans A. On the complexity of postoptimality analysis of 0/1 programs // Discrete Applied Mathematics. – 1999. – V. 91. – P. 251-263.Van Hoesel S., Wagelmans A. On the complexity of postoptimality analysis of 0/1 programs // Discrete Applied Mathematics. – 1999. – V. 91. – P. 251-263.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.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.Libura M. Optimality conditions and sensitivity analysis for combinatorial optimization problems // Control and Cybernetics. – 1996. – V. 25. – № 6. – P. 1165-1180.Libura M. Optimality conditions and sensitivity analysis for combinatorial optimization problems // Control and Cybernetics. – 1996. – V. 25. – № 6. – P. 1165-1180.Van Hoesel S., Wagelmans A. Sensitivity analysis of the economic lot-sizing problem // Discrete Applied Mathematics. – 1993. – V. 45. – № 3. – P. 291-312.Van Hoesel S., Wagelmans A. Sensitivity analysis of the economic lot-sizing problem // Discrete Applied Mathematics. – 1993. – V. 45. – № 3. – P. 291-312.Емеличев В.А., Гирлих Э., Янушкевич О.А. Лексикографические оптимумы многокритериальной задачи // Дискретный анализ и исследование операций. – 1997. – T. 4. – № 2. – C. 3-14.Емеличев В.А., Гирлих Э., Янушкевич О.А. Лексикографические оптимумы многокритериальной задачи // Дискретный анализ и исследование операций. – 1997. – T. 4. – № 2. – C. 3-14.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.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.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.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.Wagelmans A.P.M. Sensitivity analysis in combinatorial optimization // PhD thesis. – Econometric Institute, Erasmus University. The Netherlands, 1990.Wagelmans A.P.M. Sensitivity analysis in combinatorial optimization // PhD thesis. – Econometric Institute, Erasmus University. The Netherlands, 1990.Wagner H.M. Global sensitivity analysis // Operations Research. – 1995. – V. 43. – P. 948-969.Wagner H.M. Global sensitivity analysis // Operations Research. – 1995. – V. 43. – P. 948-969.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.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.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.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.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.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.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.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.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.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.
The authors declare that there are no conflicts of interest present.