SMART SMART BOUNDS FOR WEIGHTED RESPONSE-TIME SCHEDULING

Consider a system of independent tasks to be scheduled without preempt ion on a parallel computer. For each task the number of processors req uired, the execution time, and a weight are known. The problem is to f ind a schedule with minimum weighted average response time. We present an algorithm called SMART (which stands for scheduling to minimize av erage response time) for this problem that produces solutions that are within a factor of 8.53 of optimal. To our knowledge this is the firs t polynomial-time algorithm for the minimum weighted average response time problem that achieves a constant bound. In addition, for the unwe ighted case (that is, where all the weights are unity) we describe a v ariant 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.