Priority queues

Abstract

Extensive research has been carried out in the subject of Priority Queues over the past ten years, culminating in the book by Jaiswal [8], in this thesis, certain isolated problems which appear to have been omitted from the consideration of other authors are discussed. The first two chapters are concerned with the question of how priorities should be allocated to customers (or 'units') arriving at a queue so as to minimize the overall meaning waiting time [it is perhaps worth mentioning at the outset that following current usage, the terms 'queueing time' and ‘waiting time' will be used synonymously throughout; both refer to the time a unit waits before commencing service]. In previous treatments of this 'allocation of priorities problem it has always been assumed that on arrival, the service time requirement of a unit could be predicted exactly; the effect of having only imperfect information in the form of an estimated service time is considered here. Chapter l deals with the non-pre-emptive discipline; Chapter 2 with discretionary disciplines. Priority queues in which the arrival epochs of different types of units form independent renewal processes have only been solved under the assumption of random arrivals. However, if the following modified arrival scheme is considered. arrival epochs form an ordinary renewal process, and at any arrival epoch, independently of what happened at all previous epochs, with probability q1 the arrival is a priority unit and with probability q2 a non=priority unit (where ql+q2 =l) then the priority analogues of the ordinary single-server queues E(_b)/G/l and GI/M/1 can be solved (Chapters 3 and 4 respectively)" In conclusion, Chapter 5 is concerned with approximate methods: (v) section 1 is a review of previous work on deriving bounds for the mean waiting time in a GI/G/1 queue, section 2 extends this work to the GI/G/1 priority queue,