The M/G/1 Queue with Quasi-Restricted Accessibility

Abstract

We consider single-server queues of the M/G/1 kind with a special kind of partial customer rejection called quasi-restricted accessibility (QRA). Under QRA, the actual service time assigned to an arriving customer depends on his service requirement, say x, the current workload, say w, and a prespecified threshold b. If x+wb the customer is fully served. If wbw+x, the customer receives service time b-w+(w+x-b)f for some random number f[0, 1], while if wb the actual service time is the fraction fx of the requirement. The random fractions are assumed to be i.i.d. The main aim of this article is to determine some of the central characteristics of this system in closed form. We derive the steady-state distribution of the workload process, which is also the steady-state distribution of the waiting time, and provide explicit results for the case of service times with rational Laplace transforms, in particular for Erlang or hyperexponential service requirements, and uniformly distributed or constant fractions. We also deal with the case of exponential barriers b (instead of one constant threshold). Furthermore, the distribution functions of the length of a busy period and the cycle maximum of the workload are determined. In the case of phase-type service requirements there is an alternative (martingale) technique to derive the busy period distribution; we illustrate this approach in the case of Erlang(2,). Finally, we show in the example of the Erlang(2,)/M/1-type QRA queue with deterministic fractions (which is non-Markovian) how to compute the busy period distribution via a duality with a Markovian system.