Recent Advances in Accumulating Priority Queues

This thesis extends the theory underlying the Accumulating Priority Queue (APQ) in three directions. In the first, we present a multi-class multi-server accumulating priority queue with Poisson arrivals and heterogeneous services. The waiting time distributions for different classes have been derived. A conservation law for systems with heterogeneous servers has been studied. We also investigate an optimization problem to find the optimal level of heterogeneity in the multi-server system. Numerical investigations through simulation are carried out to validate the model. We next focus on a queueing system with Poisson arrivals, generally distributed service times and nonlinear priority accumulation functions. We start with an extension of the power-law APQ in Kleinrock and Finkelstein (1967), and use a general argument to show that there is a linear system of the form discussed in Stanford, Taylor, and Ziedins (2014) which has the same priority ordering of all customers present at any given instant in time, for any sample path. Beyond the power-law case, we subsequently characterize the class of nonlinear accumulating priority queues for which an equivalent linear APQ can be found, in the sense that the waiting time distributions for each of the classes are identical in both the linear and nonlinear systems. Many operational queuing systems must adhere to waiting time targets known as Key Performance Indicators (KPIs), particularly in health care applications. In the last aspect, we address an optimization problem to minimize the weighted average of the expected excess waiting time (WAE), so as to achieve the optimal performance of a system operating under KPIs. We then find that the Accumulating Priority queuing discipline is well suited to systems with KPIs, in that each class of customers progresses fairly towards timely access by its own waiting time limit. Due to the difficulties in minimizing the WAE, we introduce a surrogate objective function, the integrated weighted average excess (IWAE), which provides a useful proxy for WAE. Finally, we propose a rule of thumb in which patients in the various classes accumulate priority credit at a rate that is inversely proportional to their time limits