Multi-processor scheduling to minimize flow time with ε resource augmentation

ABSTRACT

We investigate the problem of online scheduling of jobs to minimize flow time and stretch on m identical machines. We consider the case where the algorithm is given either (1+ε)m machines or m machines of speed (1+ε), for arbitrarily small ε > 0. We show that simple randomized and deterministic load balancing algorithms, coupled with simple single machine scheduling strategies such as SRPT (shortest remaining processing time) and SJF (shortest job first), are O(poly(1/ε))-competitive for both flow time and stretch. These are the first results which prove constant factor competitive ratios for flow time or stretch with arbitrarily small resource augmentation. Both the randomized and the deterministic load balancing algorithms are non-migratory and do immediate dispatch of jobs.The randomized algorithm just allocates each incoming job to a random machine. Hence this algorithm is non-clairvoyant, and coupled with SETF (shortest elapsed time first), yields the first non-clairvoyant algorithm which is constant competitive for minimizing flow time with arbitrarily small resource augmentation. The deterministic algorithm that we analyze is due to Avrahami and Azar. For this algorithm, we show O(1/ε)-competitiveness for total flow time and stretch, and also for their Lp norms, for any fixed p ≥ 1.

REFERENCES

• 1: Noga Alon , Yossi Azar , Gerhard J. Woeginger , Tal Yadid, Approximation schemes for scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.493-500, January 05-07, 1997, New Orleans, Louisiana, United States
• 2: A. Avidor, Y. Azar and J. Sgall. Ancient and new algorithms for load balancing in the lp norm. Algorithmica, 29(3):422--441, 2001.
• 3: B. Awerbuch , Y. Azar , E. F. Grove , Ming-Yang Kao , P. Krishnan , J. S. Vitter, Load balancing in the L/sub p/ norm, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.383, October 23-25, 1995
• 4: 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]
• 5: Baruch Awerbuch , Yossi Azar , Stefano Leonardi , Oded Regev, Minimizing the flow time without migration, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.198-205, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301304]
• 6: Nikhil Bansal , Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.279-290, June 2001, Cambridge, Massachusetts, United States
• 7: Nikhil Bansal , Kirk Pruhs, Server scheduling in the L_p norm: a rising tide lifts all boat, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780580]
• 8: N. Bansal , K. Dhamdhere, Minimizing weighted flow time, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Luca Becchetti , Stefano Leonardi, Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.94-103, July 2001, Hersonissos, Greece [doi>10.1145/380752.380782]
• 10: Luca Becchetti , Stefano Leonardi , S. Muthukrishnan, Scheduling to minimize average stretch without migration, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 09-11, 2000, San Francisco, California, United States
• 11: Luca Becchetti , Stefano Leonardi , Alberto Marchetti-Spaccamela , Kirk Pruhs, Online Weighted Flow Time and Deadline Scheduling, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.36-47, August 18-20, 2001
• 12: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 13: Chandra Chekuri , Sanjeev Khanna, Approximation schemes for preemptive weighted flow time, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509954]
• 14: 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]
• 15: M. Crovella, R. Frangioso and M. Harchol-Balter. Connection scheduling in web servers. USENIX Symposium on Internet Technologies and Systems, 1999.
• 16: Leah Epstein , Jiri Sgall, Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines, Proceedings of the 7th Annual European Symposium on Algorithms, p.151-162, July 16-18, 1999
• 17: 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]
• 18: 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]
• 19: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 20: S. Muthukrishnan , Rajmohan Rajaraman , Anthony Shaheen , Johannes E. Gehrke, Online Scheduling to Minimize Average Stretch, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.433, October 17-18, 1999
• 21: Cynthia A. Phillips , Cliff Stein , Eric Torng , Joel Wein, Optimal time-critical scheduling via resource augmentation (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.140-149, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258570]
• 22: B. Schroeder and M. Harchol-Balter. Web servers under overload : how scheduling can help. Proc. of 18th International Teletraffic Congress, 2003.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory

Keywords:
flow time, load balancing, multi-processor scheduling, online algorithms, resource augmentation, stretch