Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid

The most common objective function of task scheduling problems is makespan. However, on a computational grid, the 2nd optimal makespan may be much longer than the optimal makespan because the speed of each processor of a grid varies over time. So, if the performance measure is makespan, there is no approximation algorithm in general for scheduling onto a grid. In contrast, recently the authors proposed the computing power consumed by a schedule as a criterion of the schedule. For the criterion, this Ä Ô Ò ¡Ñ ÐÓ� � Ñ paper gives a Ò-approximation algorithm for scheduling precedence constrained coarsegrained tasks with the same length onto a grid where Ò is the number of tasks, Ñ is the number of processors, and Ä Ô Ò is the length of the critical path of the task graph. The proposed algorithm does not use any prediction information on the performance of underlying resources. Ä Ô Ò is usually a sublinear function of Ò. So, the above performance guarantee converges to one as Ò grows. This result implies a non-trivial result that the computing power consumed by an application on a grid can be limited within Ä Ô Ò ¡Ñ ÐÓ� � Ñ Ò times that required by an optimal schedule in such a case.