Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-18T11:51:48.206Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal control of batch service queues

Published online by Cambridge University Press:  01 July 2016

Rajat K. Deb  and
Richard F. Serfozo
Rajat K. Deb
Affiliation:
State University of New York, Oswego
Richard F. Serfozo
Affiliation:
Syracuse University
Get access Rights & Permissions [Opens in a new window]

Abstract

A batch service queue is considered where each batch size and its time of service is subject to control. Costs are incurred for serving the customers and for holding them in the system. Viewing the system as a Markov decision process (i.e., dynamic program) with unbounded costs, we show that policies which minimize the expected continuously discounted cost and the expected cost per unit time over an infinite time horizon are of the form: at a review point when x customers are waiting, serve min {x, Q} customers (Q being the, possibly infinite, service capacity) if and only if x exceeds a certain optimal level M. Methods of computing M for both the discounted and average cost contexts are presented.

Keywords

BATCH SERVICE QUEUESBULK QUEUESDYNAMIC PROGRAMMINGMARKOV DECISION PROCESSESSTOCHASTIC CONTROL
Type
Research Article
Information
Advances in Applied Probability , Volume 5 , Issue 2 , August 1973 , pp. 340 - 361
Copyright
Copyright © Applied Probability Trust 1973 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Bailey, N. T. J. (1954) On queueing process with bulk service. J. R. Statist. Soc. B 18, 265–274.Google Scholar
[2] Crabill, T. (1969) Optimal control of a queue wih variable service rate. Technical Report No. 75, Department of Operations Research, Cornell University.Google Scholar
[3] Deb, R. (1971) Optimal Control of Bulk Queues. Ph. D. dissertation, Systems and Information Sciences, Syracuse University.Google Scholar
[4] Derman, C. (1962) On sequential decisions and Markov chains. Management Sci. 9, 16–24.Google Scholar
[5] Fabens, A. J. (1961) The solution of queueing and inventory models by semi-Markov processes. J. R. Statist. Soc. B 23, 113–127.Google Scholar
[6] Heyman, D. P. (1968) Optimal operating policies for M/G/1 queueing systems. Operations Res. 16, 362–382.Google Scholar
[7] Howard, R. A. (1970) Dynamic Probabilistic Systems. Vols. 1 and 2. John Wiley and Sons, New York.Google Scholar
[8] Klein, M. (1962) Inspection-maintenance-replacement schedules under Markovian deterioration. Management Sci. 9, 25–32.Google Scholar
[9] Kolesar, P. (1966) Minimum cost replacement under Markovian deterioriation. Management Sci. 12, 694–766.Google Scholar
[10] Magazine, M. J. (1969) Optimal Policies for Queueing Systems with Periodic Review. Ph. D. dissertation, University of Florida.Google Scholar
[11] McGill, J. T. (1969) Optimal control of a queueing system with variable number of exponential servers. Technical Report No. 123, Department of Operations Research, Stanford University.Google Scholar
[12] Miller, B. L. (1969) A queueing reward system with several customer classes. Management Sci. 16, 234–245.Google Scholar
[13] Mine, H. and Osaki, S. (1970) Markovian Decision Processes. American Elsevier, New York.Google Scholar
[14] Rolfe, A. J. (1968) The control of a multiple facility, multiple channel queueing system with parallel input streams. Technical Report No. 22, Graduate School of Business, Stanford University.Google Scholar
[15] Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
[16] Saaty, T. L. (1961) Elements of Queueing Theory with Applications. McGraw-Hill, New York.Google Scholar
[17] Sobel, M. G. (1969) Optimal average-cost policy for a queue with start-up and shut-down costs. Operations Res. 17, 145–162.Google Scholar
[18] Stidham, S. (1970) On the optimality of single-server queueing systems. Operations Res. 18, 708–732.Google Scholar
[19] Takács, L. (1962) Introduction to the Theory of Queues. Oxford University Press, New York.Google Scholar
[20] Thatcher, R. M. (1968) Optimal Single Channel Service Policies for Stochastic Arrivals. Ph.D. dissertation, University of California, Berkeley.Google Scholar
[21] Widder, D. (1941) The Laplace Transform. Princeton University Press, Princeton, New Jersey.Google Scholar
[22] Yadin, M. and Naor, P. (1967) On queueing systems with variable service capacities. Naval Res. Logist. Quart. 14, 43–53.Google Scholar
[23] Yadin, M. and Naor, P. (1963) Queueing systems with removable service station. Operational Research Quarterly 17, 393–405.Google Scholar
[24] Yadin, M. and Zacks, S. (1969) The optimal control of a queueing process. Technical Report No. 54, Industrial and Management Engineering, Haifa, Israel.Google Scholar