Robert E. Donovan
INTERSPEECH - Eurospeech 2001
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.
Robert E. Donovan
INTERSPEECH - Eurospeech 2001
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)