A 2-Approximation Algorithm for Scheduling Independent Tasks onto a Uniform Parallel Machine and its Extension to a Computational Grid

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 (0 < epsiv les 1) which runs in exponential in (1/epsiv) time and 2-approximation algorithm based on LP-rounding technique which runs in O((mn)^3.5L²) 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