论文标题
在两个处理器上安排深度二的UET-uct DAG
Scheduling UET-UCT DAGs of Depth Two on Two Processors
论文作者
论文摘要
给定的单元执行时间（UET）任务的任务形成了有向的无环图（DAG），弧与单位通信时间（UCT）延迟相关联。问题是安排两个处理器上的任务，以最大程度地减少MakePan。文献中的几种多项式算法是针对特殊类别的Digraphs提出的，但是在通常的情况下解决此问题的复杂性却是一个充满挑战的开放问题。我们在本文中提出了一种线性时间算法，以计算深度二的DAG类的最佳时间表。
Given unit execution time (UET) tasks whose precedence constraints form a directed acyclic graph (DAG), the arcs are associated with unit communication time (UCT) delays. The problem is to schedule the tasks on two processors in order to minimize the makespan. Several polynomial algorithms in the literature are proposed for special classes of digraphs, but the complexity of solving this problem in general case stills a challenging open question. We propose in this paper a linear time algorithm to compute an optimal schedule for the class of DAGs of depth two.
