Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем

Научная статья

Компактная MILP-модель для планирования многостадийных графов вычислений с однородными зависимостями в облаке

Юрий Дмитриевич Семенов¹, Олег Викторович Сухорослов²

1	Национальный исследовательский университет «Высшая школа экономики»
2	Институт проблем передачи информации им. А.А. Харкевича Российской академии наук
1	ydsemenov@hse.ru

Аннотация.
В статье рассматривается задача планирования ориентированных ациклических графов (DAG) вычислительных задач в облачной среде с целью минимизации длительности расписания или стоимости выполнения. Важным направлением исследований, связанных с решением сложных задач планирования, является разработка моделей смешанно-целочисленного линейного программирования (MILP), которые могут использоваться с точными решателями или служить основой для построения линейных релаксаций. Существующие MILP-модели для планирования DAG в облаке содержат большое число переменных и ограничений и известны как чрезвычайно трудные для решения. Хотя в общем случае улучить такие модели сложно, графы, встречающиеся на практике, часто обладают выраженными структурными свойствами, которые можно использовать для построения более эффективных моделей.
В работе такие свойства используются для разработки более компактной и лучше поддающейся решению MILP-модели для графов, состоящих из нескольких стадий (слоёв) с однородными зависимостями по данным. Преимущества предложенной модели демонстрируются с помощью вычислительных экспериментов.
(Связанные тексты статьи на английском и на русском языках).

Ключевые слова: планирование графов вычислений, облачные вычисления, оптимизационное моделирование, смешанно-целочисленное линейное программирование

Благодарности: Работа выполнена в рамках государственного задания ИППИ РАН, утвержденного Минобрнауки России.

Для цитирования: Семенов Ю. Д., Сухорослов О. В. Компактная MILP-модель для планирования многостадийных графов вычислений с однородными зависимостями в облаке // Программные системы: теория и приложения. 2026. Т. 17. № 3. С. 275–314. (Англ., Рус.). https://psta.psiras.ru/2026/3_275-314.

Полный текст двуязычной статьи (PDF): https://psta.psiras.ru/read/psta2026_3_275-314.pdf (клик по флажку в верхнем колонитуле переключит язык страницы).

Русскоязычная часть оригинальной двуязычной статьи (PDF): https://psta.psiras.ru/read/psta2026_3_275-314-ru.pdf.

Статья поступила в редакцию 29.05.2026; одобрена после рецензирования 29.05.2026; принята к публикации 28.07.2026; опубликована онлайн 21.09.2026.