Компактная MILP-модель для планирования многостадийных графов вычислений с однородными зависимостями в облаке
Журнал: Программные системы: теория и приложения @programmnye-sistemy
Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем
Статья в выпуске: 3 (72) т.17, 2026 года.
Бесплатный доступ
В статье рассматривается задача планирования ориентированных ациклических графов (DAG) вычислительных задач в облачной среде с целью минимизации длительности расписания или стоимости выполнения. Важным направлением исследований, связанных с решением сложных задач планирования, является разработка моделей смешанно-целочисленного линейного программирования (MILP), которые могут использоваться с точными решателями или служить основой для построения линейных релаксаций. Существующие MILP-модели для планирования DAG в облаке содержат большое число переменных и ограничений и известны как чрезвычайно трудные для решения. Хотя в общем случае улучить такие модели сложно, графы, встречающиеся на практике, часто обладают выраженными структурными свойствами, которые можно использовать для построения более эффективных моделей. В работе такие свойства используются для разработки более компактной и лучше поддающейся решению MILP-модели для графов, состоящих из нескольких стадий (слоёв) с однородными зависимостями по данным. Преимущества предложенной модели демонстрируются с помощью вычислительных экспериментов.
Короткий адрес: https://sciup.org/143186357
IDS: 143186357 | УДК: 519.687.1:004.75 | DOI: 10.25209/2079-3316-2026-17-3-275-314
Compact MILP Model for Scheduling Multi-Stage DAGs with Homogeneous Dependencies in the Cloud
In this paper, we consider the problem of scheduling directed acyclic graphs (DAGs) of computational tasks in the cloud to minimize makespan or execution cost. An important part of research on solving challenging scheduling problems is designing mixed-integer linear programming models in order to use them with an exact solver, or as a source of linear programming relaxations. The existing MILP models for DAG scheduling in the cloud have a large number of variables and constraints, and are known to be notoriously hard to solve. While in general these models are hard to improve, DAGs encountered in practice often have remarkable structural properties that may be exploited to design better models. We capitalize on such properties to devise a more compact and solvable MILP model for DAGs consisting of multiple stages (layers) with homogeneous data dependencies. The advantages of the proposed model are demonstrated by computational experiments.
