Hostname: page-component-848d4c4894-ndmmz Total loading time: 0 Render date: 2024-05-25T07:07:32.983Z Has data issue: false hasContentIssue false
  • English
  • Français

Work-conserving priorities

Published online by Cambridge University Press:  14 July 2016

Ronald W. Wolff
Ronald W. Wolff*
Affiliation:
University of California, Berkeley
Get access Rights & Permissions [Opens in a new window]

Abstract

In many situations, it is reasonable to assume that a priority rule does not affect the total time spent in service of any job. Rules with this property are said to be work-conserving. This concept unifies and simplifies the analysis of a variety of priority queues. Some results are obtained for rules applied to the GI/G/1 queue. Some special properties of Poisson arrivals are discussed, and a new proof of the equivalence of averaging over all time with averaging over arrival epochs is presented. In this case, explicit results for particular rules are obtained in examples. In another example, the optimal rule (from a very restrictive class) is determined without specializing the arrival stream.

Type
Research Papers
Information
Journal of Applied Probability , Volume 7 , Issue 2 , August 1970 , pp. 327 - 337
Copyright
Copyright © Applied Probability Trust 1970 

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

Avi-Itzhak, B. and Naor, P. (1963) Some queuing problems with service station subject to breakdown. Operat. Res. 11, 303–320.Google Scholar
Avi-Itzhak, B., Maxwell, W. L. and Miller, L. W. (1965) Queuing with alternating priorities. Operat. Res. 13, 306–318.Google Scholar
Balachandran, K. (1968) Optimization in priority queues. ORC 68–26, Operations Research Center, University of California, Berkeley.Google Scholar
Beneš, V. W. (1963) General Stochastic Processes in the Theory of Queues. Addison-Wesley, Reading, Mass.Google Scholar
Brumelle, S. L. (1969) Some inequalities for multi-server queues. ORC 69–17, Operations Research Center, University of California, Berkeley.Google Scholar
Cobham, A. (1954) Priority assignment in waiting line problems. Operat. Res. 2, 70–76.Google Scholar
Gaver, D. P. (1962) A waiting line with interrupted service, including priorities. J. R. Statist. Soc. B 25, 73–90.Google Scholar
Jaiswal, N. K. (1968) Priority Queues. Academic Press, New York.Google Scholar
Kiefer, J. and Wolfowitz, J. (1956) On the characteristics of the general queueing process with applications to random walk. Ann. Math. Statist. 27, 147–161.Google Scholar
Kleinrock, L. (1964) Communication Nets. McGraw-Hill, New-York.Google Scholar
Little, J. D. C. (1961) A proof of the queuing formula: L = ?W. Operat. Res. 9, 383–387.Google Scholar
Oliver, R. M. (1964) An alternative derivation of the Pollaczek-Khintchine formula. Operat. Res. 12, 158–159.Google Scholar
Riordan, J. (1962) Stochastic Service Systems. John Wiley and Sons, New York.Google Scholar
Schrage, L. (1969) A mixed-priority queue with applications to the analysis of real-time systems. Operat. Res. 17, 728–742.Google Scholar
Strauch, R. (1968) When a queue looks the same to an arriving customer as to an observer. RAND Corporation Report P–3985, Santa Monica, California.Google Scholar
Takács, L. (1964) Priority queues. Operat. Res. 12, 63–74.Google Scholar
Takács, L. (1968) Two queues attended by a single server. Operat. Res. 16, 639–650.Google Scholar
Van Den Heever, R. J. (1969) Computer time sharing priority systems. ORC 69–22, Operations Research Center, University of California, Berkeley.Google Scholar
Welch, P. D. (1964) On a generalized M/G/1 queueing process in which the first customer of each busy period receives exceptional service. Operat. Res. 12, 736–752.Google Scholar
Wolff, R. W. (1968) Time sharing with priorities. ORC 68–13, Operations Research Center, University of California, Berkeley.Google Scholar
Wolff, R. W. (1969) Conditions for delay to have finite moments in the GI/G/1 queue. ORC 69–39, Operations Research Center, University of California, Berkeley.Google Scholar