Informacionnye TehnologiiInformacionnye TehnologiiИнформационные технологии1684-6400New Technologies Publishing House70731510.17587/it.32.236-242Modeling and optimizationМоделирование и оптимизацияResearch ArticleApplication of computational graph to scheduling problems under uncertaintyПрименение вычислительного графа для решения задач планирования в условиях неопределенностиKnyazevaM. V.КнязеваМ. В.
Russian Federation

Cand. of Tech. Sc., Assistant Professor

канд. техн. наук, доц.

mknyazeva@sfedu.ruBozhenyukA. V.БоженюкА. В.
Russian Federation

Dr. of Tech. Sc., Professor

д-р техн. наук, проф.

avbozhenyuk@sfedu.ruRozenbergI. N.РозенбергИ. Н.
Russian Federation

Dr. of Tech. Sc., Professor

д-р техн. наук, проф.

avb@itt.net.ruSouthern Federal University, TaganrogЮжный федеральный университет, ТаганрогRussian University of Transport (MIIT)Российский университет транспорта (МИИТ)090520263252362420805202608052026Copyright ©; 2026, Informacionnye TehnologiiCopyright ©; 2026, Информационные технологии2026Informacionnye TehnologiiИнформационные технологииhttps://journals.eco-vector.com/1684-6400/article/view/707315

This paper considers the problem of deploying a computational graph under uncertainty for an example production scheduling problem with time intervals. An estimated level of demand for the product is given for each planning period, and the level of production during time interval t can be used to cover the demand, which may differ for different time periods. The approach proposed in the work allows developing a production program that minimizes the total cost of production, and satisfies demand fully and on time.

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

