On using priced timed automata to achieve optimal scheduling
On using priced timed automata to achieve optimal scheduling
复制标题
利用定价时间自动机实现最优调度
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
K. Subramani
中科院分区：
文献类型：
--
作者：
J. I. Rasmussen;K. Larsen;K. Subramani
在这篇文章中，我们描述了一种利用价格时间自动机来解决一般类型的能量最优任务图调度问题的方法。提出了一种有效的基于区域的最小代价可达性算法。此外，我们还展示了如何利用在价格时间自动机的符号最小代价可达性分析中遇到的线性规划的简单结构来显著提高当前算法的性能。这个思想植根于线性规划的对偶性，我们证明了每个遇到的线性规划都可以归结为最小费用流问题的一个实例的对偶问题。使用Uppaal的实验结果表明，性能提高了70%-80%。我们为调度问题提供了定价的时间自动机模型，并提供了实验结果，说明了与现有方法(如混合整数线性规划)相比，该方法具有潜在的竞争力。
In this paper, we describe an approach for solving the general class of energy-optimal task graph scheduling problems using priced timed automata. We provide an efficient zone-based algorithm for minimum-cost reachability. Furthermore, we show how the simple structure of the linear programs encountered during symbolic minimum-cost reachability analysis of priced timed automata can be exploited in order to substantially improve the performance of the current algorithm. The idea is rooted in duality of linear programs and we show that each encountered linear program can be reduced to the dual problem of an instance of the min-cost flow problem. Experimental results using Uppaal show a 70–80 percent performance gain. We provide priced timed automata models for the scheduling problems and provide experimental results illustrating the potential competitiveness of our approach compared to existing approaches such as mixed integer linear programming.