SRPT optimally utilizes faster machines to minimize flow time

ABSTRACT

We analyze the shortest remaining processing time (SRPT) algorithm with respect to the problem of scheduling n jobs with release times on m identical machines to minimize total flow time. It is known that SRPT is optimal if m = 1 but that SRPT has a worst-case approximation ratio of Θ(min(log n/m, log Δ)) for this problem, where Δ is the ratio of the length of the longest job divided by the length of the shortest job. It has previously been shown that SRPT is able to use faster machines to produce a schedule as good as an optimal algorithm using slower machines. We now show that SRPT optimally uses these faster machines with respect to the worst-case approximation ratio. That is, if SRPT is given machines that are s ≥ 2 − 1/m times as fast as those used by an optimal algorithm, SRPT's flow time is at least s times smaller than the flow time incurred by the optimal algorithm. Clearly, no algorithm can offer a better worst-case guarantee, and we show that existing algorithms with similar performance guarantees to SRPT without resource augmentation do not optimally use extra resources.

REFERENCES

• 1: Edward J. Anderson , Chris N. Potts, Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time, Mathematics of Operations Research, v.29 n.3, p.686-697, August 2004 [doi>10.1287/moor.1040.0092]
• 2: Nir Avrahami , Yossi Azar, Minimizing total flow time and total completion time with immediate dispatching, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777415]
• 3: Baruch Awerbuch , Yossi Azar , Stefano Leonardi , Oded Regev, Minimizing the Flow Time Without Migration, SIAM Journal on Computing, v.31 n.5, p.1370-1382, 2002 [doi>10.1137/S009753970037446X]
• 4: Bussema, C., and Torng, E. 2006. Greedy multiprocessor server scheduling. Oper. Res. Letters 34, 451--458.
• 5: Chandra Chekuri , Ashish Goel , Sanjeev Khanna , Amit Kumar, Multi-processor scheduling to minimize flow time with ε resource augmentation, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007411]
• 6: Chandra Chekuri , Sanjeev Khanna , An Zhu, Algorithms for minimizing weighted flow time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.84-93, July 2001, Hersonissos, Greece [doi>10.1145/380752.380778]
• 7: Conway, R. W., Maxwell, W. L., and Miller, L. W. 1967. Theory of Scheduling. Addison-Wesley, Reading, MA.
• 8: Piotr Berman , Chris Coulston, Speed is more powerful than clairvoyance, Nordic Journal of Computing, v.6 n.2, p.181-193, Summer 1999
• 9: Jeff Edmonds, Scheduling in the dark, Theoretical Computer Science, v.235 n.1, p.109-141, March 17, 2000 [doi>10.1016/S0304-3975(99)00186-3]
• 10: Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Disc. Math. 5. 287--326.
• 11: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 12: Leonardi, S. 2003. A simpler proof of preemptive flow-time approximation. In Approximation and On-line Algorithms. Lecture Notes in Computer Science. Springer-Verlag, New York.
• 13: Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.110-119, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258562]
• 14: Phillips, C., Stein, C., Torng, E., and Wein, J. 2002. Optimal time-critical scheduling via resource augmentation. Algorithmica 32, 163--200.
• 15: Schrage, L. E. 1968. A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16, 678--690.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory

Keywords:
SRPT, flow time, parallel machines, resource augmentation, scheduling