期刊
ACM TRANSACTIONS ON ALGORITHMS
卷 2, 期 3, 页码 416-434出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1159892.1159899
关键词
Approximation algorithms; scheduling; malleable tasks; precedence constraints
资金
- EU Thematic Network APPOL II, Approximation and Online Algorithms for Optimization Problems [IST-2001-32007]
- EU [IST-2001-33135]
- DFG Graduiertenkolleg 357, Effiziente Algorithmen and Mehrskalenmethoden
- MITACS of Canada
- NSERC [DG 5-48923]
In this article, we study the problem of scheduling malleable tasks with precedence constraints. We are given m identical processors and n tasks. For each task the processing time is a function of the number of processors allotted to it. In addition, the tasks must be processed according to the precedence constraints. The goal is to minimize the makespan (maximum completion time) of the resulting schedule. The best previous approximation algorithm (that works in two phases) in Lepere et al. [2002b] has a ratio 3 + root 5 approximate to 5.236. We develop an improved approximation algorithm with a ratio at most 100/43 + 100(root 4349 - 7)/2451 approximate to 4.730598. We also show that our resulting ratio is asymptotically tight.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据