Меню
Публикации
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
Главный редактор
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2025-25-1-106-113
УДК 65.012.122
Планирование распределенных вычислений в недетерминированных системах
Читать статью полностью
Язык статьи - русский
Ссылка для цитирования:
Аннотация
Ссылка для цитирования:
Колесов Н.В., Литуненко Е.Г., Толмачева М.В., Тюльников В.С. Планирование распределенных вычислений в недетерминированных системах // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 1. С. 106–113. doi: 10.17586/2226-1494-2025-25-1-106-113
Аннотация
Введение. Планирование вычислений занимает важное место в процессе проектирования распределенных систем обработки информации и управления. Эффективные алгоритмы планирования позволяют находить технические решения, адекватные существующим ограничениям. Это становится особенно актуально для вычислителей, размещенных на автономных носителях, таких как беспилотные летательные аппараты, необитаемые подводные аппараты и другие подвижные объекты. В работе предложены и исследованы алгоритмы планирования заданий для распределенной вычислительной недетерминированной системы в случае, когда время выполнения заданий известно неточно и задано в виде временных интервалов. Метод. Решение поставленной задачи достигается путем сведения ее к известной задаче flow shop планирования с последующим применением формализма разрешимых классов распределенных вычислительных систем. Основные результаты. Предложены два алгоритма планирования заданий для недетерминированной распределенной вычислительной системы. Алгоритмы допускают отсутствие изоморфизмов между графами заданий и графом межпроцессорных связей. В этом случае невозможно применение известных алгоритмов flow shop планирования. Алгоритмы предполагают предварительное приведение рассматриваемой системы к требуемому виду и базируются на положениях интервального анализа и понятии разрешимого класса распределенных вычислительных систем. Критерием оптимальности предложенных алгоритмов служит минимум среднего времени пребывания задания в системе. Дополнительно для второго алгоритма используется критерий минимума максимального отклонения от заданных директивных сроков. Для введенных разрешимых классов систем для обоих критериев сформулированы оптимальные алгоритмы планирования полиномиальной сложности. Обсуждение. Предложенные решения могут быть применены при планировании вычислений в распределенных вычислительных системах при неточно известных длительностях решаемых задач, в частности, при планировании экономических процессов.
Ключевые слова: планирование вычислений, распределенная вычислительная система реального времени, flow shop планирование, разрешимый класс систем, время пребывания задания в системе, директивный срок
Список литературы
Список литературы
- 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
- Малашенко Ю.Е., Назарова И.А. Управление ресурсоемкими разнородными вычислительными заданиями с директивными сроками окончания // Известия РАН. Теория и системы управления. 2012. N 5. С. 15–22.
- Колесов Н.В., Толмачева М.В., Юхта П.В. Системы реального времени. Планирование, анализ, диагностирование // СПб.: ОАО "Концерн "ЦНИИ "Электроприбор", 2014. 180 с.
- 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.
- Глонина А.Б., Балашов В.В. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. 2018. Т. 25. N 2. С. 174–192. https://doi.org/10.18255/1818-1015-2018-2-174-192
- 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.
- 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.
- Грузликов А.М., Колесов Н.В., Литуненко Е.Г., Скородумов Ю.М. Маршрутизация в сетях автономных необитаемых подводных аппаратов // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21. N 6. С. 984–990. https://doi.org/10.17586/2226-1494-2021-21-6-984-990
- Колесов Н.В., Литуненко Е.Г., Скородумов Ю.М., Толмачева М.В. Планирование заданий в распределенной вычислительной системе на кристалле с минимизацией потребляемой мощности // Научно-технический вестник информационных технологий, механики и оптики. 2023. Т. 23. N 5. С. 1001–1008. https://doi.org/10.17586/2226-1494-2023-23-5-1001-1008
- Жолен Л., Кифер М., Дидри О., Вальтер Э. Прикладной интервальный анализ: с примерами по оцениванию параметров и состояний, робастному управлению и робототехнике. Москва; Ижевск: Институт компьютерных исследований, 2005. 467 с.
- Brucker P. Scheduling Algorithms. Springer, 2007. 371 p.
- Лазарев А.А. Метрики в задачах теории расписаний // Математическая теория управления и ее приложения. 15-я мультиконференция по проблемам управления. СПб, 2022. C.146–14.
- Белоусов Ф.А., Неволин И.В., Хачатрян Н.К. Моделирование и оптимизация планов грузовых железнодорожных перевозок, выполняемых транспортным оператором // Бизнес-информатика. 2020. Т. 14. N 2. С. 21–35. https://doi.org/10.17323/2587-814X.2020.2.21.35
