Approximation schemes for preemptive weighted flow time

ABSTRACT

(MATH) We present the first approximation schemes for minimizing weighted flow time on a single machine with preemption. Our first result is an algorithm that computes a (1+&egr;)-approximate solution for any instance of weighted flow time in O(n^{O(ln W ln P/&egr;3)}) time; here P is the ratio of maximum job processing time to minimum job processing time, and W is the ratio of maximum job weight to minimum job weight. This result directly gives a quasi-PTAS for weighted flow time when P and W are poly-bounded, and a PTAS when they are both O(1). We strengthen the former result to show that in order to get a quasi- PTAS it suffices to have just one of P and W to be poly-bounded. Our result provides strong evidence to the hypothesis that the weighted flow time problem has a PTAS. We note that the problem is strongly NP-hard even when P and W are O(1). We next consider two important special cases of weighted flow time, namely, when P is O(1) and W is arbitrary, and when the weight of a job is inverse of its processing time referred to as the stretch metric. For both of the above special cases we obtain a (1+&egr;)-approximation for any &egr; ρ 0 by using a randomized partitioning scheme to reduce an arbitrary instance to several instances all of which have P and W bounded by a constant that depends only on &egr;.

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: 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
• 3: 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
• 4: 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]
• 5: M. E. Dyer , L. A. Wolsey, Formulating the single machine sequencing problem with release dates as a mixed integer program, Discrete Applied Mathematics, v.26 n.2-3, p.255-270, Mar. 1990 [doi>10.1016/0166-218X(90)90104-K]
• 6: Michel X. Goemans, A Supermodular Relaxation for Scheduling with Release Dates, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.288-300, June 03-05, 1996
• 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: M. Harchol-Balter, N. Bansal, and B. Schroeder. Implementation of SRPT Scheduling in Web Servers. Technical Report, Carnegie Mellon University, CMU-CS-00-170, 2000.
• 9: R. Jain. The Art of Computer Systems Performance Analysis. John Wiley, New York, 1991.
• 10: 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]
• 11: J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete (MATH)ematics, 1:343--362, 1977.
• 12: 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]
• 13: 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
• 14: A. Schulz and M. Skutella. The power of α-points in preemptive single machine scheduling. To appear in Journal of Scheduling.
• 15: W. E. Smith. Various optimizers for single-stage production. Naval Res. Logist. Quart., 3:59--66, 1956.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Special function approximations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Performance, Theory