Abstract
We review models for the optimal control of networks of queues. Our main emphasis is on models based on Markov decision theory and the characterization of the structure of optimal control policies.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E.F. Abdel-Gawad, Optimal control of arrivals and routing in a network of queues, Ph.D. dissertation, Program in Operations Research, N.C. State University, Raleigh (1984).
A. Araposthatis, V.S. Borkar, E. Fernandez-Gaucherand, M.K. Ghosh and S.I. Marcus, Discrete-time controlled Markov processes with average cost criterion: a survey, to appear in SIAM J. Control Optim.
J.S. Baras, A.J. Dorsey and A.M. Makowski, Two competing queues with linear costs and geometric service requirements: the μc rule is often optimal, Adv. Appl. Prob. 17 (1985) 186–209.
J.S. Baras, D.-J. Ma and A.M. Makowski,K competing queues with geometric service requirements and linear costs: the μc rule is always optimal, Syst. Control Lett. 6 (1985) 173–180.
M. Bartroli, On the structure of optimal control policies for networks of queues, Ph.D. dissertation, Department of Research, University of North Carolina at Chapel Hill (1989).
D. Bertsekas,Dynamic Programming: Deterministic and Stochastic Models (Prentice-Hall, Englewood Cliffs, NJ, 1987).
F.J. Beutler and D. Teneketzis, Routing in queueing networks under imperfect information, Stoch. Stoch. Reports (1989) 81–100.
V.S. Borkar, Controlled Markov chains and stochastic networks, SIAM J. Control Optim.21 (1983) 652–666.
V.S. Borkar, Control of Markov chains with long-run average cost criterion, in:Stochastic Differential Systems, Stochastic Control Theory and Applications, volume 10, eds. W. Fleming and P.L. Lions, IMA Volumes in Mathematics and its Applications (Springer, 1988) pp. 57–77.
V.S. Borkar, Control of Markov chains with long-run average cost criterion: the dynamic programming equations, SIAM J. Control Optim. 27 (1989) 642–657.
A.D. Bovopoulos and A.A. Lazar, Optimal routing and flow control of a network of parallel processors with individual buffers,Proc. 23rd Allerton Conf. on Communication, Control, and Computing (1985) pp. 564–573.
R. Cavazos-Cadena, Necessary conditions for the optimality equation in average reward Markov decision processes, Appl. Math. Optim. 19 (1989) 97–112.
R. Cavazos-Cadena, Recent results on conditions for the existence of average optimal stationary policies, Ann. Oper. Res. 28 (1991) 3–26.
M.H. Chang, Martingale dynamics and optimal routing in a network, Appl. Math. Comp. (1988)309–327.
X. Chao and H. Chen, Optimal intensity control for tandem queues with blocking, Faculty of Commerce and Business Administration, University of British Columbia (1990).
H. Chen, P. Yang and D. Yao, Control and scheduling in a two-station queueing network: optimal policies, heuristics, and conjectures, Technical report, Department of Industrial Engineering and Operations Research, Columbia University (1991).
T. Crabill, Optimal control of a service facility with variable exponential service time and constant arrival rate, Manag. Sci. 18 (1972) 560–566.
E. Davis, Optimal control of arrivals to a two-server queueing system with separate queues, Ph.D. dissertation, Program in Operations Research, N.C. State University, Raleigh (1977).
A. Ephremides, P. Varaiya and J. Walrand, A simple dynamic routing problem, IEEE Trans. Auto. Control AC-25 (1980) 690–693.
T.M. Farrar, Optimal use of an extra server in a two station queueing network, IEEE Trans. Auto. Control AC-37 (1992).
T.M. Farrar, Resource allocation in systems of queues, Ph.D. dissertation, University of Cambridge (1992).
W. Farrell, Optimal switching policies in a non-homogeneous exponential queueing system, Ph.D. dissertation, Graduate School of Management, University of California at Los Angeles (1976).
G. Foschini, On heavy traffic diffusion analysis and dynamic routing in packet-switched networks,Computer Performance, eds. K.M. Chandy and M. Reiser (North-Holland, 1977) pp. 499–513.
G. Foschini and J. Salz, A basic dynamic routing problem and diffusion, IEEE Trans. Commun. COM-26 (1978) 320–327.
H. Ghoneim, Optimal control of arrivals to a network of two queues in series, Ph.D. dissertation, Programm Operations Research, N.C. State University, Raleigh (1980).
H. Ghoneim and S. Stidham, Optimal control of arrivals to two queues in series, Euro. J. Oper. Res. 21 (1985) 399–409.
J.C. Gittins, Bandit processes and dynamic allocation indices, J. Roy. Statist. Soc. B41 (1979) 148–164.
P. Glasserman and D. Yao, Monotone optimal control of permutable GSMPs, Technical Report, IE/OR Department, Columbia University, New York.
B. Hajek, Optimal control of two interacting service stations, IEEE Trans. Auto. Control AC-29(1984) 491–499.
B. Hajek, Extremal splittings of point processes, Math. Oper. Res. 10 (1985) 543–556.
R. Hariharan, V.G. Kulkarni and S. Stidham, Optimal control of admission and routing to two parallel infinite-server queues,Proc. 29th IEEE Conf. on Decision and Control (1990).
R. Hariharan, V.G. Kulkarni and S. Stidham, A survey of research relevant to virtual-circuit routing in telecommunication networks, Preprint, Department of Operations Research, University of North Carolina at Chapel Hill (1990).
R. Hariharan, M.S. Moustafa and S. Stidham, Scheduling in a multi-class queueing network, Department of Operations Research, University of North Carolina, Chapel Hill (1991).
J.M. Harrison, Dynamic scheduling of a multi-class queue: discount optimality, Oper. Res. 23 (1975) 270–282.
J.M. Harrison, A priority queue with discounted linear costs, Oper. Res. 23 (1975) 260–269.
J.M. Harrison,Brownian Motion and Stochastic Flow Systems (Wiley, New York, 1985).
J.M. Harrison, Brownian models of queueing networks with heterogeneous customers, presented at theIMA Workshop on Stochastic Differential Systems, Minneapolis, MI (1986).
J.M. Harrison and L.M. Wein, Scheduling a two-station multiclass closed queueing network in heavy traffic, Oper. Res. (1987), to appear.
A. Hordijk and G. Koole, Note on the optimality of the generalized shortest queue policy, Prob. Eng. Inf. Sci. (1992), to appear.
D.J. Houck, Comparison of policies for routing customers of parallel queueing systems, Oper. Res. 35 (1987) 306–310.
P.K. Johri, Optimality of the shortest line discipline with state-dependent service times, Euro. J. Oper. Res. 41 (1990) 157–161.
G.P. Klimov, Time sharing systems, Theory Prob. Appl. 9 (1974) 532–551.
K.R. Krishnan, Joining the right queue: a Markov decision rule,Proc. 26th IEEE Conf. on Decision and Control (1987) pp. 1863–1868.
C.N. Laws and G.M. Louth, Dynamic scheduling of a four-station queueing network, Prob. Eng. Inf. Sci.4 (1990) 131–156.
T. Lehtonen, On the optimality of the shortest-line discipline, Ph.D. dissertation, Helsinki School of Economics (1981).
W. Lin and P.R. Kumar, Optimal control of a queueing system with two heterogeneous servers, IEEE Trans. Auto. Control AC-29 (1984) 696–703.
Z. Liu and P. Nain, Optimal scheduling in some multi-queue single-server systems, IEEE Trans. Auto. Control AC-37 (1992).
R. Menich and R. Serfozo, Optimality of shortest-queue routing for dependent service stations, Queueing Systems 9 (1991) 403–418.
M.S. Moustafa, Scheduling in a multi-class network, Ph.D. dissertation, Program in Operations Research, North Carolina State University, Raleigh (1987).
P. Nain, Interchange arguments for classical scheduling problems in queues, Syst. Control Lett. 12 (1989) 177–184.
P. Nain, P. Tsoucas and J. Walrand, Interchange arguments in stochastic scheduling, J. Appl. Prob. 27 (1989) 815–826.
P.E. Sarachik and U. Ozgüner, On decentralized dynamic routing for congested traffic networks, IEEE Trans. Auto. Control AC-27 (1982) 1233–1238.
M. Schäl, Conditions for optimality in dynamic programming and for the limit of n-stage optimal policies to be optimal, Z. Wahrscheinlichkeitstheorie verw. Geb. 32 (1975) 179–196.
L. Sennott, Average cost optimal stationary policies in infinite state Markov decision processes, Oper. Res. 37 (1989) 626–633.
L. Sennott, Average cost semi-Markov decision processes and the control of queueing systems, Prob. Eng. Inf. Sci. 3 (1989) 247–272.
S. Shenker and A. Weinrib, The optimal control of heterogeneous queueing systems: a paradigm for load-sharing and routing, IEEE Trans. Comp. C-38 (1989) 1724–1735.
S. Stidham, Optimal control of admission to a queueing system, IEEE Trans. Auto. Control 30 (1985) 705–713.
S. Stidham, Scheduling, routing, and flow control in stochastic networks,Stochastic Differential Systems, Stochastic Control Theory and Applications, eds. W. Fleming and P.L. Lions, IMA vol. 10 (1988) pp. 529–561.
D.W. Tcha and S.R. Pliska, Optimal control of single-server queueing networks and multiclassM/G/1 queues with feedback, Oper. Res. 25 (1977) 248–257.
D. Topkis, Minimizing a submodular function on a lattice, Oper. Res. 26 (1978) 305–321.
P. Varaiya, J. Walrand and C. Buyukkoc, Extensions of the multiarmed bandit problem: the discounted case, IEEE Trans. Auto. Control AC-30 (1985) 426–439.
M. Veatch and L. Wein, Monotone control of queueing and production/inventory systems, Preprint, Operations Research Center, MIT (1991).
I. Viniotis and A. Ephremides, An optimization problem in a multiserver queue,Proc. 23rd Allerton Conf. on Communications, Control, and Computing (1985) pp. 555–563.
J. Walrand, A note on “Optimal control of a queueing system with heterogeneous servers”, Syst. Control Lett. 4 (1984) 131–134.
J. Walrand,An Introduction to Queueing Networks (Prentice-Hall, Englewood Cliffs, NJ, 1988).
R. Weber, On the optimal assignment of customers to parallel servers, J. Appl. Prob. 15 (1978) 406–413.
R. Weber and S. Stidham, Control of service rates in networks of queues, Adv. Appl. Prob. 24 (1987) 202–218.
L.M. Wein, Asymptotically optimal scheduling of a two-station multi-class queueing network, Technical Report, Sloan School of Management, M.I.T. (1987).
L.M. Wein, Reducing the variance of sojourn times in multiclass queueing systems, Technical Report, Sloan School of Management, M.I.T. (1989).
W. Whitt, Deciding which queue to join; some counterexamples, Oper. Res. 34 (1986) 55–62.
P. Whittle, Multi-armed bandits and the Gittins index, J. Roy. Statist. Soc. B42 (1980) 143–149.
P. Whittle,Optimization over Time: Dynamic Programming and Stochastic Control, Vol. 1 (Wiley, New York, 1982).
P. Whittle,Optimization over Time: Dynamic Programming and Stochastic Control, Vol. 2 (Wiley, New York, 1983).
W. Winston, Optimality of the shortest-line discipline, J. Appl. Prob. 14 (1977) 181–189.
P. Yang, H. Chen and D. Yao, Optimal control and scheduling in a multi-class queueing network: results and conjectures, SIAM Conf. Proc., New Orleans (1990).
T.K. Yum and M. Schwartz, The join-biased-queue rule and its application to routing in computer communication networks, IEEE Trans. Commun. COM-29 (1981) 505–511.
Author information
Authors and Affiliations
Additional information
This research was partially supported by the National Science Foundation under Grant No. DDM-8719825. The Government has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research was also partially supported by the C.I.E.S. (France), while the author was on leave at INRIA, Sophia-Antipolis, 1991–92.
Rights and permissions
About this article
Cite this article
Stidham, S., Weber, R. A survey of Markov decision models for control of networks of queues. Queueing Syst 13, 291–314 (1993). https://doi.org/10.1007/BF01158935
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01158935