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

Journal of the ACM - Tập 35 Số 4 - Trang 832-844 - 1988
Shivendra S. Panwar1, Don Towsley2, Jack K. Wolf3
1Polytechnic University, Brooklyn, NY,#TAB#
2University of Massachusetts: Amherst#TAB#
3University of California at San Diego, La Jolla

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

DAISISI~LLI~ 1-'.~ AND FII~tlUII~R NI~ , U. VN Clll~UeS Wll.II impatient customers, in rerjormunc'e ol, F. J. Klystra , Ed. North Holland , Amsterdam , 1981 , pp. 159 - 179 . 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.

DERTOUZOS , M. Control robotics : The procedural control of physical processes . In Proceedings of the IFIP Congress , 1974 , pp. 807 - 813 . DERTOUZOS, M. Control robotics: The procedural control of physical processes. In Proceedings of the IFIP Congress, 1974, pp. 807-813.

GOLD , B . Digital speech networks . Proc. IEEE 65 ( Dec. 1977 ), 1636 - 1658 . GOLD, B. Digital speech networks. Proc. IEEE 65 (Dec. 1977), 1636-1658.

GROSS , D. , AND HARRIS , M.T. Fundamentals of Queueing Theory . Wiley , New York , 1974 . GROSS, D., AND HARRIS, M.T. Fundamentals of Queueing Theory. Wiley, New York, 1974.

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 . 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.

HOWARD , R. Dynamic Programming and Markov Processes . M.I.T. Press , Cambridge, Mass ., 1960 . HOWARD, R. Dynamic Programming and Markov Processes. M.I.T. Press, Cambridge, Mass., 1960.

JACKSON , J.R. Scheduling a production line to minimize maximum tardiness. Res. Rep. 43, Management Sci. Rep ., Univ. of Calif. , Los Angeles , 1955 . JACKSON, J.R. Scheduling a production line to minimize maximum tardiness. Res. Rep. 43, Management Sci. Rep., Univ. of Calif., Los Angeles, 1955.

KLEINROCK , L. Queueing Systems Volume II: Computer Applications . Wiley , New York , 1976 . KLEINROCK, L. Queueing Systems Volume II: Computer Applications. Wiley, New York, 1976.

MOORE , J. M. An n job , one machine sequencing algorithm for minimizing the number of late jobs . Manage. Sci. 15 ( 1968 ), 102 - I09 . MOORE, J. M. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Manage. Sci. 15 (1968), 102-I09.

PIERSKALLA , W. P. , AND ROACH , C . Optimal issuing policies for perishable inventory . Manage. Sci. 18 ( 1972 ), 603 - 614 . PIERSKALLA, W. P., AND ROACH, C. Optimal issuing policies for perishable inventory. Manage. Sci. 18 (1972), 603-614.

PINEDO , M . Stochastic scheduling with release dates and due dates . Oper. Res. 31 ( 1983 ), 559 - 572 . PINEDO, M. Stochastic scheduling with release dates and due dates. Oper. Res. 31 (1983), 559-572.

SCHWARTZ , M. Telecommunication Networks: Protocols, Modeling and Analysis . Addison- Wesley, Reading , Mass ., 1987 . SCHWARTZ, M. Telecommunication Networks: Protocols, Modeling and Analysis. Addison- Wesley, Reading, Mass., 1987.

Su, Z.-S., AND SEVCIK , K.C . A combinatorial approach to scheduling problems . Oper. Res. 26 ( 1978 ), 836 - 844 . Su, Z.-S., AND SEVCIK, K.C. A combinatorial approach to scheduling problems. Oper. Res. 26 (1978), 836-844.

Thông tin
Thông tin xuất bản

Journal of the ACM

Tập 35 Số 4

832-844

Thông tin tác giả