Homepage Program Systems: Theory and Applications Русская версия
ISSN 2079-3316 Bilingual online scientific Online scientific journal of the Ailamazyan Program System Institute of the Ailamazyan PSI of PSI of Russian Academy of Science of RAS 12+ 
Volume 17 (2026) . Issue 3 (72) . Paper No. 8 (518)

Hardware and software for distributed and supercomputer systems

Research Article
DOIDigital Object Identifier 10.25209/2079-3316-2026-17-3-275-314

Compact MILP Model for Scheduling Multi-Stage DAGs with Homogeneous Dependencies in the Cloud

Yury Dmitrievich Semenov1Correspondent author, Oleg Viktirovich Sukhoroslov2

1HSE University, Moscow, Russia
2Institute for Information Transmission Problems of the Russian Academy of Sciences, Moscow, Russia
1 Yury Dmitrievich Semenov — Correspondent author ydsemenov@hse.ru

Abstract. 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. (Linked article texts in English and in Russian).

Keywords: DAG scheduling, cloud computing, mathematical modeling, mixed-integer linear programming

MSC-20202020 Mathematics Subject Classification 68M20; 90C11,90C05MSC-2020 68-XX: Computer science MSC-2020 68Mxx: Computer system organization MSC-2020 68M20: Performance evaluation, queueing, and scheduling in the context of computer systems MSC-2020 90-XX: Operations research, mathematical programming MSC-2020 90Cxx: Mathematical programming MSC-2020 90C11: Mixed integer programming MSC-2020 90C05: Linear programming

Acknowledgments: The research was carried out within the state assignment of Ministry of Science and Higher Education of the Russian Federation for IITP RAS.

For citation: Yury D. Semenov, Oleg V. Sukhoroslov. Compact MILP Model for Scheduling Multi-Stage DAGs with Homogeneous Dependencies in the Cloud. Program Systems: Theory and Applications, 2026, 17:3, pp. 275–314. (in Engl. In Russ.). https://psta.psiras.ru/2026/3_275-314.

Full text of bilingual article (PDF): https://psta.psiras.ru/read/psta2026_3_275-314.pdf (Clicking on the flag in the header switches the page language).

The article was submitted 29.05.2026; approved after reviewing 29.05.2026; accepted for publication 28.07.2026; published online 21.09.2026.

© Semenov Y. D., Sukhoroslov O. V.
2026
Editorial address: Ailamazyan Program Systems Institute of the Russian Academy of Sciences, Peter the First Street 4«a», Veskovo village, Pereslavl area, Yaroslavl region, 152021 Russia;   Website:  http://psta.psiras.ru Phone: +7(4852) 695-228;   E-mail: ;   License: CC-BY-4.0License text on the Creative Commons site
© Ailamazyan Program System Institute of Russian Academy of Science (site design) 2010–2026