Email this article 
Application of computational graph to scheduling problems under uncertainty
- Authors: Knyazeva M.V.1, Bozhenyuk A.V.1, Rozenberg I.N.2
-
Affiliations:
- Southern Federal University, Taganrog
- Russian University of Transport (MIIT)
- Issue: Vol 32, No 5 (2026)
- Pages: 236-242
- Section: Modeling and optimization
- Published: 09.05.2026
- URL: https://journals.eco-vector.com/1684-6400/article/view/707315
- DOI: https://doi.org/10.17587/it.32.236-242
- ID: 707315
Cite item
Open Access
Access granted
Abstract
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.
Full Text
About the authors
M. V. Knyazeva
Southern Federal University, Taganrog
Author for correspondence.
Email: mknyazeva@sfedu.ru
Cand. of Tech. Sc., Assistant Professor
Russian Federation, TaganrogA. V. Bozhenyuk
Southern Federal University, Taganrog
Email: avbozhenyuk@sfedu.ru
Dr. of Tech. Sc., Professor
Russian Federation, TaganrogI. N. Rozenberg
Russian University of Transport (MIIT)
Email: avb@itt.net.ru
Dr. of Tech. Sc., Professor
Russian Federation, MoscowReferences
- 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., 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Wagner Н. M. Principles of Operations Research with Applications to Managerial Decisions, Prentice-Hall international series in management, 1975.
Supplementary files
