Scheduling UET-UCT Series-Parallel Graphs on Two Processors
Scheduling UET-UCT Series-Parallel Graphs on Two Processors
复制标题
在两个处理器上调度 UET-UCT 系列并行图
DOI：
10.1016/0304-3975(96)00035-7
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
E. Bampis
中科院分区：
文献类型：
--
作者：
L. Finta;Z. Liu;I. Milis;E. Bampis
研究了任务图在两台相同处理机上的调度问题。假设任务具有单位执行时间，并且弧线与单位通信时间延迟相关联。问题是将任务分配给两个处理器并调度它们的执行，以最小化完工时间。提出了一种计算一类串并图的最优调度的二次型算法，称为SP1图，它特别包括林内图和林外图。
The scheduling of task graphs on two identical processors is considered. It is assumed that tasks have unit-execution-time, and arcs are associated with unit-communication-time delays. The problem is to assign the tasks to the two processors and schedule their execution in order to minimize the makespan. A quadratic algorithm is proposed to compute an optimal schedule for a class of series-parallel graphs, called SP1 graphs, which includes in particular in-forests and out-forests.