Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-25T17:13:31.825Z Has data issue: false hasContentIssue false
  • English
  • Français

Customer routing to different servers with complete information

Published online by Cambridge University Press:  01 July 2016

Zvi Rosberg  and
Parviz Kermani
Zvi Rosberg*
Affiliation:
Technion—Israel Institute of Technology
Parviz Kermani*
Affiliation:
IBM Thomas J. Watson Research Center
*
∗Postal address: Dept. of Computer Science, Technion—IIT, Haifa 32000, Israel. Research was done while this author was with IBM T. J. Watson Research center.
∗∗Postal address: IBM T. J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider a queueing system having n exponential servers, each with its own queue and service rate. Customers arrive according to a Poisson process with rate λ, and upon arrival each customer must be routed to some server's queue. No jockeying amongst the queues is allowed and each server serves its queue according to a first-come-first-served discipline.

Each server i, 1 ≦ i ≦ n, provides service with a state-dependent rate μ(i)(k), k = 0, 1, …. In addition, at every queue i, there is a deterministic holding cost which occurs at rate h(i)(k) while there are k customers at the queue.

An admissible routing policy is a policy that assigns each arriving customer to one of the queues. A decision at time t may be randomized and dependent on the queue lengths and decisions till time t. An optimal routing policy is an admissible policy that minimizes the long-run average holding cost.

In this study, we bound the optimal cost from below, by considering an ideal system, where each server optimally selects a given proportion of customers, irrespective of other servers' selections. From this ideal system we construct a class of admissible routing policies, the overflow routing class, that approximates the ideal situation for each server. Finally, we evaluate the policies and compare them to the lower bound.

Keywords

EXPONENTIAL QUEUESPARALLEL SERVERSFLOW CONTROLMARKOV DECISION PROCESSESOVERFLOW QUEUES
Type
Research Article
Information
Advances in Applied Probability , Volume 21 , Issue 4 , December 1989 , pp. 861 - 882
Copyright
Copyright © Applied Probability Trust 1989 

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

[1] Beutler, F. J. and Ross, K. W. (1986) Time-average optimal constrained semi-Markov decision processes. Adv. Appl. Prob. 18, 341–359.CrossRefGoogle Scholar
[2] Bovopoulos, A. D. and Lazar, A. A. (1985) Optimal Routing and Flow Control of a Network of Parallel Processors, Technical Report, Columbia University.Google Scholar
[3] Chandy, K. M., Herzog, U. and Woo, L. (1975) Parametric analysis of queueing networks. IBM J. Res. Develop. 19, 36–42.Google Scholar
[4] Denardo, E. V. (1982) Dynamic Programming: Models and Applications. Prentice-Hall, Englewood Cliffs, N.J.Google Scholar
[5] Ephremides, A., Varaiya, P. and Walrand, J. (1980) A simple dynamic routing problem. IEEE Trans. Autom. Control 25, 690–693.Google Scholar
[6] Gelenbe, E. and Mitrani, I. (1980) Analysis and Synthesis of Computer Systems. Academic Press, New York.Google Scholar
[7] Hajek, B. (1985) External splitting of point processes. Math. Operat. Res. 10, 543–556.Google Scholar
[8] Hajek, B. (1984) Optimal control of two interacting service stations. IEEE Trans. Autom. Control 29, 491–499.CrossRefGoogle Scholar
[9] Krishnan, K. R. (1987) Joining the right queue: A Markov decision rule. Proc. 26th CDC, 1863–1868.CrossRefGoogle Scholar
[10] Lippman, S. A. (1973) Semi-Markov decision processes with unbounded rewards. Management Sci. 29, 717–731.Google Scholar
[11] Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models. John Hopkins University Press, Baltimore, MD.Google Scholar
[12] Neuts, M. F. and Kumar, S. (1982) Algorithmic solution of some queues with overflows. Management Sci. 28, 925–935.Google Scholar
[13] Rosberg, Z. (1986) Deterministic routing to buffered channels. IEEE Trans. Comm. 34, 604–507.CrossRefGoogle Scholar
[14] Rosberg, Z. (1981) A note on the ergodicity of Markov chains. J. Appl. Prob. 18, 112–121.CrossRefGoogle Scholar
[15] Rosberg, Z. and Kermani, P. (1988) Customer routing to different servers with complete information. Technical Report, RC 13765, IBM T. J. Watson Res. Ctr. Google Scholar
[16] Rosberg, Z. and Towsley, D. (1985) Customer routing to parallel servers with different rates. IEEE Trans. Autom. Control 30, 1140–1143.CrossRefGoogle Scholar
[17] Schal, M. (1975) Condition for optimality in dynamic programming and for the limit of n-stage optimal policies to be optimal. Z Warscheinlichkeitsth. 32, 179–196.Google Scholar
[18] Schwartz, M. (1981) Routing and flow control in data networks. In New Concepts in Multi-user Communications, ed. Skwirzynski, J. K., NATO Advanced Study Institute, Series E: Applied Science 43.Google Scholar
[19] Weber, R. R. (1978) On the optimal assignment of customers to parallel servers. J. Appl. Prob. 15, 406–413.Google Scholar
[20] Whitt, W. (1986) Deciding which queue to join: some counterexamples. Operat. Res. 34, 55–62.Google Scholar
[21] Winston, W. L. (1977) Optimality of the shortest line discipline. J. Appl. Prob. 14, 181–189.Google Scholar