Online deadline scheduling: multiple machines and randomization

ABSTRACT

We study the competitiveness of online deadline scheduling problems. It is assumed that jobs are non-preemptive and we want to maximize, in an online manner, the sum of the length of jobs completed before their deadlines. When there is a single machine, Goldwasser [4] showed that the optimal deterministic competitiveness of this problem is 2+1/k, where each job of length L can be delayed for at least k • L before it is started, while still meeting its deadline. We consider the case that k < 1 and present an O((log 1/k ))-competitive randomized algorithm not only for a single machine but also for m machines where m = 1,2,•••, O(( log 1/k )).Of particular interest is our technique: we mainly consider deterministic algorithms for multiple machines in order to improve the randomized competitiveness for a single (or more) machine. Though this approach is not completely new, it is rather complicated in our case to design a deterministic algorithm for multiple machines. Specifically, we present an [m+1+ m • (1/k)^(1/m)]-competitive deterministic algorithm, where m (≥ 2) machines are available to both online algorithms and the adversary.Finally we also study a related problem and present an improved algorithm.

REFERENCES

• 1: B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive on-line routing. In Proc. of 34th FOCS, pages 32--41, 1993.
• 2: B. Awerbuch, Y. Azar, and S. Plotkin. Online admission control and circuit routing for high performance computing and communication. In Proc. of 35th FOCS, pages 412--423, 1994.
• 3: Sally A. Goldman , Jyoti Parwatikar , Subhash Suri, Online scheduling with hard deadlines, Journal of Algorithms, v.34 n.2, p.370-389, Feb. 2000 [doi>10.1006/jagm.1999.1060]
• 4: Michael H. Goldwasser, Patience is a virtue: the effect of slack on competitiveness for admission control, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.396-405, January 17-19, 1999, Baltimore, Maryland, United States
• 5: Jae-Hoon Kim , Kyung-Yong Chwa, On-Line Deadline Scheduling on Multiple Resources, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.443-452, August 20-23, 2001
• 6: Chiu-Yuen Koo , Tak-Wah Lam , Tsuen-Wan Ngan , Kar-Keung To, Extra processors versus future information in optimal deadline scheduling, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564890]
• 7: R. Lipton, Online interval scheduling, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.302-311, January 23-25, 1994, Arlington, Virginia, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

General Terms:
Algorithms, Theory