Minimizing weighted flow time

ABSTRACT

We consider the problem of minimizing weighted flow time on a single machine in the preemptive setting. Our main result is an O(log W) competitive online algorithm where the maximum to the minimum ratio of weights is W. More generally our algorithm achieves a competitive ratio of k if there are k weight classes. This gives the first O(1)-competitive algorithm for constant k. No O(1) competitive algorithm was known previously even for the special case of k = 2. These results settle a question posed by Chekuri et al [5] about the existence of a "truly" online algorithm with a non-trivial competitive ratio. We also give a "semi-online" algorithm with competitive ratio O(log n + log P), where P is ratio of the maximum to minimum job size. Our second result deals with the non-clairvoyant setting where the job sizes are unknown (but the weight of the jobs are known). We consider the resource augmentation model, and give a non-clairvoyant online algorithm, which if allowed a (1 + ε) speed-up, is (1 + l/ε) competitive against an optimal offline, clairvoyant 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: 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
• 3: Piotr Berman , Chris Coulston, Speed is more powerful than clairvoyance, Nordic Journal of Computing, v.6 n.2, p.181-193, Summer 1999
• 4: 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]
• 5: 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]
• 6: 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
• 7: 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]
• 8: S. Irani. Randomized weighted caching with two page weights. Algorithmica, 33:384--409, 2002.
• 9: 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]
• 10: J. Lenstra, A. Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343--362, 1977.
• 11: 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]
• 12: L.E. Schrage. A proof of the optimality of the shortest processing remaining time discipline. Operations Research, 16:678--690, 1968.
• 13: W. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3:59--66, 1956.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory