Dynamic, Non-Preemptive Priority Queues with General, Linearly Increasing Priority Function

Abstract

This paper considers a single server queueing system that services customers from P non-preemptive priority classes. We assume independent identically distributed exponential interarrival and general service times for each class of customer. We also assume that a customer's priority in the queue is determined not only by its class, but also by the length of time it has spent in the queue; the priority for each class can be a general linearly increasing priority function. Our development gives an expression for the expected waiting time of each customer class, and gives bounds on this expression. We demonstrate the calculation of the bounds by several numerical examples, and discuss the sensitivity of the bounds to priority function parameters and system utilization. We also show that, even under the most conservative assumptions, the bounds are remarkably tight. Furthermore, for the special case of an M/M/1 system with identical service time distributions, these bounds can be substantially improved if the ordinal ranking of expected waiting times is known a priori. The results of this research enable systems designers to anticipate and consequently to control system behavior for systems with general linearly increasing priority disciplines.