On the definition of "on-line" in job scheduling problems

ABSTRACT

The conventional model of on-line scheduling postulates that jobs have non-trivial release dates, and are not known in advance. However, it fails to impose any stability constraints, leading to algorithms and analyses that must deal with unrealistic load conditions arising from trivial release dates as a special case. In an effort to make the model more realistic, we show how stability can be expressed as a simple constraint on release times and processing times. We then give empirical and theoretical justifications that such a constraint can close the gap between the theory and practice. As it turns out, this constraint seems to trivialize the scheduling problem.

REFERENCES

• 1: A. Batat, Gang Scheduling with Memory Considerations. Master's thesis, Hebrew University, Sep 1999.
• 2: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001 [doi>10.1145/363647.363659]
• 3: C. Chekuri , R. Motwani , B. Natarajan , C. Stien, Approximation techniques for average completion time scheduling, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.609-618, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: D. G. Feitelson, A Survey of Scheduling in Multiprogrammed Parallel Systems. Research Report RC 19790 (87657), IBM T. J. Watson Research Center, Oct 1994.
• 5: Dror G. Feitelson , Larry Rudolph , Uwe Schwiegelshohn , Kenneth C. Sevcik , Parkson Wong, Theory and Practice in Parallel Job Scheduling, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.1-34, April 05, 1997
• 6: M. Garey and R. Graham, "Bounds for multiprocessor scheduling with resource constraints". SIAM J. Comput.4(2), pp. 187--200, Jun 1975.
• 7: 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". In Annals of Discrete Mathematics 5, pp. 287--326, North-Holland, 1979.
• 8: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 9: Stefano Leonardi , Danny Raz, Approximating total flow time on parallel machines, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.110-119, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258562]
• 10: David A. Lifka, The ANL/IBM SP Scheduling System, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.295-303, April 25, 1995
• 11: A. Mu'alem and D. G. Feitelson, "Bicriteria scheduling for parallel jobs". In Multidisciplinary Int'l Conf. Scheduling: Theory & Apps. (MISTA), pp. 606--619, Aug 2003.
• 12: D. L. Palumbo, The Derivation and Experimental Verification of Clock Synchronization Theory, IEEE Transactions on Computers, v.43 n.6, p.676-686, June 1994 [doi>10.1109/12.286301]
• 13: Jiri Sgall, On-line Scheduling, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.196-231, January 1998

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: Online computation

General Terms:
Algorithms, Theory