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 (1 + L{sub}(cp)(n)·m(log{sub}e(m-1)+1)/n)-approximation algorithm for scheduling precedence constrained coarsegrained tasks with the same length onto a grid where n is the number of tasks, m is the number of processors, and L{sub}(cp)(n) 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. L{sub}(cp) (n) is usually a sublinear function of n. So, the above performance guarantee converges to one as n grows. This result implies a non-trivial result that the computing power consumed by an application on a grid can be limited within (1 +L{sub}(cp)(n)·m(log{sub}e(m-1)+1/n)) time that required by an optimal schedule in such a case.