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

Dynamic routing and jockeying controls in a two-station queueing system

Part of: Computer system organization Operations research and management science

Published online by Cambridge University Press:  01 July 2016

Susan H. Xu  and
Y. Quennel Zhao
Susan H. Xu*
Affiliation:
Pennsylvania State University
Y. Quennel Zhao*
Affiliation:
University of Winnipeg
*
∗ Postal address: Department of Management Science and Information Systems, The Smeal College of Business Administration. The Pennsylvania State University, Beam Business Administration Building, University Park. PA 16802-1913, USA.
∗∗ Postal address: Department of Mathematics and Statistics. University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba. Canada R3B 2E9.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper studies optimal routing and jockeying policies in a two-station parallel queueing system. It is assumed that jobs arrive to the system in a Poisson stream with rate λand are routed to one of two parallel stations. Each station has a single server and a buffer of infinite capacity. The service times are exponential with server-dependent rates, μ1 and μ2. Jockeying between stations is permitted. The jockeying cost is cij when a job in station i jockeys to station j, i ≠ j. There is no cost when a new job joins either station. The holding cost in station j is hj, h1 ≦ h2, per job per unit time. We characterize the structure of the dynamic routing and jockeying policies that minimize the expected total (holding plus jockeying) cost, for both discounted and long-run average cost criteria. We show that the optimal routing and jockeying controls are described by three monotonically non-decreasing functions. We study the properties of these control functions, their relationships, and their asymptotic behavior. We show that some well-known queueing control models, such as optimal routing to symmetric and asymmetric queues, preemptive or non-preemptive scheduling on homogeneous or heterogeneous servers, are special cases of our system.

Keywords

PARALLEL QUEUESROUTINGJOCKEYINGSCHEDULINGDYNAMIC PROGRAMMINGSTOCHASTIC COUPLINGASYMPTOTIC LIMIT

MSC classification

Primary: 90B35: Scheduling theory, deterministic
Secondary: 68M20: Performance evaluation; queueing; scheduling
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 28 , Issue 4 , December 1996 , pp. 1201 - 1226
Copyright
Copyright © Applied Probability Trust 1996 

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

Abdel-Gawad, E. F. (1984) Optimal control of arrivals and routing in a network of queues. PhD dissertation. N.C. State University, Raleigh.Google Scholar
Adan, I. J. B. F., Wessels, J. and Zijm, W. H. M. (1991) Analysis of the asymmetric shortest queue problem with threshold jockeying. Stoch. Models 7, 615–628.Google Scholar
Borkar, V. S. (1988) Control of Markov chains with long-run average cost criterion. In Stochastic Differential Systems, Stochastic Control Theory and Applications 10. ed. Fleming, W. and Lions, P. L. Springer, Berlin. pp. 57–77.Google Scholar
Borkar, V. S. (1989) Control of Markov chains with long-run average cost criterion: the dynamic programming equations. SIAM J. Control Optim. 27, 642–657.Google Scholar
Davis, E. (1977) Optimal control of arrivals to a two-server queueing system with separate queues. PhD dissertation. N.C. State University, Raleigh.Google Scholar
Disney, R. L. and Mitchell, W. E. (1971) A solution for queues with instantaneous jockeying and other customer selection rules. Naval Res. Logist. 17, 315–325.Google Scholar
Elsayed, E. A. and Bastani, A. (1985) General solutions of jockeying problem. Euro. J. Operat. Res. 22, 387–396.Google Scholar
Farrar, T. M. (1992) Optimal use of an extra server in a two station queueing network. IEEE Trans. Auto. Control AC–38, 1296–1299.Google Scholar
Haight, F. A. (1958) Two queues in parallel. Biometrika 45, 401–410.Google Scholar
Hajek, B. (1984) Optimal control of two interacting service stations. IEEE Trans. Aut. Control AC–29, 491–499.Google Scholar
Hordijk, A. and Koole, G. (1990) On the optimality of the generalized shortest queue policy. Prob. Eng. Inf. Sci. 4, 477–488.Google Scholar
Kao, E. P. C. and Lin, C. (1990) A matrix-geometric solution of the jockeying problem. Euro. J. Operat. Res. 44, 67–74.Google Scholar
Lin, W. and Kumar, P. R. (1984) Optimal control of a queueing system with two heterogeneous servers. IEEE Trans. Aut. Control AC–29, 211–216.Google Scholar
Lippman, S. A. (1975) Applying a new device in the optimization of exponential queueing systems. Operat. Res. 23, 687–710.Google Scholar
Nelson, R. D. and Philips, T. K. (1989) An approximation to the response time for shortest queue routing. Perf. Eval. Rev. 17, 181–189.CrossRefGoogle Scholar
Ross, S. (1983) Introduction to Stochastic Dynamic Programming. Academic Press, New York.Google Scholar
Stidham, S. Jr and Weber, R. (1993) A survey of Markov decision models for control of networks of queues. QUESTA 13, 291–314.Google Scholar
Stoyan, D. (1983) Comparison Methods for Queues and Other Stochastic Models. Wiley, New York.Google Scholar
Walrand, J. (1984) A note on ‘optimal control of a queueing system with two heterogeneous servers’. Syst. Cont. Lett. 4, 131–134.Google Scholar
Walrand, J. (1989) Introduction to Queueing Netowrks. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Weber, R. (1978) On the optimal assignment of customers to parallel servers. J. Appl. Prob. 15, 406–413.Google Scholar
Whitt, W. (1986) Deciding which queue to join; some counterexamples. Operat. Res. 34, 53–62.Google Scholar
Winston, W. (1977) Optimality of the shortest-line discipline. J. Appl. Prob. 14, 181–189.Google Scholar
Xu, S. H. (1994) A duality approach to admission and scheduling controls of queues. QUESTA 18, 273–300.Google Scholar
Xu, S. H. and Chen, H. (1992) On the asymptote of the optimal routing policy for two service stations. IEEE Trans. Aut. Control 38, 187–189.Google Scholar
Xu, S. H., Righter, R. and Shanthikumar, J. G. (1992) Optimal dynamic assignment of customers to heterogeneous servers in parallel. Operat. Res. 41, 1139–1148.Google Scholar
Zhao, Y. Q. and Grassmann, W. K. (1990) A solution of the shortest queue model with jockeying in terms of traffic intensity p. Naval Res. Logist. 37, 773–787.Google Scholar
Zhao, Y. Q. and Grassmann, W. K. (1995) Queueing analysis of a jockeying model. Operat. Res. 43, 520–529.Google Scholar