Smart smart bounds for weighted response time scheduling

Abstract

Consider a system of independent tasks to be scheduled without preemption on a parallel computer. For each task the number of processors required, the execution time, and a weight are known. The problem is to find a schedule with minimum weighted average response time. We present an algorithm called SMART (which stands for scheduling to minimize average response time) for this problem that produces solutions that are within a factor of 8.53 of optimal. To our knowledge this is the first polynomial-time algorithm for the minimum weighted average response time problem that achieves a constant bound. In addition, for the unweighted case (that is, where all the weights are unity) we describe a variant of SMART that produces solutions that are within a factor of 8 of optimal, improving upon the best known bound of 32 for this special case.