论文标题
定价定时自动机和定时的马尔可夫决策过程接近最佳的任务图计划
Near Optimal Task Graph Scheduling with Priced Timed Automata and Priced Timed Markov Decision Processes
论文作者
论文摘要
任务图调度是计算机科学中的一个相关问题，应用于不同的现实世界领域。任务图调度遭受组合爆炸的影响，因此找到最佳调度程序是一个艰巨的任务。 在本文中，我们提出了一种用于计算任务图的近乎最佳预先抢先和非首选调度程序的方法。任务图调度问题通过价格定时自动机（PTA）和定价的马尔可夫决策过程（PTMDP）中的最快路径降低到位置可及性。此外，我们探讨了使用链条减少查找时间表的计算时间的效果。 我们已经在Uppaal Cora和Uppaal Stratego中实施了模型。我们进行了详尽的实验评估，在其中将最终的时间表与最有名的状态工具的时间表进行比较。我们的大量结果表明，我们的时间表短于或等于最著名的时间表。
Task graph scheduling is a relevant problem in computer science with application to diverse real world domains. Task graph scheduling suffers from a combinatorial explosion and thus finding optimal schedulers is a difficult task. In this paper we present a methodology for computing near-optimal preemptive and non-preemptive schedulers for task graphs. The task graph scheduling problem is reduced to location reachability via the fastest path in Priced Timed Automata (PTA) and Priced Timed Markov Decision Processes (PTMDP). Additionally, we explore the effect of using chains to reduce the computation time for finding schedules. We have implemented our models in UPPAAL CORA and UPPAAL STRATEGO. We conduct an exhaustive experimental evaluation where we compare our resulting schedules with the best-known schedules of a state of the art tool. A significant number of our resulting schedules are shown to be shorter than or equal to the best-known schedules.
