Task graph scheduling using timed automata
Task graph scheduling using timed automata
复制标题
DOI：
10.1109/ipdps.2003.1213431
复制
发表时间：
2003-04
期刊：
影响因子：
--
通讯作者：
Yasmina Abdeddaïm;Abdelkarim Kerbaa;O. Maler
中科院分区：
文献类型：
--
作者：
Yasmina Abdeddaïm;Abdelkarim Kerbaa;O. Maler
在本文中，我们开发了一种方法来处理并行机器上计划部分订购任务的问题。我们的框架基于定时自动机模型，该模型最初用于验证实时程序和数字电路，并且最近适用于解决时间优势的调度问题。在此框架中，调度问题允许状态空间表示形式，最佳时间表对应于定时自动机中的最短路径。我们检查了我们对众多基准测试的实现，并显示如何轻松地将发布时间和截止日期合并到模型中。
In this paper we develop a methodology for treating the problem of scheduling partially-ordered tasks on parallel machines. Our framework is based on the timed automaton model, originally developed for verification of real-time programs and digital circuits and more recently adapted for solving time-optimal scheduling problems. In this framework, the scheduling problem admits a state-space representation and an optimal schedule corresponds to a shortest path in the timed automaton. We check our implementation on numerous benchmarks and show how release times and deadlines can be easily incorporated into the model.