SpringerLink
Log in

On computing average cost optimal policies with application to routing to parallel queues

  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

The Approximating Sequence Method for computation of average cost optimal stationary policies in denumerahle state Markov decision chains, introduced in Sennott (1994), is reviewed. New methods for verifying the assumptions are given. These are useful for models with multidimensional state spaces that satisfy certain mild structural properties. The results are applied to four problems in the optimal routing of packets to parallel queues. Numerical results are given for one of the models.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Arapostathis A, Borkar V, Fernandez-Gaucherand E, Ghosh M, Marcus S (1993) Discrete-time controlled Markov processes with average cost criterion: A survey. SIAM J Control Optim 31:282–344

    Google Scholar 

  • Bertsekas D (1987) Dynamic programming. Prentice-Hall, Englewood Cliffs New Jersey

    Google Scholar 

  • Ephremides A, Varaiya P, Walrand J (1980) A simple dynamic routing problem. IEEE Trans Auto Control 25:690–693

    Google Scholar 

  • Hajek B (1984) Optimal control of two interacting service stations. IEEE Trans Auto Control 29:491–499

    Google Scholar 

  • Puterman M (1994) Markov decision processes. John Wiley & Sons, New York

    Google Scholar 

  • Rosberg Z (1986) Deterministic routing to buffered channels. IEEE Trans Comm 34:504–507

    Google Scholar 

  • Sennott L (1989) Average cost optimal stationary policies in infinite state Markov decision processes with unbounded costs. Oper Res 37:626–633

    Google Scholar 

  • Sennott L (1994) The computation of average optimal policies in denumerable state Markov decision chains. To appear, Adv Appl Prob

  • Sennott L (1995) Another set of conditions for average optimality in Markov control processes. Sys Control Lett 24:147–151

    Google Scholar 

  • Stidham S Jr, Weber R (1993) A survey of Markov decision models for control of networks of queues. Queueing Sys 13:291–314

    Google Scholar 

  • Winston W (1977) Optimality of the shortest line discipline. J Appl Prob 14:181–189

    Google Scholar 

  • Weber R (1978) On the optimal assignment of customers to parallel servers. J. Appl Prob 15:406–413

    Google Scholar 

  • Xu S, Righter R, Shanthikumar G (1992) Optimal dynamic assignment of customers to heterogeneous servers in parallel. Oper Res 40:1126–1138

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics 4520, Illinois State University, 61790-4520, Normal, IL, USA

    Linn I. Sennott

Authors
  1. Linn I. Sennott
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sennott, L.I. On computing average cost optimal policies with application to routing to parallel queues. Mathematical Methods of Operations Research 45, 45–62 (1997). https://doi.org/10.1007/BF01194247

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01194247

Key words

Search

Navigation