Shivendra S. Panwar
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.
- 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.Google Scholar
- 2 DERTOUZOS, M. Control robotics: The procedural control of physical processes. In Proceedings of the IFIP Congress, 1974, pp. 807-813.Google Scholar
- 3 GOLD, B. Digital speech networks. Proc. IEEE 65 (Dec. 1977), 1636-1658.Google Scholar
- 4 GROSS, D., AND HARRIS, M.T. Fundamentals of Queueing Theory. Wiley, New York, 1974. Google Scholar
- 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.Google Scholar
- 6 HOWARD, R. Dynamic Programming and Markov Processes. M.I.T. Press, Cambridge, Mass., 1960.Google Scholar
- 7 JACKSON, J.R. Scheduling a production line to minimize maximum tardiness. Res. Rep. 43, Management Sci. Rep., Univ. of Calif., Los Angeles, 1955.Google Scholar
- 8 KLEINROCK, L. Queueing Systems Volume II: Computer Applications. Wiley, New York, 1976.Google Scholar
- 9 MOORE, J. M. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Manage. Sci. 15 (1968), 102-I09.Google Scholar
- 10 PANWAR, S.S. Time constrained and multiaccess communications. Ph.D. dissertation. Dept. of Electrical and Computer Electrical Engineering, Univ. of Massachusetts, Amherst, Feb. 1986. Google Scholar
- 11 PIERSKALLA, W. P., AND ROACH, C. Optimal issuing policies for perishable inventory. Manage. Sci. 18 (1972), 603-614.Google Scholar
- 12 PINEDO, M. Stochastic scheduling with release dates and due dates. Oper. Res. 31 (1983), 559-572.Google Scholar
- 13 SCHWARTZ, M. Telecommunication Networks: Protocols, Modeling and Analysis. Addison- Wesley, Reading, Mass., 1987. Google Scholar
- 14 Su, Z.-S., AND SEVCIK, K.C. A combinatorial approach to scheduling problems. Oper. Res. 26 (1978), 836-844.Google Scholar
Index Terms
- Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service
Recommendations
Customer Abandonment in Many-Server Queues
We study G/G/n + GI queues in which customer patience times are independent, identically distributed following a general distribution. When a customer's waiting time in queue exceeds his patience time, the customer abandons the system without service. ...
Optimal control of parallel queues with impatient customers
Performance modelling and evaluation of high-performance parallel and distributed systemsWe consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent ...
Reviews
Carl Glen Ponder
This paper treats the problem of queueing packets that have an assigned expiration date. If a packet does not begin processing within the specified time limit, it is discarded as useless. The primary example is transmission of voice or video frames over a packet-switched network, where the illusion of real-time transmission is to be maintained. The occasional loss of a packet will reduce transmission quality, but the voice or video reception should remain intelligible. A shortest time to extinction (STE) policy services the customer nearest its completion deadline if no customer is already being serviced. A shortest time to extinction with inserted idle time (STEI) policy also services the customer nearest its completion deadline, though it may choose to sit idle before servicing the next customer. A scheduling policy is optimal within its class if it is minimal with respect to the expected number of discarded packets. The authors show that the following results hold. (1)For a continuous-time nonpreemptive queue with an exponential distribution of arrivals, a general distribution of service times, and a general distribution of deadlines ( M/ G/1 + G queue), the STE policy is optimal among policies not inserting idle times. (2)Under the assumptions in (1), except that inserted idle times are permitted, STEI policies will approach optimality. (3)For a discrete-time nonpreemptive queue with a general distribution of arrivals, unit service time, and a general distribution of deadlines ( G/ D/1 + G queue), the STE policy is optimal even with inserted idle times permitted. The proven results are supplemented by some approximations of the expected losses incurred by STE versus first-come, first-served (FCFS) and STEI under various parameters. The authors were unable to construct an STEI policy superior to STE. These results are of fundamental importance in queueing theory. The classes of queues and policies under consideration are quite basic, yet results in this field are scarce even under simple conditions. The fact that STE and STEI policies are optimal seems to be the intuitively most plausible result. Unfortunately the proofs require a significant amount of notation, even though the proof ideas are straightforward. The (un)readability is typical of papers in the Journal of the ACM, though a better presentation would be difficult. A less frivolous complaint is that the results do not extend further: Can one construct an STEI policy that is optimal for the M/ G/1 + G queue__ __ Result (2) uses an existence proof that can construct an STEI policy to match the performance of any other policy. No optimal policy is presented. Alternatively, one might show that some intuitively simple STEI policies are suboptimal. Regarding the original intent of the paper, the distribution of discarded packets is worth considering. The transmission will not be intelligible if the losses are clumped together.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments