Near-optimal dynamic task scheduling of precedence constrained coarse-grained tasks onto a computational grid
Noriyuki Fujimoto, Kenichi Hagihara · 2004
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. 1