Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-29T21:01:33.206Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Assignment of Customers to Parallel Queues

Published online by Cambridge University Press:  27 July 2009

Arie Hordijk  and
Ger Koole
Arie Hordijk
Affiliation:
Department of Mathematics and Computer Science University of Leiden, P.O. Box 9512 2300 RA Leiden, The Netherlands
Ger Koole
Affiliation:
Department of Mathematics and Computer Science University of Leiden, P.O. Box 9512 2300 RA Leiden, The Netherlands
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper considers routing to parallel queues in which each queue has its own single server and service times are exponential with nonidentical parameters. We give conditions on the cost function such that the optimal policy assigns customers to a faster queue when that server has a shorter queue. The queues may have finite buffers, and the arrival process can be controlled and can depend on the state and routing policy. Hence our results on the structure of the optimal policy are also true when the assigning control is in the “last” node of a network of service centers. Using dynamic programming we show that our optimality results are true in distribution.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 6 , Issue 4 , October 1992 , pp. 495 - 511
Copyright
Copyright © Cambridge University Press 1992

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

Asmussen, S. & Koole, G. (1991). Marked point processes as limits of Markovian arrival streams. Technical Report TW-91−04, University of Leiden, Leiden, The Netherlands.Google Scholar
Daley, D.J. (1987). Certain optimality properties of the first-come first-served discipline for G∣G∣s queues. Stochastic Processes and Their Applications 25: 301–308.Google Scholar
Derman, C., Lieberman, G.J., & Ross, S.M. (1980). On the optimal assignment of servers and a repairman. Journal of Applied Probability 17: 577–581.Google Scholar
Hordijk, A. & Koole, G. (1990). On the optimality of the generalized shortest queue policy. Probability in the Engineering and Informational Sciences 4: 477–487.CrossRefGoogle Scholar
Hordijk, A. & Koole, G. (1992). On the shortest queue policy for the tandem parallel queue. Probability in the Engineering and Informational Sciences 6: 63–79.Google Scholar
Hordijk, A. & Koole, G. (1992). The μc-rule is not optimal in the second node of the tandem queue; a counterexample. Advances in Applied Probability 24: 234–237.CrossRefGoogle Scholar
Hordijk, A. & Koole, G. (1992). On the optimality of LEPT and μc rules for parallel processors and dependent arrival processes. Technical Report TW-92−01, University of Leiden, Leiden, The Netherlands.Google Scholar
Hordijk, A. & Van, der Duyn Schouten F. (1985). Markov decision drift processes; conditions for optimality obtained by discretization. Mathematics of Operations Research 10: 160–173.Google Scholar
Houck, D.J. (1987). Comparison of policies for routing customers to parallel queueing systems. Operations Research 35: 306–310.Google Scholar
Koole, G. (1991). Assigning multiple customer classes to parallel servers. Technical Report TW-91−07, University of Leiden, Leiden, The Netherlands.Google Scholar
Koole, G. (1992). Stochastic scheduling and dynamic programming. Ph.D. thesis, University of Leiden, Leiden, The Netherlands.Google Scholar
Marshall, A.W. & Olkin, I. (1979). Inequalities: Theory of majorizalion and its applications. New York: Academic Press.Google Scholar
Menich, R. & Serfozo, R.F. (1991). Optimality of routing and servicing in dependent parallel processing systems. Queueing Systems, Theory and Applications 9: 403–418.CrossRefGoogle Scholar
Nobel, R. & Tijms, H.C. (1990). Optimal routing of customers to parallel service groups. Memorandum 90−47, Vrije Universiteit Amsterdam.Google Scholar
Pinedo, M. & Rammouz, E. (1988). A note on stochastic scheduling on a single machine subject to breakdown and repair. Probability in the Engineering and Informational Sciences 2: 41–49.CrossRefGoogle Scholar
Ross, S.M. (1983). Introduction to stochastic dynamic programming. New York: Academic Press.Google Scholar
Ross, S.M. (1983). Stochastic processes. New York: Wiley.Google Scholar
Seth, K. (1977). Optimal service policies, just after idle periods, in two-server heterogeneous queueing systems. Operations Research 25: 356–360.CrossRefGoogle Scholar
Shenker, S. & Weinrib, A. (1989). The optimal control of heterogeneous queueing systems: A paradigm for load-sharing and routing. IEEE Transactions on Computers 38: 1724–1735.CrossRefGoogle Scholar
Sobel, M.J. (1990). Throughput maximization in a loss queueing system with heterogeneous servers. Journal of Applied Probability 27: 693–700.CrossRefGoogle Scholar
Sobel, M.J. & Srivastava, C. (1991). Full-service policy optimality with heterogeneous servers (working paper).Google Scholar
Stoyan, D. (1983). Comparison methods for queues and other stochastic models. Chichester: Wiley.Google Scholar
Towsley, D., Sparaggis, P.D., & Cassandras, C.G. (1992). Stochastic ordering properties and optimal routing control for a class of finite capacity queueing systems. IEEE Transactions on Automatic Control (to appear).Google Scholar
van, Dijk N.M. (1988). On the finite horizon Bellman equation for controlled Markov jump models with unbounded characteristics: Existence and approximations. Stochastic Processes and Their Applications 28: 141–157.Google Scholar
van, Moorsel A. & de, Vries E. (1989). Optimale toewijzingsstrategieën bij eenvoudige netwerken van wachtrijen. Master's thesis, University of Leiden, Leiden, The Netherlands (in Dutch).Google Scholar
Walrand, J. (1988). An introduction to queueing networks. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Winston, W. (1977). Optimality of the shortest line discipline. Journal of Applied Probability 14: 181–189.Google Scholar