×

Control of arrivals to two queues in series. (English) Zbl 0569.60091

We consider two queues in series with input to each queue, which can be controlled by accepting or rejecting arriving customers. The objective is to maximize the discounted or average expected net benefit over a finite or infinite horizon, where net benefit is composed of (random) rewards for entering customers minus holding costs assessed against the customers at each queue. Provided that it costs more to hold a customer at the first queue than at the second, we show that an optimal policy is monotonic in the following senses: Adding a customer to either queue makes it less likely that we will accept a new customer into either queue; moreover, moving a customer from the first queue to the second makes it more (less) likely that we will accept a new customer into the first (second) queue.
Our model has policy implications for flow control in communication systems, industrial job shops, and traffic-flow systems. We comment on the relation between the control policies implied by our model and those proposed in the communications literature.

MSC:

60K25 Queueing theory (aspects of probability theory)
90C47 Minimax problems in mathematical programming
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Davis, E., Optimal control of arrivals to a two-server queueing system with separate queues, (Ph.D. dissertation, Program in Operations Research (1977), N.C. State University: N.C. State University Raleigh)
[2] Ephremides, A.; Varaiya, P.; Walrand, J., A simple dynamic routing problem, IEEE Transactions on Automatic Control, 25, 690-693 (1980) · Zbl 0451.90060
[3] Farrell, W., Optimal switching policies in a nonhomogeneous exponential queueing system, (Ph.D. dissertation (1976), Graduate School of Management, University of California: Graduate School of Management, University of California Los Angeles)
[4] Gerla, M.; Kleinrock, L., Flow control: A comparative survey, IEEE Transactions on Communication, 28, 552-574 (1980)
[5] Ghoneim, H., Optimal control of arrivals to a network of two servers in series, (Ph.D. dissertation, Program in Operations Research (1980), N.C. State University: N.C. State University Raleigh) · Zbl 1169.74478
[6] Hajek, B., Optimal control of two interacting service stations, IEEE Transactions on Automatic Control, 29, 491-499 (1984) · Zbl 0555.90047
[7] Johansen, S.; Stidham, S., Control of arrivals to a stochastic input-output system, Advances in Applied Probability, 12, 972-999 (1980) · Zbl 0436.60074
[8] Lazar, A., Optimal flow control of a class of queueing networks in equilibrium, IEEE Transactions on Automatic Control, 28, 1001-1007 (1983) · Zbl 0526.90041
[9] Lippman, S., Applying a new device in the optimization of exponential queueing systems, Operations Research, 23, 687-710 (1975) · Zbl 0312.60048
[10] Lippman, S.; Stidham, S., Individual versus social optimization in exponential congestion system, Operations Research, 25, 233-247 (1977) · Zbl 0369.90079
[11] Naor, P., On the regulation of queue size by levying tolls, Econometrica, 37, 15-24 (1969) · Zbl 0172.21801
[12] Schäl, M., Conditions for optimally in dynamic programming and for the limit of \(n\)-stage optimal policies to be optimal, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 32, 179-196 (1975) · Zbl 0316.90080
[13] Serfozo, R., Monotone optimal policies for Markov decision processes, (Stochastic Systems: Modelling, Identification, and Optimization II, Mathematical Programming Study, 6 (1976), North-Holland: North-Holland New York), 202-216
[14] Serfozo, R., An equivalence beween discrete- and continuous-time Markov decision processes, Operations Research, 27, 616-620 (1979) · Zbl 0413.90079
[15] Stidham, S., On the convergence of successive approximations in dynamic programming with non-zero terminal reward, Zeitschrift für Operations Research, 25, 57-77 (1981) · Zbl 0454.90087
[16] Stidham, S., Optimal control of admission to a queueing system, IEEE Transactions on Automatic Control (August 1985), to appear in
[17] Stidham, S.; Nunen, J.van, The shift-function approach ffor Markov decision processes with unbounded returns, (Technical Report No. 80-7 (1980), Department of Industrial Engineering, N.C. State University: Department of Industrial Engineering, N.C. State University Raleigh)
[18] Topkis, D., Minimizing a submodular function on a lattice, Operations Research, 26, 305-321 (1978) · Zbl 0379.90089
[19] Hee, K.van; Hordijk, A.; Wal, J.van der, Successive approximation for convergent dynamic programming, (Tijms, H. C.; Wessels, J., Markov Decision Theory (1977), Mathematical Centre tract No. 93: Mathematical Centre tract No. 93 Amsterdam), 183-211
[20] Wal, J.van der, Stochastic Dynamic Programming (1981), Mathematical Centre Tract No. 139: Mathematical Centre Tract No. 139 Amsterdam
[21] Weber, R., On the optimal assignment of customers to parallel servers, Journal of Applied Probability, 15, 406-413 (1978) · Zbl 0378.60095
[22] Weber, R.; Stidham, S., Optimal control service rates in cycles and series of queues (1983), Statistical Laboratory, University of Cambridge, submitted for publication
[23] Whittle, P., (Optimization over Time: Dynamic Programming and Stochastoc Control, Vol. II (1983), Wiley: Wiley New York)
[24] Winston, W., Optimality of the shortest-processing-time discipline, Journal of Applied Probability, 14, 181-189 (1977) · Zbl 0357.60023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.