Approximation Algorithms for Scheduling Malleable Tasks Under Precedence Constraints
Approximation Algorithms for Scheduling Malleable Tasks Under Precedence Constraints
复制标题
DOI：
10.1142/s0129054102001308
复制
发表时间：
2001-08
期刊：
影响因子：
--
通讯作者：
Renaud Lepère;D. Trystram;G. Woeginger
中科院分区：
文献类型：
--
作者：
Renaud Lepère;D. Trystram;G. Woeginger
这项工作提出了用于调度受优先约束的并行应用任务的近似算法。所考虑的任务是可塑的，这意味着它们可以在不同数量的处理器上并行执行。所考虑的目标标准是完工时间，即最大的任务完成时间。我们证明了这个调度问题与其一个子问题（分配问题）之间的密切关系。通过利用这种关系，我们针对串并行优先约束的特殊情况以及有界宽度优先约束的特殊情况，设计了一个多项式时间近似算法，其性能保证可以任意接近(3 + √5)/2 ≅ 2.61803。这些特殊情况涵盖了树状结构优先约束的重要情形。对于具有任意优先约束的一般情况，我们给出了一个性能保证为3 + √5 ≅ 5.23606的多项式时间近似算法。
This work presents approximation algorithms for scheduling the tasks of a parallel application that are subject to precedence constraints. The considered tasks are malleable which means that they may be executed on a varying number of processors in parallel. The considered objective criterion is the makespan, i.e., the largest task completion time. We demonstrate a close relationship between this scheduling problem and one of its subproblems, the allotment problem. By exploiting this relationship, we design a polynomial time approximation algorithm with performance guarantee arbitrarily close to (3 + √5)/2 ≅ 2:61803 for the special case of series parallel precedence constraints and for the special case of precedence constraints of bounded width. These special cases cover the important situation of tree structured precedence constraints. For the general case with arbitrary precedence constraints, we give a polynomial time approximation algorithm with performance guarantee 3 + √5 ≅ 5:23606.