Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines

ABSTRACT

In this paper we study the problem of assigning unit-size tasks to related machines when only limited online information is provided to each task. This is a general framework whose special cases are the classical multiple-choice games for the assignment of unit-size tasks to identical machines. The latter case was the subject of intensive research for the last decade. The problem is intriguing in the sense that the natural extensions of the greedy oblivious schedulers, which are known to achieve near-optimal performance in the case of identical machines, are proved to perform quite poorly in the case of the related machines.(MATH) In this work we present a rather surprising lower bound stating that any oblivious scheduler that assigns an arbitrary number of tasks to $n$ related machines would need $\Omega\left(\frac{\log n}{\l2 n}\right)$ polls of machine loads per task, in order to achieve a constant competitive ratio versus the optimum offline assignment of the same input sequence to these machines. On the other hand, we prove that the missing information for an oblivious scheduler to perform almost optimally, is the amount of tasks to be inserted into the system. In particular, we provide an oblivious scheduler that only uses $\O(\l2 n)$ polls, along with the additional information of the size of the input sequence, in order to achieve a constant competitive ratio vs. the optimum offline assignment. The philosophy of this scheduler is based on an interesting exploitation of the slowfit concept ([1, 5, 3]; for a survey see [6, 9, 16]) for the assignment of the tasks to the related machines despite the restrictions on the provided online information, in combination with a layered induction argument for bounding the tails of the number of tasks passing from slower to faster machines. We finally use this oblivious scheduler as the core of an adaptive scheduler that does not demand the knowledge of the input sequence and yet achieves almost the same performance.

REFERENCES

• 1: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 2: Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195412]
• 3: Piotr Berman , Moses Charikar , Marek Karpinski, On-line Load Balancing for Related Machines, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.116-125, August 06-08, 1997
• 4: Petra Berenbrink , Artur Czumaj , Angelika Steger , Berthold Vöcking, Balanced allocations: the heavily loaded case, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.745-754, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335411]
• 5: A. Bar-Noy, A. Freund, J. Naor. New Algorithms for Related Machines with Temporary Jobs. In Journal of Scheduling, Vol. 3 (2000), pp. 259--272.
• 6: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 7: R. Corless, G. Gonnet, D. Hare, D. Jeffrey, D. Knuth. On the Lambert W Function. In Advances in Computational (MATH)ematics, Vol. 5 (1996), pp. 329--359.
• 8: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 9: Yossi Azar, On-line Load Balancing, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.178-195, January 1998
• 10: Gaston H. Gonnet, Expected Length of the Longest Probe Sequence in Hash Code Searching, Journal of the ACM (JACM), v.28 n.2, p.289-304, April 1981 [doi>10.1145/322248.322254]
• 11: M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed (Eds.). Probabilistic Methods for Algorithmic Discrete (MATH)ematics. ISBN: 3-540-64622-1, Springer-Velrag 1998.
• 12: E. Koutsoupias, C. Papadimitriou. Worst-case Equilibria. In Proc. of 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 1563, Springer-Verlag 1999, pp. 404--413.
• 13: Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
• 14: M. Mitzenmacher, A. Richa, R. Sitaraman. The Power of Two Random Choices: A Survey of Techniques and Results. In Handbook of Randomized Algorithms (to appear). Also available through http://www.eecs.harvard.edu/~michaelm/.
• 15: Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
• 16: Jiri Sgall, On-line Scheduling, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.196-231, January 1998
• 17: David B. Shmoys , Joel Wein , David P. Williamson, Scheduling parallel machines on-line, Proceedings of the 32nd annual symposium on Foundations of computer science, p.131-140, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185361]
• 18: Berthold Vöcking, How Asymmetry Helps Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.131, October 17-18, 1999

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:
  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, Experimentation, Performance, Theory

Keywords:
limited information, online load balancing, related machines