The utility of foresight in single server scheduling

ABSTRACT

We consider a single server job queueing system with a Poisson arrival process, hyper-exponentially distributed job service times, no job precedence constraints, nonpreemptive service and a look-ahead table of jobs. A look-ahead heuristic is described which schedules jobs to minimize average job waiting time. This job placement algorithm is then compared to the standard FIFO, LIFO and SJF scheduling policies, which operate without look-ahead knowledge. We isolate situations where the benefits outweigh the expenses incurred by the look-ahead algorithm, and observe some theoretical considerations necessary for modelling this system.

REFERENCES

• 1: Arnold O. Allen, Probability, statistics, and queueing theory with computer science applications, Academic Press Professional, Inc., San Diego, CA, 1990
• 2: K.R. Baker. Introduction to sequencing and scheduling. Wiley, New York, 1974.
• 3: O. Berman and O. Maimon. Cooperation among flexible manufacturing systems. IEEE Journal of Robotics and Automation, RA-2(1):24-30, March 1986.
• 4: J. Bruno , P. Downey , G. N. Frederickson, Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan, Journal of the ACM (JACM), v.28 n.1, p.100-113, Jan. 1981 [doi>10.1145/322234.322242]
• 5: P.G. Gazmuri. Probabilistic analysis of a machine scheduling problem. Mathematics of Operations Research, 10:328-339, 1985.
• 6: R.G. Herrtwich. An introduction to realtime scheduling. Technical Report TR-90- 035, International Computer Science Institute, 1947 Center St, Suite 600, Berkeley, CA 94704-1105, July 1990.
• 7: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 8: L. Kleinrock. Queueing Systems Volume II: Computer Applications. John Wiley and Sons, 1976.
• 9: Labetoulle, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Karl. Preemptive scheduling of uniform machines subject to release dates. Progress Combinatorial Optimization, pages 245-261, 1984.
• 10: L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Karl, and P. Brucker. Sequencing and scheduling: Algorithms and complex- In Handbooks in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory. 1991.
• 11: K. Lenstra, A.H.G. Rinnooy Kan, and Brucker. Complexity of machine schedulproblems. Annals of Discrete Mathematics, 1:343-362, 1977.
• 12: W. Mao and A. Rifkin. Analysis of the fcfs algorithm for 1-rj-cj. TechnicM report, Department of Computer Science, College of William and Mary, December 1991. Submitted to "Information Processing Letters".
• 13: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• 14: S. K. Park. Lecture notes on simulation, version 3.1. Technical report, Department of Computer Science, College of William and Mary, August 1991.
• 15: S. K. Park, S. Harvey, R.K. Kincaid, and Miller. Alternative server disciplines for mobile-servers on a congested network. Presented at the ORSA-CSTS Conference, January 8-10, 1992.
• 16: M. Pinedo. Stochastic scheduling with release dates and due dates. Operations Research, 31(3):559-572, May 1983.
• 17: L. Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, pages 687-690, 1968.
• 18: E. Smith. Various optimizers for singlestate production. Naval Research Logistics Quarterly, 3, 1956.

INDEX TERMS

Keywords:
discrete-event simulation, scheduling theory, single server queue