Scheduling parallel tasks to minimize average response time

Abstract

Consider a system of independent tasks which are to be scheduled without preemption on a parallel computer. For each task both the number of processors required and the corresponding execution time are known. The problem of finding a schedule with minimum makespan has been extensively studied in the literature. In this paper we tackle the corresponding problem of finding a schedule with minimum average response time. The results are analogous: The average response time problem is also NP-hard, and we construct a polynomial time algorithm whose solution is within a fixed multiplicative constant of optimal. Moreover, we show that none of the classic algorithms for the makespan problem have this property when viewed as solutions to the average response time problem.