Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T19:41:56.684Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal control of queueing networks: an approach via fluid models

Part of: Stochastic systems and control Computer system organization Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Nicole Bäuerle
Nicole Bäuerle*
Affiliation:
University of Ulm
*
∗ Postal address: Department of Mathematics VII, University of Ulm, D-89069 Ulm, Germany. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a general control problem for networks with linear dynamics which includes the special cases of scheduling in multiclass queueing networks and routeing problems. The fluid approximation of the network is used to derive new results about the optimal control for the stochastic network. The main emphasis lies on the average-cost criterion; however, the β-discounted as well as the finite-cost problems are also investigated. One of our main results states that the fluid problem provides a lower bound to the stochastic network problem. For scheduling problems in multiclass queueing networks we show the existence of an average-cost optimal decision rule, if the usual traffic conditions are satisfied. Moreover, we give under the same conditions a simple stabilizing scheduling policy. Another important issue that we address is the construction of simple asymptotically optimal decision rules. Asymptotic optimality is here seen with respect to fluid scaling. We show that every minimizer of the optimality equation is asymptotically optimal and, what is more important for practical purposes, we outline a general way to identify fluid optimal feedback rules as asymptotically optimal. Last, but not least, for routeing problems an asymptotically optimal decision rule is given explicitly, namely a so-called least-loaded-routeing rule.

Keywords

Stochastic networkaverage-cost optimality equationasymptotic optimalitydeterministic control problemstability

MSC classification

Primary: 90B15: Network models, stochastic 93E20: Optimal stochastic control
Secondary: 68M20: Performance evaluation; queueing; scheduling
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 34 , Issue 2 , June 2002 , pp. 313 - 328
Copyright
Copyright © Applied Probability Trust 2002 

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

Footnotes

Work supported in part by a grant from the University of Ulm.

References

