Minimizing weighted flow time

ABSTRACT

We consider the problem of minimizing the total weighted flow time on a single machine with preemptions. We give an online algorithm that is O(k)-competitive for k weight classes. This implies an O(log W)-competitive algorithm, where W is the maximum to minimum ratio of weights. This algorithm also implies an O(log n + log P)-approximation ratio for the problem, where P is the ratio of the maximum to minimum job size and n is the number of jobs. We also consider the nonclairvoyant setting where the size of a job is unknown upon its arrival and becomes known to the scheduler only when the job meets its service requirement. We consider the resource augmentation model, and give a (1 + ϵ)-speed, (1 +1/ϵ)-competitive online algorithm.

REFERENCES

• 1: Foto Afrati , Evripidis Bampis , Chandra Chekuri , David Karger , Claire Kenyon , Sanjeev Khanna , Ioannis Milis , Maurice Queyranne , Martin Skutella , Cliff Stein , Maxim Sviridenko, Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.32, October 17-18, 1999
• 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, 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]
• 4: Bansal, N. 2005. Minimizing flow time on a constant number of machines with preemption. Oper. Res. Lett. 33, 267--273.
• 5: Nikhil Bansal , Kedar Dhamdhere , Jochen Könemann , Amitabh Sinha, Non-clairvoyant Scheduling for Minimizing Mean Slowdown, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.260-270, February 27-March 01, 2003
• 6: 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]
• 7: Bansal, N., and Pruhs, K. 2004. Server scheduling in the weighted ℓ_p norm. In Proceedings of the Latin American Symposium on Theoretical Informatics (LATIN), 434--443.
• 8: Luca Becchetti , Stefano Leonardi, Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines, Journal of the ACM (JACM), v.51 n.4, p.517-539, July 2004 [doi>10.1145/1008731.1008732]
• 9: 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
• 10: 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
• 11: 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
• 12: Michael A. Bender , S. Muthukrishnan , Rajmohan Rajaraman, Improved algorithms for stretch scheduling, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.762-771, January 06-08, 2002, San Francisco, California
• 13: 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]
• 14: 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]
• 15: 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]
• 16: C. Chekuri , R. Motwani , B. Natarajan , C. Stien, Approximation techniques for average completion time scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.609-618, January 05-07, 1997, New Orleans, Louisiana, United States
• 17: Leslie A. Hall , Andreas S. Schulz , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, v.22 n.3, p.513-544, Aug. 1997 [doi>10.1287/moor.22.3.513]
• 18: 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]
• 19: Bala Kalyanasundaram , Kirk R. Pruhs, Minimizing flow time nonclairvoyantly, Journal of the ACM (JACM), v.50 n.4, p.551-567, July 2003 [doi>10.1145/792538.792545]
• 20: Hans Kellerer , Thomas Tautenhahn , Gerhard J. Woeginger, Approximability and nonapproximability results for minimizing total flow time on a single machine, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.418-426, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237989]
• 21: Lenstra, J., Kan, A., and Brucker, P. 1977. Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343--362.
• 22: 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]
• 23: 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]
• 24: 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
• 25: 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]
• 26: Pruhs, K., Sgall, J., and Torng, E. 2004. Online scheduling. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Ratan, FL, Chap. 35 CRC Press.
• 27: Schrage, L. 1968. A proof of the optimality of the shortest processing remaining time discipline. Oper. Res. 16, 678--690.
• 28: Smith, W. 1956. Various optimizers for single-stage production. Naval Res. Logistics Quart. 3, 59--66.

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, Performance

Keywords:
Scheduling, nonclairvoyant scheduling, online algorithms, response time