Online nonpreemptive scheduling of equal-length jobs on two identical machines

ABSTRACT

We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P2 | p_j = p,r_j | ∑ &Uhorbar;_j. The problem is known to be polynomially solvable in an offline setting.

In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.

REFERENCES

• 1: Baptiste, P., Brucker, P., Knust, S., and Timkovsky, V. G. 2004. Ten notes on equal-processing-time scheduling. 4OR: Quarterly J. Belgian, French and Italian Oper. Res. Soc. 2, 2 (July), 111--127.
• 2: Baruah, S. K., Haritsa, J. R., and Sharma, N. 2001. On-line scheduling to maximize task completions. J. Combin. Math. Combin. Computing 39, 65--78.
• 3: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 4: Marek Chrobak , Wojciech Jawor , Jirˇi´ Sgall , Toma´sˇ Tichy´, Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help, SIAM Journal on Computing, v.36 n.6, p.1709-1728, February 2007 [doi>10.1137/S0097539704446608]
• 5: Ding, J., and Zhang, G. 2006. Online scheduling with hard deadlines on parallel machines. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (Hong Kong, China). Lecture Notes in Computer Science, vol. 4041. Springer-Verlag, New York, 32--42.
• 6: 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]
• 7: Michael H. Goldwasser, Patience is a virtue: the effect of slack on competitiveness for admission control, Journal of Scheduling, v.6 n.2, p.183-211, March/April 2003 [doi>10.1023/A:1022994010777]
• 8: Michael H. Goldwasser , Boris Kerbikov, Admission control with immediate notification, Journal of Scheduling, v.6 n.3, p.269-285, May/June 2003 [doi>10.1023/A:1022956425198]
• 9: Jackson, J. R. 1955. Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, University of California, Los Angeles. Jan.
• 10: Simons, B. B. 1983. Multiprocessor scheduling of unit length jobs with arbitrary release times and deadlines. SIAM J. Comput. 12, 294--299.
• 11: Barbara B. Simons , Manfred K. Warmuth, A fast algorithm for multiprocessor scheduling of unit-length jobs, SIAM Journal on Computing, v.18 n.4, p.690-710, Aug. 1989 [doi>10.1137/0218048]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

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

General Terms:
Algorithms, Theory

Keywords:
Admission control, competitive analysis, scheduling