TY - JOUR

T1 - Some related paradoxes of queuing theory

T2 - New cases and a unifying explanation

AU - Atkinson, J. B.

PY - 2000/8

Y1 - 2000/8

N2 - In this paper, we study a number of closely related paradoxes of queuing theory, each of which is based on the intuitive notion that the level of congestion in a queuing system should be directly related to the stochastic variability of the arrival process and the service times. In contrast to such an expectation, it has previously been shown that, in all Hk/G/l queues, PW (the steady-state probability that a customer has to wait for service) decreases when the service-time becomes more variable. An analagous result has also been proved for ploss (the steady-state probability that a customer is lost) in all Hk/G/l loss systems. Such theoretical results can be seen, in this paper, to be part of a much broader scheme of paradoxical behaviour which covers a wide range of queuing systems. The main aim of this paper is to provide a unifying explanation for these kinds of behaviour. Using an analysis based on a simple, approximate model, we show that, for an arbitrary set of n GI/Gk/l loss systems (k = l,.n), if the interarrival-time distribution is fixed and ‘does not differ too greatly from the exponential distribution, and if the n systems are ordered in terms of their ploss values, then the order that results whenever cA < l is the exact reverse of the order that results whenever cA > l, where cA is the coefficient of variation of the interarrival time. An important part of the analysis is the insensitivity of the ploss value in an M/G/l loss system to the choice of service-time distribution, for a given traffic intensity. The analysis is easily generalised to other queuing systems for which similar insensitivity results hold. Numerical results are presented for paradoxical behaviour of the following quantities in the steady state: ploss in the GI/G/l loss system; PW and Wq (the expected queuing time of customers) in the GI /G/l queue; and pK (the probability that all K machines are in the failed state) in the GI/G/r machine interference model. Two of these examples of paradoxical behaviour have not previously been reported in the literature. Additional cases are also discussed.

AB - In this paper, we study a number of closely related paradoxes of queuing theory, each of which is based on the intuitive notion that the level of congestion in a queuing system should be directly related to the stochastic variability of the arrival process and the service times. In contrast to such an expectation, it has previously been shown that, in all Hk/G/l queues, PW (the steady-state probability that a customer has to wait for service) decreases when the service-time becomes more variable. An analagous result has also been proved for ploss (the steady-state probability that a customer is lost) in all Hk/G/l loss systems. Such theoretical results can be seen, in this paper, to be part of a much broader scheme of paradoxical behaviour which covers a wide range of queuing systems. The main aim of this paper is to provide a unifying explanation for these kinds of behaviour. Using an analysis based on a simple, approximate model, we show that, for an arbitrary set of n GI/Gk/l loss systems (k = l,.n), if the interarrival-time distribution is fixed and ‘does not differ too greatly from the exponential distribution, and if the n systems are ordered in terms of their ploss values, then the order that results whenever cA < l is the exact reverse of the order that results whenever cA > l, where cA is the coefficient of variation of the interarrival time. An important part of the analysis is the insensitivity of the ploss value in an M/G/l loss system to the choice of service-time distribution, for a given traffic intensity. The analysis is easily generalised to other queuing systems for which similar insensitivity results hold. Numerical results are presented for paradoxical behaviour of the following quantities in the steady state: ploss in the GI/G/l loss system; PW and Wq (the expected queuing time of customers) in the GI /G/l queue; and pK (the probability that all K machines are in the failed state) in the GI/G/r machine interference model. Two of these examples of paradoxical behaviour have not previously been reported in the literature. Additional cases are also discussed.

KW - Insensitivity

KW - Loss systems

KW - Machine interference models

KW - Measures of congestion

KW - Paradoxes

KW - Queues

KW - Stochastic order

UR - http://www.scopus.com/inward/record.url?scp=0034250901&partnerID=8YFLogxK

U2 - 10.1057/palgrave.jors.2601000

DO - 10.1057/palgrave.jors.2601000

M3 - Article

AN - SCOPUS:0034250901

SN - 0160-5682

VL - 51

SP - 921

EP - 935

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

IS - 8

ER -