Alanyali, M. and Hajek, B. (1998). Analysis of simple algorithms for dynamic load balancing. Math. Operat. Res. 22, 840–871.CrossRefGoogle Scholar
Altman, E., Koole, G. and Jiménez, T. (2001). On the comparison of queueing systems with their fluid limits. Preprint. Prob. Eng. Inf. Sci. 15, 165–178.Google Scholar
Asmussen, S. (1987). Applied Probability and Queues. John Wiley, Chichester.Google Scholar
Atkins, D. and Chen, H. (1995). Performance evaluation of scheduling control of queueing networks: fluid model heuristics. Queueing Systems 21, 391–413.CrossRefGoogle Scholar
Avram, F., Bertsimas, D. and Ricard, M. (1995). Fluid models of sequencing problems in open queueing networks: an optimal control approach. In Stochastic Networks (IMA Vol. Math. Appl. 71), eds Kelly, F. P. and Williams, R. J., Springer, New York, pp. 199–234.Google Scholar
Bäuerle, N., (1999). How to improve the performance of ATM multiplexers. Operat. Res. Lett. 24, 81–89.CrossRefGoogle Scholar
Bäuerle, N., (2000). Asymptotic optimality of tracking-policies in stochastic networks. Ann. Appl. Prob. 10, 1065–1083.CrossRefGoogle Scholar
Bäuerle, N., (2001). Discounted stochastic fluid programs. To appear in Math. Operat. Res. 26, 401–420.Google Scholar
Bäuerle, N. and Rieder, U. (2000). Optimal control of single-server fluid networks. Queueing Systems 35, 185–200.Google Scholar
Chen, H. (1995). Fluid approximations and stability of multiclass queueing networks: work-conserving disciplines. Ann. Appl. Prob. 5, 637–665.Google Scholar
Chen, H. and Xu, S. (1993). On the asymptote of the optimal routing policy for two service stations. IEEE Trans. Automatic Control 38, 187–189.Google Scholar
Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Prob. 5, 49–77.Google Scholar
Dai, J. G. (1999). Stability of Fluid and Stochastic Processing Networks (MaPhySto Miscellanea 9). Centre for Mathematical Physics and Stochastics, Aarhus.Google Scholar
Dai, J. G. and Williams, R. J. (1995). Existence and uniqueness of semimartingale reflecting Brownian motions in convex polyhedrons. Theory Prob. Appl. 40, 1–40.Google Scholar
Gajrat, A. and Hordijk, A. (2000a). Fluid approximation of a controlled multiclass tandem network. Preprint. Queueing Systems 35, 349–380.Google Scholar
Gajrat, A. and Hordijk, A. (2000b). Optimal service control of multiclass fluid tandem networks. Preprint, Leiden University.Google Scholar
Gajrat, A. and Hordijk, A. (2000c). Synthesis of the optimal control problem for fluid networks. Preprint, Leiden University.Google Scholar
Hajek, B. (1984). Optimal control of two interacting service stations. IEEE Trans. Automatic Control 29, 491–499.CrossRefGoogle Scholar
Harrison, J. M. (1996). The BIGSTEP approach to flow management in stochastic processing networks. In Stochastic Networks: Stochastic Control Theory and Applications (R. Statist. Soc. Lecture Notes 4), eds Kelly, F., Zachary, S. and Ziedins, I., Clarendon Press, Oxford, pp. 57–90.Google Scholar
Hordijk, A. and Koole, G. (1992). On the assignment of customers to parallel queues. Prob. Eng. Inf. Sci. 6, 495–511.CrossRefGoogle Scholar
Kitaev, M. and Rykov, V. (1995). Controlled Queueing Systems. CRC Press, Boca Raton, FL.Google Scholar
Luo, X. and Bertsimas, D. (1998). A new algorithm for state-constrained separated continuous linear programs. SIAM J. Control Optimization 37, 177–210.Google Scholar
Maglaras, C. (1999). Dynamic scheduling in multiclass queueing networks: stability under discrete-review policies. Queueing Systems 31, 171–206.CrossRefGoogle Scholar
Maglaras, C. (2000). Discrete-review policies for scheduling stochastic networks: trajectory tracking and fluid-scale asymptotic optimality. Preprint. Ann. Appl. Prob. 10, 897–929.Google Scholar
Meyn, S. P. (1997a). The policy iteration algorithm for average reward Markov decision processes with general state space. IEEE Trans. Automatic Control 42, 1663–1679.Google Scholar
Meyn, S. P. (1997b). Stability and optimization of queueing networks and their fluid models. In Mathematics of Stochastic Manufacturing Systems (Lectures Appl. Math. 33), eds Yin, G. G. and Zhang, Q., American Mathematical Society, Providence, RI, pp. 175–199.Google Scholar
Meyn, S. P. (2001). Sequencing and routing in multiclass queueing networks I: Feedback regulation. Preprint. SIAM J. Control Optimization 40, 741–776.Google Scholar
Ott, T. J. and Shanthikumar, J. G. (1996). Discrete storage processes and their Poisson flow and fluid flow approximations. Queueing Systems 24, 101–136.Google Scholar
Pullan, M. C. (1995). Forms of optimal solutions for separated continuous linear programs. SIAM J. Control Optimization 33, 1952–1977.Google Scholar
Seierstad, A. and Sydsæter, K. (1987). Optimal Control Theory with Economic Applications. North-Holland, Amsterdam.Google Scholar
Sennott, L. I. (1989). Average cost optimal stationary policies in infinite state Markov decision processes with unbounded costs. Operat. Res. 37, 626–633.CrossRefGoogle Scholar
Sennott, L. I. (1998). Stochastic Dynamic Programming and the Control of Queues. John Wiley, New York.Google Scholar
Sethi, S. P. and Zhang, Q. (1994). Hierarchical Decision Making in Stochastic Manufacturing Systems. Birkhäuser, Boston, MA.Google Scholar
Stidham, S. and Weber, R. (1993). A survey of Markov decision models for control of networks of queues. Queueing Systems 13, 291–314.Google Scholar
Veatch, M. (2001). Fluid analysis of arrival routing. Preprint. IEEE Trans. Automat. Control 46, 1254–1257.Google Scholar
Weiss, G. (1996). Optimal draining of fluid re-entrant lines: some solved examples. In Stochastic Networks: Stochastic Control Theory and Applications (R. Statist. Soc. Lecture Notes 4), eds Kelly, F., Zachary, S. and Ziedins, I., Clarendon Press, Oxford, pp. 19–34.Google Scholar
Williams, R. J. (1998). Some recent developments for queueing networks. In Probability Towards 2000 (Lecture Notes Statist. 128), eds Accardi, L. and Heyde, C. C., Springer, New York, pp. 340–356.Google Scholar