On randomized online scheduling

ABSTRACT

(MATH) We study one of the most basic problems in online scheduling. A sequence of jobs has to be scheduled on $m$ identical parallel machines so as to minimize the makespan. Whenever a new job arrives, its processing time is known in advance. The job has to be scheduled immediately on one of the machines without knowledge of any future jobs. In the sixties Graham presented the famous List scheduling algorithm which is $(2-{1\over m})$-competitive. In the last ten years deterministic online algorithms with an improved competitiveness have been developed. The first algorithm with a performance guarantee asymptotically smaller than 2 was 1.986- competitive. The competitive ratio was first improved to 1.945 and then to 1.923 and 1.9201. Randomized competitive algorithms that are better than (known) deterministic algorithms were proposed for specific values of $m$, i.e. for $m\in\{2,\ldots,7\}$.(MATH) In this paper we present the first randomized online algorithm that performs better than known deterministic algorithms for general $m$. The algorithm is a combination of two deterministic scheduling strategies $A_1$ and $A_2$. Initially, when starting the scheduling process, a scheduler chooses $A_i$, $i\in\{1,2\}$, with probability ${1\over 2}$ and then serves the entire job sequence using the chosen algorithm. The new randomized algorithm is 1.916-competitive. We prove that this performance cannot be achieved by a deterministic algorithm based on analysis techniques that have been used in the literature so far: Using know techniques (or generalizations) it is impossible to prove a competitiveness smaller than 1.919 for any deterministic online algorithm. Our results strictly limit the performance that can be achieved with existing techniques.

REFERENCES

• 1: Susanne Albers, Better Bounds for Online Scheduling, SIAM Journal on Computing, v.29 n.2, p.459-473, Oct. 1999 [doi>10.1137/S0097539797324874]
• 2: Yair Bartal , Amos Fiat , Howard Karloff , Rakesh Vohra, New algorithms for an ancient scheduling problem, Journal of Computer and System Sciences, v.51 n.3, p.359-366, Dec. 1995 [doi>10.1006/jcss.1995.1074]
• 3: Yair Bartal , Howard Karloff , Yuval Rabani, A better lower bound for on-line scheduling, Information Processing Letters, v.50 n.3, p.113-116, May 9, 1994 [doi>10.1016/0020-0190(94)00026-3]
• 4: Bo Chen , André van Vliet , Gerhard J. Woeginger, A lower bound for randomized on-line scheduling algorithms, Information Processing Letters, v.51 n.5, p.219-222, Sept. 12, 1994 [doi>10.1016/0020-0190(94)00110-3]
• 5: 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
• 6: Rudolf Fleischer , Michaela Wahl, Online Scheduling Revisited, Proceedings of the 8th Annual European Symposium on Algorithms, p.202-210, September 05-08, 2000
• 7: Gábor Galambos , Gerhard J. Woeginger, An on-line scheduling heuristic with better worst case ratio than Graham's list scheduling, SIAM Journal on Computing, v.22 n.2, p.349-355, April 1993 [doi>10.1137/0222026]
• 8: Todd Gormley , Nicholas Reingold , Eric Torng , Jeffery Westbrook, Generating adversaries for request-answer games, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.564-565, January 09-11, 2000, San Francisco, California, United States
• 9: R.L. Graham. Bounds for certain multi-processing anomalies. Bell System Technical Journal, 45:1563--1581, 1966.
• 10: David R. Karger , Steven J. Phillips , Eric Torng, A better algorithm for an ancient scheduling problem, Journal of Algorithms, v.20 n.2, p.400-430, March 1996 [doi>10.1006/jagm.1996.0019]
• 11: S.S. Seiden. Online randomized multiprocessor scheduling. Algorithmica, 28:173--216, 2000.
• 12: Steve Seiden, Barely random algorithms for multiprocessor scheduling, Journal of Scheduling, v.6 n.3, p.309-334, May/June 2003 [doi>10.1023/A:1022960526107]
• 13: Jiří Sgall, A lower bound for randomized on-line multiprocessor scheduling, Information Processing Letters, v.63 n.1, p.51-55, July 14, 1997 [doi>10.1016/S0020-0190(97)00093-8]
• 14: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]

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.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Experimentation, Performance, Theory