New algorithms for an ancient scheduling problem

ABSTRACT

We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the makespan, the completion time of the last job. In the on-line version, as soon as job j arrrives, it must be assigned immediately to one of the m machines. We present two main results. The first is a (2–&egr;)-competitive deterministic algorithm for all m. The competitive ratio of all previous algorithms approaches 2 as m→ ∞ . Indeed, the problem of improving the competitive ratio for large m had been open since 1966, when the first algorithm for this problem appeared. The second result is an optimal randomized algorithm for the case m = 2. To the best of our knowledge, our 4/3-competitive algorithm is the first specifically randomized algorithm for the original, m-machine, on-line scheduling problem.

REFERENCES

• 1: U. Faigle , W. Kern , G. Turan, On the performance of on-line algorithms for partition problems, Acta Cybernetica, v.9 n.2, p.107-119, 1989
• 2: G. Galambos and G. Woeginger, "An On- Line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling," manuscript, J6zsef Attila University, Szeged, Hungary.
• 3: R. L. Graham, "Bounds for Certain Multiprocessing Anomalies," Bell System Technical Journal 45 (1966), 1563-1581.
• 4: R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey," Annals of Discrete Mathematics 5 (1979), 287-326.
• 5: E. L. Lawler, "Recent Results in the Theory of Machine Scheduling," in A. Baehem, M. Grotsehel, and B. Korte (eds.), Math Programming The State of the Art (Bonn 1982), Springer-Verlag, New York, 1983, 202-234.
• 6: E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, "Sequencing and Scheduling: Algorithms and Complexity," to appear in Handbook of Operations Research and Management Science, Volume IV: Production Planning and Inventory, S. C. Graves, A. H. G. Rinnooy Kan, and P. Zipkin (eds.), North-Holland.
• 7: J. K. Lenstra and A. H. G. Rinnooy Kan, "An Introduction to Multiprocessor Scheduling," Technical Report, CWI, Amsterdam, 1988.
• 8: N. Linial, personal communication.
• 9: P. R. Narayanan and R. Chandrasekaran, "Optimal On-Line Algorithms for Scheduling," manuscript, University of Texas at Dallas, 1991.

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

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory