The performance of a single-server queue with preemptive random priorities

Queues in which customers who belong to different classes have different priority levels is an old subject. Usually one looks for the performance of each class given its priority level. We suggest here a new model. Specifically, we consider the M/G/1 queue model in which all customers are identical ex-ante, but prior to joining the queue they draw a random (preemptive) priority level. We derive the Laplace-Stieltjes transform (LST) of a customer given his drawn priority parameter. From that the LST of an arbitrary customer can be integrated out. We present a number of proofs that provide some insight into the model. Special attention is given to the case of exponential service (the M/M/1 queue) and to finding the first moment of waiting. In particular, we show that the model is ä middle of the road” one in the sense that the mean sojourn time lies between the corresponding means under the First-Come First-Served FCFS and the Last-Come First-Served with Preemption Resume (LCFS-PR) (or equivalently, Egalitarian Processor Sharing (EPS)) schemes. Finally, we show how the new scheme may lead to an improvement in the utilization of the server when customer decides whether or not to join. We conclude with a few words on the corresponding model but without preemption.