A Dynamic Time-Sharing Priority Queue

Abstract

This paper deals with a single server station delivering service to m priority classes (m might be finite or infinite). The arrival process of customers from a jth (j = 1, 2,…, m) priority class (jth customers) to a single server station is a homogenous Poisson process with rate X3 � Service requirements of jth customers are exponentially distributed with mean 1/~. The waiting line consists of infinitely many separate queues all of which obey the FIFO rule. Each priority class is assigned to one of the queues. A newly arrived jth customer joins the end of a predetermined queue. In the ith (i = 1, 2,… ) queue a customer is eligible for a certain amount of service following which he either departs when his service requirement has been satisfied or joins the end of the (i + 1)th queue for additional service. When a quantum of service is completed, the server attends to the first customer in the lowest index (highest priority) nonempty queue. In such a priority regime, long and unknown in advance service requirements in all priority classes are dynamically penalized by degrading their priority degree. This paper derives mathematical expressions for calculating the expected total flow time of a jth customer whose service requirement is known. © 1971, ACM. All rights reserved.