WORST-CASE PERFORMANCE EVALUATION ON MULTIPROCESSOR TASK SCHEDULING WITH RESOURCE AUGMENTATION
Abstract
We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m identical processors with resource augmentation, whose objective is to minimize the makespan. In this case, the approximation algorithms are given k (k ≥ 0) extra processors than the optimal off-line algorithm. For on-line algorithms, the Greedy algorithm and shelf algorithms are studied. For off-line algorithm, we consider the LPT (longest processing time) algorithm. Particularly, we prove that the schedule produced by the LPT algorithm is no longer than the optimal off-line algorithm if and only if k ≥ m - 2.
A preliminary version of this paper appeared in Proceedings of 2008 International Symposium on Performance Evaluation of Computer and Telecommunication Systems(SPECTS08). Research was supported by the State Key Development Program for Basic Research of China ("973 project", No. 2007CB310900), NSFC(10601048) and NSFC(11071215).
