×

Waiting time distributions in the accumulating priority queue. (English) Zbl 1307.60136

Summary: We are interested in queues in which customers of different classes arrive to a service facility, and where performance targets are specified for each class. The manager of such a queue has the task of implementing a queueing discipline that results in the performance targets for all classes being met simultaneously. For the case where the performance targets are specified in terms of ratios of mean waiting times, as long ago as the 1960s, L. Kleinrock [Nav. Res. Logist. Q. 11, 329–341 (1964; Zbl 0137.11906)] suggested a queueing discipline to ensure that the targets are achieved. He proposed that customers accumulate priority as a linear function of their time in the queue: the higher the urgency of the customer’s class, the greater the rate at which that customer accumulates priority. When the server becomes free, the customer (if any) with the highest accumulated priority at that time point is the one that is selected for service. Kleinrock called such a queue a time-dependent priority queue, but we shall refer to it as the accumulating priority queue. Recognising that the performance of many queues, particularly in the healthcare and human services sectors, is specified in terms of tails of waiting time distributions for customers of different classes, we revisit the accumulating priority queue to derive its waiting time distributions, rather than just the mean waiting times. We believe that some elements of our analysis, particularly the process that we call the maximum priority process, are of mathematical interest in their own right.

MSC:

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems

Citations:

Zbl 0137.11906

Software:

Algorithm 368
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abate, J., Whitt, W.: Numerical inversion of Laplace transforms of probability distributions. ORSA J. Comput. 7(1), 36-43 (1995) · Zbl 0821.65085 · doi:10.1287/ijoc.7.1.36
[2] Arnett, G., Hadorn, D.: Developing priority criteria for hip and knee replacement surgery: results from the Western Canada waiting list project. Can. J. Surg. 46(4), 290-296 (2003)
[3] The Australasian Triage Scale. From the website. http://www.acem.org.au/media/policies_and_guidelines/P06_Aust_Triage_Scale_Nov_2000.eps · Zbl 0155.24804
[4] The Canadian Triage and Acuity Scale. From the website. http://www.calgaryhealthregion.ca/policy/docs/1451/Admission_over_capacity_AppendixA.eps
[5] Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Addison-Wesley, Reading (1967) · Zbl 1058.90500
[6] Curtis, A.J., Russell, C.O.H., Stoelwinder, J.U., McNeil, J.J.: Waiting lists and elective surgery: ordering the queue. Med. J. Aust. 192(4), 217-220 (2010)
[7] Introduction to the National Clinical Priority System (CPS) for Access to Publicly Funded Hip or Knee Joint Replacement Surgery October 2007. http://www.nzoa.org.nz/content/CPAC_Prioritisation_Guidelines.eps
[8] Gaver Jr, D.P.: Observing stochastic processes and approximate transform inversion. Oper. Res. 14, 444-459 (1966) · doi:10.1287/opre.14.3.444
[9] Hay, A.M., Valentin, E.C., and Bijlsma, R.A. (2006) Modeling Emergency Care in Hospitals: A Paradox—The Patient Should Not Drive the Process. Proceedings of the 2006 Winter Simulation Conference, pp. 439-445
[10] Kleinrock, L.: Queueing Systems, vol. I. Theory Wiley, New York (1975) · Zbl 0334.60045
[11] Kleinrock, L.: Queueing Systems, vol. II: Computer Applications. Wiley, New York (1976) · Zbl 0361.60082
[12] Kleinrock, L.: A delay dependent queue discipline. Nav. Res. Logist. Q. 11, 329-341 (1964) · Zbl 0137.11906
[13] Kleinrock, L., Finkelstein, R.P.: Time dependent priority queues. Oper. Res. 15, 104-116 (1967) · Zbl 0155.24804 · doi:10.1287/opre.15.1.104
[14] Ramanan, K., Stolyar, A.: Largest weighted delay first scheduling: large deviations and optimality. Ann. Appl. Probab. 11, 1-48 (2001) · Zbl 1024.60012
[15] Seddon, M., Broad, J. Crengle, S., Bramley, D., Jackson, R. and White, H.: Coronary artery bypass graft surgery in New Zealands Auckland region: a comparison between the clinical priority assessment criteria score and the actual clinical priority assigned. J. N. Z. Med. Assoc. 119(1230), U1881 (2006). http://journal.nzma.org.nz/journal/119-1230/1881/ · Zbl 0821.65085
[16] Stehfest, H. (1970) Numerical inversion of Laplace transforms. Commun. ACM 13(1), 47-49 (Algorithm 368 with correction (October 1970), 13, No. 10)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.