TIGHTER BOUND FOR MULTIFIT SCHEDULING ON UNIFORM PROCESSORS

被引:11
作者
CHEN, B
机构
[1] Institute of Applied Mathematics, Academia Sinica, Beijing
关键词
BIN PACKING; MULTIPROCESSOR SCHEDULING; HEURISTIC ALGORITHMS; UNIFORM PROCESSORS; WORST-CASE ANALYSIS; PERFORMANCE RATIO;
D O I
10.1016/0166-218X(91)90053-Y
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We examine one of the basic, well studied problem of scheduling theory, that of nonpreemptive assignment of independent tasks on m parallel processors with the objective of minimizing the makespan. Because this problem is NP-complete and apparently intractable in general, much effort has been directed toward devising fast algorithms which find near optimal schedules. Two well-known heuristic algorithms LPT (largest processing time first) and MULTIFIT, shortly MF, find schedules having makespans within 4/3, 13/11, respectively, of the minimum possible makespan, when the m parallel processors are identical. If they are uniform, then the best worst-case performance ratio bounds we know are 1.583, 1.40, respectively. In this paper we tighten the bound to 1.382 for MF algorithm for the uniform-processor system. On the basis of some of our general results and other investigations, we conjecture that the bound could be tightened further to 1.366.
引用
收藏
页码:227 / 260
页数:34
相关论文
共 7 条