Deliverable D6

State of the Art in the Theory and Applications of Queueing Networks with Negative and Positive Customers

• Introduction to the deliverable
• Contents of the deliverable

Introduction to Deliverable D6

G-networks are a generalisation of Markovian queueing networks with negative customers. A negative customer will remove an ordinary (positive) customer (if any) out of the system. G-networks were proposed by Gelenbe [E. Gelenbe (1991), ``Product Form Queueing Networks with Negative and Positive Customers'', J. Appl. Prob., 1991]. Various new properties of single queues (G-queues) and G-networks have been derived in the first year of the QMIPS project, together with generalisations of the semantics of a negative customer (negative signals) and applications of the concept. A negative signal will transfer a positive customer either to another queue or outside of the system, the choice being probabilistic. [E. Gelenbe (1993), ``G-Networks with Triggered Customer Mouvement'', J. Appl. Prob., (to appear)]

Product-form solutions for the steady-state probabilities of the queue length have been found for G-networks and G-networks with signals, [Gelenbe (1991), Gelenbe (1993) above].

Harrison and Pitel have extended their results on the sojourn time distribution in a Markovian G-queue to a tandem of two G-queues [Harrison and Pitel (1993), ``Response Time Distributions in Tandem'', (submitted for publication)]. The same authors have also solved for the equilibrium queue length distribution in a M/G/1 queue with negative customers, for various combinations of queueing disciplines (for positive customers) and killing strategies [Harrison and Pitel (1993), ``The M/G/1 Queue with Negative Customers'', (submitted for publication)]. Gelenbe (jointly with Fourneau and Suros) has investigated G-networks with multiple classes of positive customers.

Applications

The first application of negative customers was in the modeling of inhibition signals in neural networks. In the first year of the QMIPS project, this has been extended in the light of the above generalisations and new applications have been pursued in the areas of load-balancing, and synchronisation through semaphores.

D6-1

``G-Networks with multiple class of negative and positive customers'', J.M. Fourneau, E. Gelenbe and R. Suros.

D6-2

``Response Time Distributions in Tandem G-Networks'', P.G. Harrison and E. Pitel. (front page)

D6-3

``The M/G/1 Queue with Negative Customers'', P. G. Harrison and E. Pitel. (front page)