About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SODA 1994
Conference paper
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.