Scholarlink

In this paper, we consider the problem of scheduling computational DAGs in the cloud, closely related to parallel machine scheduling with precedence constraints. While there exists a huge variety of heuristics and metaheuristics dealing with DAG scheduling, little work has been done with regard to the mathematical properties of the problem. We strive to close this gap by presenting results on the complexity and inapproximability of the cloud DAG scheduling problem and suggesting mixed-integer programming models.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

MIP Models and Complexity Results for DAG Scheduling in the Cloud

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Yury Semenov,
  • Oleg Sukhoroslov

摘要

In this paper, we consider the problem of scheduling computational DAGs in the cloud, closely related to parallel machine scheduling with precedence constraints. While there exists a huge variety of heuristics and metaheuristics dealing with DAG scheduling, little work has been done with regard to the mathematical properties of the problem. We strive to close this gap by presenting results on the complexity and inapproximability of the cloud DAG scheduling problem and suggesting mixed-integer programming models.