Планирование распределенных вычислений в недетерминированных системах

Введение. Планирование вычислений занимает важное место в процессе проектирования распределенных систем обработки информации и управления. Эффективные алгоритмы планирования позволяют находить технические решения, адекватные существующим ограничениям. Это становится особенно актуально для вычислителей, размещенных на автономных носителях, таких как беспилотные летательные аппараты, необитаемые подводные аппараты и другие подвижные объекты. В работе предложены и исследованы алгоритмы планирования заданий для распределенной вычислительной недетерминированной системы в случае, когда время выполнения заданий известно неточно и задано в виде временных интервалов. Метод. Решение поставленной задачи достигается путем сведения ее к известной задаче flow shop планирования с последующим применением формализма разрешимых классов распределенных вычислительных систем. Основные результаты. Предложены два алгоритма планирования заданий для недетерминированной распределенной вычислительной системы. Алгоритмы допускают отсутствие изоморфизмов между графами заданий и графом межпроцессорных связей. В этом случае невозможно применение известных алгоритмов flow shop планирования. Алгоритмы предполагают предварительное приведение рассматриваемой системы к требуемому виду и базируются на положениях интервального анализа и понятии разрешимого класса распределенных вычислительных систем. Критерием оптимальности предложенных алгоритмов служит минимум среднего времени пребывания задания в системе. Дополнительно для второго алгоритма используется критерий минимума максимального отклонения от заданных директивных сроков. Для введенных разрешимых классов систем для обоих критериев сформулированы оптимальные алгоритмы планирования полиномиальной сложности. Обсуждение. Предложенные решения могут быть применены при планировании вычислений в распределенных вычислительных системах при неточно известных длительностях решаемых задач, в частности, при планировании экономических процессов.

1. Toporkov V., Yemelyanov D.,Toporkova A. Coordinated global and private job-flow scheduling in grid virtual organizations // Simulation Modelling Practice and Theory. 2021. V. 107. P. 102228. https://doi.org/10.1016/j.simpat.2020.102228

2. Малашенко Ю.Е., Назарова И.А. Управление ресурсоемкими разнородными вычислительными заданиями с директивными сроками окончания // Известия РАН. Теория и системы управления. 2012. № 5. С. 15–22.

3. Колесов Н.В., Толмачева М.В., Юхта П.В. Системы реального времени. Планирование, анализ, диагностирование // СПб.: ОАО «Концерн «ЦНИИ «Электроприбор», 2014. 180 с.

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. Глонина А.Б., Балашов В.В. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. 2018. Т. 25. № 2. С. 174–192. https://doi.org/10.18255/1818-1015-2018-2-174-192

8. Choudhari, S.D., Khanna R. Flow shop scheduling problem with loading and unloading time // International Journal of Mathematics Research. 2017. V. 9. N 1. P. 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. P. 1–6.

10. Грузликов А.М., Колесов Н.В., Литуненко Е.Г., Скородумов Ю.М. Маршрутизация в сетях автономных необитаемых подводных аппаратов // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21. № 6. С. 984–990. https://doi.org/10.17586/2226-1494-2021-21-6-984-990

11. Колесов Н.В., Литуненко Е.Г., Скородумов Ю.М., Толмачева М.В. Планирование заданий в распределенной вычислительной системе на кристалле с минимизацией потребляемой мощности // Научно-технический вестник информационных технологий, механики и оптики. 2023. Т. 23. № 5. С. 1001–1008. https://doi.org/10.17586/2226-1494-2023-23-5-1001-1008

12. Жолен Л., Кифер М., Дидри О., Вальтер Э. Прикладной интервальный анализ: с примерами по оцениванию параметров и состояний, робастному управлению и робототехнике. Москва; Ижевск: Институт компьютерных исследований, 2005. 467 с.

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

14. Лазарев А.А. Метрики в задачах теории расписаний // Математическая теория управления и ее приложения. 15-я мультиконференция по проблемам управления. СПб, 2022. C.146–148.

15. Белоусов Ф.А., Неволин И.В., Хачатрян Н.К. Моделирование и оптимизация планов грузовых железнодорожных перевозок, выполняемых транспортным оператором // Бизнес-информатика. 2020. Т. 14. № 2. С. 21–35. https://doi.org/10.17323/2587-814X.2020.2.21.35