Minimizing total flow time and total completion time with immediate dispatching

ABSTRACT

We consider the problem of scheduling jobs arriving over time in a multiprocessor setting, with immediate dispatching, disallowing job migration. The goal is to minimize both the total flow time (total time in the system) and the total completion time.Previous studies have shown that while preemption (interrupt a job and later continue its execution) is inherent to make a scheduling algorithm efficient, migration (continue the execution on a different machine) is not. Still, the current non-migratory online algorithms suffer from a need for a central queue of unassigned jobs which is a "no option" in large computing system, such as the Web.We introduce a simple online non-migratory algorithm IMD, which employs immediate dispatching, i.e., it immediately assigns released jobs to one of the machines. We show that the performance of this algorithm is within a logarithmic factor of the optimal migratory offline algorithm, with respect to the total flow time, and within a small constant factor of the optimal migratory offline algorithm, with respect to the total completion time. This solves an open problem suggested by Awerbuch et al [STOC99].

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: 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]
• 3: K.R. Baker. Introduction to Sequencing and Scheduling. Wiley, 1974.
• 4: Soumen Chakrabarti , Cynthia A. Phillips , Andreas S. Schulz , David B. Shmoys , Clifford Stein , Joel Wein, Improved Scheduling Algorithms for Minsum Criteria, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.646-657, July 08-12, 1996
• 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: J. Du , J. Y.-I. Leung , G. H. Young, Minimizing mean flow time with release time constraint, Theoretical Computer Science, v.75 n.3, p.347-355, Oct. 1990 [doi>10.1016/0304-3975(90)90100-V]
• 8: Leslie A. Hall , David B. Shmoys , Joel Wein, Scheduling to minimize average completion time: off-line and on-line algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.142-151, January 28-30, 1996, Atlanta, Georgia, United States
• 9: Leslie A. Hall, Approximation algorithms for scheduling, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 10: Han Hoogeveen , Arjen P. A. Vestjens, Optimal On-Line Algorithms for Single-Machine Scheduling, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.404-414, June 03-05, 1996
• 11: 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]
• 12: E.L. Lawler, J.K Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys. Sequencing and scheduling: algorithms and complexity. In Handbooks in operations research and management science, volume 4, pages 445--522. North Holland, 1993.
• 13: 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]
• 14: Cynthia A. Phillips , Clifford Stein , Joel Wein, Scheduling Jobs that Arrive Over Time (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.86-97, August 16-18, 1995
• 15: L. Stougie and A. Vestjens. Randomized on-line scheduling: How low can't you go, 1997.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

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

General Terms:
Algorithms, Theory

Keywords:
competitive, completion time, flow time, on-line