Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service

ABSTRACT

Many problems can be modeled as single-server queues with impatient customers. An example is that of the transmission of voice packets over a packet-switched network. If the voice packets do not reach their destination within a certain time interval of their transmission, they are useless to the receiver and considered lost. It is therefore desirable to schedule the customers such that the fraction of customers served within their respective deadlines is maximized. For this measure of performance, it is shown that the shortest time to extinction (STE) policy is optimal for a class of continuous and discrete time nonpreemptive M/G/1 queues that do not allow unforced idle times. When unforced idle times are allowed, the best policies belong to the class of shortest time to extinction with inserted idle time (STEI) policies. An STEI policy requires that the customer closest to his or her deadline be scheduled whenever it schedules a customer. It also has the choice of inserting idle times while the queue is nonempty. It is also shown that the STE policy is optimal for the discrete time G/D/1 queue where all customers receive one unit of service. The paper concludes with a comparison of the expected customer loss using an STE policy with that of the first-come, first-served (FCFS) scheduling policy for one specific queue.

REFERENCES

• 1: DAISISI~LLI~ 1-'.~ AND FII~tlUII~RNI~, U. VN Clll~UeS Wll.II impatient customers, in rerjormunc'e ol, F. J. Klystra, Ed. North Holland, Amsterdam, 1981, pp. 159-179.
• 2: DERTOUZOS, M. Control robotics: The procedural control of physical processes. In Proceedings of the IFIP Congress, 1974, pp. 807-813.
• 3: GOLD, B. Digital speech networks. Proc. IEEE 65 (Dec. 1977), 1636-1658.
• 4: Donald Gross , Carl M. Harris, Fundamentals of queueing theory (2nd ed.)., John Wiley & Sons, Inc., New York, NY, 1985
• 5: GRUBER, J. G., AND LE, N.H. Performance requirements for integrated voice/data networks. IEEE J. Selected Areas Commun. SAC-I, 6 (Dec. 1983), 981-1005.
• 6: HOWARD, R. Dynamic Programming and Markov Processes. M.I.T. Press, Cambridge, Mass., 1960.
• 7: JACKSON, J.R. Scheduling a production line to minimize maximum tardiness. Res. Rep. 43, Management Sci. Rep., Univ. of Calif., Los Angeles, 1955.
• 8: KLEINROCK, L. Queueing Systems Volume II: Computer Applications. Wiley, New York, 1976.
• 9: MOORE, J. M. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Manage. Sci. 15 (1968), 102-I09.
• 10: Shivendra Singh Panwar, Time constrained and multiaccess communications (packet-switched networks, scheduling, queues impatience, contention, resolution, algorithms), 1986
• 11: PIERSKALLA, W. P., AND ROACH, C. Optimal issuing policies for perishable inventory. Manage. Sci. 18 (1972), 603-614.
• 12: PINEDO, M. Stochastic scheduling with release dates and due dates. Oper. Res. 31 (1983), 559-572.
• 13: Mischa Schwartz, Telecommunication networks: protocols, modeling and analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 14: Su, Z.-S., AND SEVCIK, K.C. A combinatorial approach to scheduling problems. Oper. Res. 26 (1978), 836-844.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Stochastic analysis

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

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

General Terms:
Design, Performance, Theory, Verification