Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-28T04:21:48.564Z Has data issue: false hasContentIssue false
  • English
  • Français

Extremal properties of the shortest/longest non-full queue policies in finite-capacity systems with state-dependent service rates

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

P. D. Sparaggis ,
D. Towsley  and
C. G. Cassandras
P. D. Sparaggis*
Affiliation:
University of Massachusetts
D. Towsley*
Affiliation:
University of Massachusetts
C. G. Cassandras*
Affiliation:
University of Massachusetts
*
∗ Postal address: Department of Electrical and Computer Engineering, University of Massachusetts, Amherst MA 01002, USA.
∗∗ Postal address: Department of Computer and Information Science, University of Massachusetts, Amherst MA 01002, USA.
∗ Postal address: Department of Electrical and Computer Engineering, University of Massachusetts, Amherst MA 01002, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of routing jobs to parallel queues with identical exponential servers and unequal finite buffer capacities. Service rates are state-dependent and non-decreasing with respect to queue lengths. We establish the extremal properties of the shortest non-full queue (SNQ) and the longest non-full queue (LNQ) policies, in systems with concave/convex service rates. Our analysis is based on the weak majorization of joint queue lengths which leads to stochastic orderings of critical performance indices. Moreover, we solve the buffer allocation problem, i.e. the problem of how to distribute a number of buffers among the queues. The two optimal allocation schemes are also ‘extreme', in the sense of capacity balancing. Some extensions are also discussed.

Keywords

OPTIMAL ROUTINGBUFFER ALLOCATIONWEAK MAJORIZATIONSTATE-DEPENDENT SERVICE RATES

MSC classification

Primary: 60K25: Queueing theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 30 , Issue 1 , March 1993 , pp. 223 - 236
Copyright
Copyright © Applied Probability Trust 1993 

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

Partially supported by the Office of Naval Research under contract N00014-87-0304 and by the National Science Foundation under Grant ECS-8801912.

Partially supported by the Office of Naval Research under contract N00014-87-0304.

References

[1] Ephremides, A., Varaiya, P. and Walrand, J. (1980) A simple dynamic routing problem. IEEE Trans. Autom. Control. 25.Google Scholar
[2] Hordijk, A. and Koole, G. (1990) On the optimality of the generalized shortest queue policy. Prob. Eng. Inf. Sci. 4, 477–487.Google Scholar
[3] Johri, P. K. (1989) Optimality of the shortest line discipline with state-dependent service times. Eur. J. Operat. Res. 41, 157–161.Google Scholar
[4] Marshall, A. W. and Olkin, I. (1979) Inequalities: Theory of Majorization and Its Applications. Academic Press, New York.Google Scholar
[5] Menich, R. (1987) Optimality of the shortest queue routing for dependent service stations. Proc. 26th IEEE Conf. Dec. Control. Los Angeles, CA.CrossRefGoogle Scholar
[6] Shanthikumar, J. G. (1987) Stochastic majorization of random variables with proportional equalibrium rates. Adv. Appl. Prob. 19, 854–872.Google Scholar
[7] Towsley, D., Sparaggis, P. D. and Cassandras, C. G. (1992) Optimal routing and buffer allocation for a class of finite capacity queueing systems. IEEE Trans. Autom. Control. 3, 1446–1451.Google Scholar
[8] Walrand, J. (1988) Introduction to Queueing Networks. Prentice-Hall, Englewood Cliffs. NJ.Google Scholar
[9] Weber, R. R. (1978) On the optimal assignment of customers to parallel queue. J. Appl. Prob. 15, 406–413.Google Scholar
[10] Whitt, W. (1986) Deciding which queue to join. Operat. Res. 34, 55–62.Google Scholar
[11] Winston, W. (1977) Optimality of the shortest line discipline. J. Appl. Prob. 14, 181–189.CrossRefGoogle Scholar