A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation

ABSTRACT

We consider the online problem of scheduling jobs on unrelated machines so as to minimize the total weighted flow time. This problem has an unbounded competitive ratio even for very restricted settings. In this paper we show that if we allow the machines of the online algorithm to have ε more speed than those of the offline algorithm then we can get an O((1+ε^-1)²)-competitive algorithm. Our algorithm schedules jobs preemptively but without migration. However, we compare our solution to an offline algorithm which allows migration. Our analysis uses a potential function argument which can also be extended to give a simpler and better proof of the randomized immediate dispatch algorithm of Chekuri-Goel-Khanna-Kumar for minimizing average flow time on parallel machines.

REFERENCES

• 1: S. Anand, Naveen Garg, and Amit Kumar. An O(log P) competitive algorithm for minimizing flow time on related machines. Unpublished manuscript, 2009.
• 2: Nir Avrahami , Yossi Azar, Minimizing Total Flow Time and Total Completion Time with Immediate Dispatching, Algorithmica, v.47 n.3, p.253-268, March 2007 [doi>10.1007/s00453-006-0193-6]
• 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: 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]
• 5: 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]
• 6: Nikhil Bansal , Ho-Leung Chan , Rohit Khandekar , Kirk Pruhs , Cliff Stein , Baruch Schieber, Non-Preemptive Min-Sum Scheduling with Resource Augmentation, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.614-624, October 21-23, 2007 [doi>10.1109/FOCS.2007.46]
• 7: 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]
• 8: 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]
• 9: 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]
• 10: Naveen Garg and Amit Kumar. Better algorithms for minimizing average flow-time on related machines. In ICALP (1), pages 181--190, 2006.
• 11: Naveen Garg , Amit Kumar, Minimizing average flow time on related machines, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132618]
• 12: Naveen Garg , Amit Kumar, Minimizing Average Flow-time: Upper and Lower Bounds, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.603-613, October 21-23, 2007 [doi>10.1109/FOCS.2007.42]
• 13: Naveen Garg , Amit Kumar , V. N. Muralidhara, Minimizing Total Flow-Time: The Unrelated Case, Proceedings of the 19th International Symposium on Algorithms and Computation, December 15-17, 2008, Gold Coast, Australia [doi>10.1007/978-3-540-92182-0_39]
• 14: B. Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance [scheduling problems], Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.214, October 23-25, 1995
• 15: 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]
• 16: 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]
• 17: 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]

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:
approximation algorithms, competitive ratio, flow-time, scheduling