On the stability condition of a precedence-based queueing discipline

Publisher Website
Google Scholar
Abstract
The queueing model known asprecedence-based queueing discipline, proposed in [8] by Tsitsiklis et al. is addressed. In this queueing model, there are infinitely many servers and for any pair of customersiandjsuch thatiarrived later thanj,there is a fixed probabilitypthatiwill have to wait for the end of the execution ofjbefore starting its execution. In the case where the customer service times are deterministic and the arrival process is Poisson, these authors have derived the stability condition which determines the maximum arrival rate that keeps the system stable. For more general statistics, they conjectured that the stability condition would possibly depend on the complete service time distribution functions but only on the first moment of the inter-arrival times.In this paper, we consider this queueing model and relax the restrictive statistical assumptions mentioned above by only assuming that the service times and the inter-arrival times are stationary and ergodic sequences, so that these variables can receive general distribution functions and be correlated.We derive a general expression for the stability condition which in turn proves the above conjectures. The results are obtained by establishing pathwise evolution equations for these queueing systems, and then a schema which, in certain sense, generalizes the schema of Loynes for theG/G/1 queues.

This publication has 5 references indexed in Scilit: