A 2-Approximation Algorithm for Scheduling Independent Tasks onto a Uniform Parallel Machine and its Extension to a Computational Grid
Noriyuki Fujimoto, Kenichi Hagihara · 2006
First, this paper gives a very simple 2-approximation algorithm for scheduling n independent tasks onto a uniform parallel machine with m processors. Best known results so far are (1 + epsiv)-approximation algorithm (03.5L2) time where L is the bit length of the linear program. In contrast, the proposed algorithm runs in O(n log n + mn) time. Next, this paper proves that, if a criterion of a schedule is total computing power consumed by the schedule and accurate performance prediction is possible, the proposed algorithm is a 2-approximation algorithm also for a uniform parallel machine such that processor speed varies over time. Such a parallel machine corresponds to a so-called desktop grid