computational graphtime modelingoperation planninguncertaintyoptimizationdynamic planningschedulingrecursive relationsвычислительный графвременное моделированиепланирование операцийнеопределенностьоптимизациядинамическое планированиесетевое планированиерекурсивные отношенияМинистерство транспорта Российской ФедерацииMinistry of Transport of the Russian Federation103-00001-26-00This work has been supported by the Ministry of Transport of the Russian Federation under Project #103-00001-26-00 "Development and research of the methodology of intelligent geoinformation modeling of transport processes in conditions of incomplete information".Работа выполнена при поддержке Министерства транспорта Российской Федерации в рамках проекта № 103-00001-26-00 "Разработка и исследование методологии интеллектуального геоинформационного моделирования транспортных процессов в условиях неполноты информации".Brucker P., Drex A., Möhring R., Neumann K., Pesch E. Resource-constrained project scheduling: Notation, classification, models and methods, European Journal of Operational Research, 1999, vol. 112, no. 1, pp. 4—41, DOI: 10.1016/S0377-2217(98)00204-5.Brucker P., Drex A., Möhring R., Neumann K., Pesch E. Resource-constrained project scheduling: Notation, classification, models and methods // European Journal of Operational Research. 1999. Vol. 112, N. 1. P. 4—41. DOI: 10.1016/S0377-2217(98)00204-5.Brucker P., Knust S. Complex Scheduling, Berlin, Heidelberg, Springer-Verlag, 2012, DOI: 10.1007/978-3-642-23929-8.Brucker P., Knust S. Complex Scheduling. Berlin, Heidelberg: Springer-Verlag, 2012. DOI: 10.1007/978-3-642-23929-8.Orlin J. B. The complexity of dynamic/periodic languages and optimization problems, Massachusetts Institute of Technology, Sloan Working Papers, MIT Management Sloan School, 1985.Orlin J. B. The complexity of dynamic/periodic languages and optimization problems. Massachusetts Institute of Technology, Sloan Working Papers, MIT Management Sloan School, 1985.Tellache N. E. Н., Boudhar M. Flow shop scheduling problem with conflict graphs, Ann. Oper. Res., 2017, vol. 261, pp. 339—363, DOI: 10.1007/s10479-017-2560-x.Tellache N. E. Н., Boudhar M. Flow shop scheduling problem with conflict graphs // Ann. Oper. Res. 2018. Vol. 261, N. 1. P. 339—363. DOI: 10.1007/s10479-017-2560-x.Chen Y., Goebel R., Lin G., Su B., Zhang А. Open-shop scheduling for unit jobs under precedence constraints, Theor. Comput. Sci., 2020, vol. 803, pp. 144—151, DOI: 10.1016/j.tcs.2019.09.046.Chen Y., Goebel R., Lin G., Su В., Zhang А. Open-shop scheduling for unit jobs under precedence constraints // Theor. Comput. Sci. 2020. Vol. 803. P. 144—151. DOI: 10.1016/j.tcs.2019.09.046.Gao Y., Xie Z., Liu X., Zhou W., Yu X. Integrated scheduling algorithm based on the priority constraint table for complex products with tree structure, Advances in Mechanical Engineering, 2020, vol. 12, no. 12, pp. 1—15, DOI: 10.1177/1687814020985206.Gao Y., Xie Z., Liu X., Zhou W., Yu X. Integrated scheduling algorithm based on the priority constraint table for complex products with tree structure // Advances in Mechanical Engineering. 2020. Vol. 12, N. 12. P. 1—15. DOI: 10.1177/1687814020985206.Nilim A., El Ghaoui L. Robust Control of Markov Decision Processes with Uncertain Transition Matrices, Operations Research, 2005, vol. 53, no. 5, pp. 780—798, DOI: 10.1287/opre.1050.0216.Nilim A., El Ghaoui L. Robust Control of Markov Decision Processes with Uncertain Transition Matrices // Operations Research. 2005. Vol. 53, N. 5. P. 780—798. DOI: 10.1287/opre.1050.0216.Baldacci R., Bartolini E., Mingozzi А. An Exact Algorithm for the Pickup and Delivery Problem with Time Windows, Operations Research, 2011, vol. 59, no. 2, pp. 414—426, DOI: 10.1287/opre.1100.0881.Baldacci R., Bartolini E., Mingozzi А. An Exact Algorithm for the Pickup and Delivery Problem with Time Windows // Operations Research. 2011. Vol. 59, N. 2. P. 414—426. DOI: 10.1287/opre.1100.0881.Srour F. J., Agatz N., Oppen J. Strategies for Handling Temporal Uncertainty in Pickup and Delivery Problems with Time Windows, Transportation Science, 2016, vol. 52, no. 1, pp. 3—19, DOI: 10.1287/trsc.2015.0658.Srour F. J., Agatz N., Oppen J. Strategies for Handling Temporal Uncertainty in Pickup and Delivery Problems with Time Windows // Transportation Science. 2016. Vol. 52, N. 1. P. 3—19. DOI: 10.1287/trsc.2015.0658.Knyazeva M., Bozhenyuk A., Bozheniuk V. Unfolding Fuzzy Temporal Computational Graph for Project Scheduling Problem, Lecture Notes in Networks and Systems, 2021, vol. 307, pp. 615—622, DOI: 10.1007/978-3-030-85626-7_72.Knyazeva M., Bozhenyuk A., Bozheniuk V. Unfolding Fuzzy Temporal Computational Graph for Project Scheduling Problem // Lecture Notes in Networks and Systems. 2021. Vol. 307. P. 615—622. DOI: 10.1007/978-3-030-85626-7_72.Crochemore M., Gabbay Dov M. Reactive automata, Information and Computation, 2011, vol. 209, no. 4, pp. 692—704, DOI: 10.1016/j.ic.2011.01.002.Crochemore M., Gabbay Dov M. Reactive automata // Information and Computation. 2011. Vol. 209, N. 4. P. 692—704. DOI: 10.1016/j.ic.2011.01.002.Pankratieva V. Minimization of the number of states of a fuzzy automaton using interval pattern concepts, Intelligent systems. Theory and applications, 2020, vol. 24, no. 2, pp. 99—115.Pankratieva V. Minimization of the number of states of a fuzzy automaton using interval pattern concepts // Intelligent systems. Theory and applications. 2020. Vol. 24, N. 2. P. 99—115.Wagner Н. M. Principles of Operations Research with Applications to Managerial Decisions, Prentice-Hall international series in management, 1975.Wagner Н. M. Principles of Operations Research: With Applications to Managerial Decisions, Prentice-Hall international series in management, 1975.