Scheduling distributed computations in non-deterministic systems

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.

1. 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

2. 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

3. 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)

4. Liu J.W.S. Real-Time Systems. Prentice Hall, 2000, 610 p.

5. Cottet F., Delacroix J., Kaiser C., Mammeri Z. Scheduling in Real-Time Systems. J. Wiley, 2002, 288 p.

6. Cheng A.M.K. Real-Time Systems: Scheduling, Analysis, and Verification. Wiley-Interscience, 2002, 552 p.

7. 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

8. 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.

9. 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.

10. 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

11. 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

12. 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

13. Brucker P. Scheduling Algorithms. Springer, 2007, 371 p.

14. 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)

15. 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