Product-form queueing networks with negative and positive customers

TLDR

The paper introduces a class of queueing networks with negative and positive customers and demonstrates that, under standard assumptions, the model admits a product‑form stationary distribution. The model allows negative customers to decrement queue length when present, never receive service, and may change sign upon moving, while positive customers follow ordinary queueing dynamics; with exponential service, Poisson arrivals, and Markovian routing, the system satisfies nonlinear flow equations that yield a product‑form solution. The authors prove that the network is quasi‑reversible and admits a unique product‑form solution, though it fails to be quasi‑reversible under a broader definition that includes all customer destructions.

Abstract

We introduce a new class of queueing networks in which customers are either ‘negative' or ‘positive'. A negative customer arriving to a queue reduces the total customer count in that queue by 1 if the queue length is positive; it has no effect at all if the queue length is empty. Negative customers do not receive service. Customers leaving a queue for another one can either become negative or remain positive. Positive customers behave as ordinary queueing network customers and receive service. We show that this model with exponential service times, Poisson external arrivals, with the usual independence assumptions for service times, and Markovian customer movements between queues, has product form. It is quasi-reversible in the usual sense, but not in a broader sense which includes all destructions of customers in the set of departures. The existence and uniqueness of the solutions to the (nonlinear) customer flow equations, and hence of the product form solution, is discussed.