Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-06T05:29:41.776Z Has data issue: false hasContentIssue false
  • English
  • Français

Convex ordering of sojourn times in single-server queues: extremal properties of FIFO and LIFO service disciplines

Published online by Cambridge University Press:  14 July 2016

J. George Shanthikumar  and
Ushio Sumita
J. George Shanthikumar*
Affiliation:
University of California, Berkeley
Ushio Sumita*
Affiliation:
University of Rochester
*
∗Postal address: School of Business Administration, University of California, Berkeley, CA 94720, USA.
∗∗Postal address: William E. Simon Graduate School of Business Administration, University of Rochester, Rochester NY 14627, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, the extremal properties of the ergodic sojourn times in G/G/1queues under various service disciplines are studied in terms of the convex ordering. It is shown that among work-conserving non-preemptive service disciplines that are service time independent, the FIFO and the LIFO service disciplines provide the minima and the maxima, respectively, of the ergodic sojourn times for any G/G/1 queue. For G/M/1 queues, this class of work-conserving service disciplines is extended to include preemptive/resume disciplines. In this case the FIFO and LIFO-P (preemptive/resume LIFO) service disciplines attain the minima and maxima, respectively. These extend results of Durr (1971), Kingman (1962) and a recent result of Ramaswami (1984). Further results are obtained for G/Em/1 and G/D/1 queues.

Keywords

INCREASING CONVEX ORDERINGSTOCHASTIC ORDERING
Type
Research Papers
Information
Journal of Applied Probability , Volume 24 , Issue 3 , September 1987 , pp. 737 - 748
Copyright
Copyright © Applied Probability Trust 1987 

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

Barlow, R. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing. Holt, Rinehart and Winston, New York.Google Scholar
Durr, L. (1971) Priority queues with random order of services. Operat. Res. 19, 453–460.CrossRefGoogle Scholar
Heyman, D. P. and Sobel, M. J. (1982) Stochastic Models in Operations Research, Vol. I. McGraw-Hill, New York.Google Scholar
Kingman, J. F. C. (1962) The effect of queue discipline on waiting time variance. Proc. Camb. Phil. Soc. 58, 163–164.Google Scholar
Kleinrock, L. (1976) Queueing Systems, Vol. 2, Wiley, New York.Google Scholar
Ramaswami, V. (1984) The sojourn times in the GI/M/1 queue with processor sharing. J. Appl. Prob. 21, 437–442.Google Scholar
Ross, S. M. (1983) Stochastic Processes. Wiley, New York.Google Scholar