Menu
Publications
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief
Nikiforov
Vladimir O.
D.Sc., Prof.
Partners
doi: 10.17586/2226-1494-2025-25-1-106-113
Scheduling distributed computations in non-deterministic systems
Read the full article
';
Article in Russian
For citation:
Abstract
For citation:
Kolesov N.V., Litunenko E.G., Tolmacheva M.V., Tiulnikov V.S. Scheduling distributed computations in non-deterministic systems. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2025, vol. 25, no. 1, pp. 106–113 (in Russian). doi: 10.17586/2226-1494-2025-25-1-106-113
Abstract
Computation scheduling is very important in the design of distributed information processing and control systems. Effective scheduling algorithms allow developer to find technical solutions that are adequate to the existing constraints. This is especially important for computers located on autonomous carriers, such as unmanned aerial vehicles, autonomous underwater vehicles, and other vehicles. Scheduling algorithms for tasks in the distributed non-deterministic computing system, when the task execution time is known inaccurately and described as time interval, are proposed and researched. The solution of the problem is achieved by reducing it to a known problem of flow shop scheduling with subsequent application of the formalism of solvable classes of distributed computing systems. Authors propose two algorithms for scheduling tasks for a non-deterministic distributed computing system. Algorithms allow the absence of isomorphisms between task graphs and the graph of interprocessor communications for the system, and the presence of many information outputs and branches between tasks. In these conditions, it is impossible to use known algorithms of flow shop scheduling. Proposed algorithms assume preliminary reduction of the considered system to the required form and base on the provisions of interval analysis and the concept of a solvable class of distributed computing systems. Optimality criterion for proposed algorithms is the criterion of minimum average time a task remains in the system. Additionally, the criterion of minimum of maximum deviation from directive terms is used. For the introduced solvable classes of systems, optimal scheduling algorithms of polynomial complexity are proposed. These algorithms allow us to schedule computations in real distributed computing systems when the system deviates from the canonical form and when the durations of the tasks are not precisely known. Proposed algorithms can be applied when scheduling computations in real distributed computing systems and solving tasks with not precisely known durations and also, for example, in scheduling economic processes.
Keywords: computation scheduling, distributed real-time computing system, (flow shop)-scheduling, solvable class of systems, task residence time in the system
References
References
- Toporkov V., Yemelyanov D.,Toporkova A. Coordinated global and private job-flow scheduling in grid virtual organizations. Simulation Modelling Practice and Theory, 2021, vol. 107, pp. 102228. https://doi.org/10.1016/j.simpat.2020.102228
- Malashenko Y.E., Nazarova I.A. Controlling computationally intensive heterogeneous computational tasks with directive deadlines. Journal of Computer and Systems Sciences International, 2012, vol. 51, no. 5, pp. 628–635. https://doi.org/10.1134/S1064230712050024
- Kolesov N.V., Tolmacheva M.V., Iukhta P.V. Real-time Systems. Planning, Analysis, Diagnostics. St. Petersburg, CSRI ELEKTROPRIBOR Publ., 2014, 180 p. (in Russian)
- Liu J.W.S. Real-Time Systems. Prentice Hall, 2000, 610 p.
- Cottet F., Delacroix J., Kaiser C., Mammeri Z. Scheduling in Real-Time Systems. J. Wiley, 2002, 288 p.
- Cheng A.M.K. Real-Time Systems: Scheduling, Analysis, and Verification. Wiley-Interscience, 2002, 552 p.
- Glonina A.B., Balashov V.V. On the correctness of Real-Time Modular Computer Systems Modeling with stopwatch automata networks. Automatic Control and Computer Sciences, 2018, vol. 52, no. 7, pp. 817-827. (in Russian). https://doi.org/10.3103/S0146411618070271
- Choudhari, S.D., Khanna R. Flow shop scheduling problem with loading and unloading time // International Journal of Mathematics Research, 2017, vol. 9, no. 1, pp. 13–26.
- Kurniawan D., Radja A.C., Suprayogi, Halim A.H. A Flow Shop Batch Scheduling and Operator Assignment Model to Minimise Actual Flow Time. Proc. of the Asia Pacific Industrial Engineering & Management Systems Conference, 2017, pp. 1–6.
- Gruzlikov A.M., Kolesov N.V., Litunenko E.G., Skorodumov Yu.M. Routing in networks of autonomous underwater vehicles. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2021, vol. 21, no. 6, pp. 984–990. (in Russian). https://doi.org/ 10.17586/2226-1494-2021-21-6-984-990
- Kolesov N.V., Litunenko E.G., Skorodumov Iu.M., Tolmacheva M.V. Job scheduling in a distributed computing system on a chip with power consumption minimization. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2023, vol. 23, no. 5, pp. 1001–1008. (in Russian). https://doi.org/10.17586/2226-1494-2023-23-5-1001-1008
- Jaulin L., Kieffer M., Didrit O, Walter É. Applied Interval Analysis With Examples in Parameter and State Estimation, Robust Control and Robotics. Springer, 2001, 379 p. https://doi.org/10.1007/978-1-4471-0249-6
- Brucker P. Scheduling Algorithms. Springer, 2007, 371 p.
- Lazarev A.A. Metrics for problem of scheduling theory // Mathematical Control Theory and Its Applications. 15th Multiconference on Control Problems. St. Petersburg, 2022, pp. 146–148. (in Russian)
- Belousov F.A., Nevolin I.V., Khachatryan N.K. Modeling and optimization of plans for railway freight transport performed by a transport operator. Business Informatics, 2020, vol. 14, no. 2, pp. 21-35. (in Russian). https://doi.org/10.17323/2587-814X.2020.2.21.35
