Double-ended queues with impatience

The effect of “impatient” behaviour is studied primarily in the context of “double-ended” queues where each demands service from the other, typically taxis and passengers. Related models, single queue, and double, with a variety of mechanisms are considered. “Impatience” is to be understood in a wider context than simply becoming tired of waiting: it can arise because the customer, for some reason, runs out of time (inventory and organ transplantation), or because an alternative service becomes available (communication applications). The emphasis in this paper is theoretical but a brief numerical assessment of operational consequences is given.

Scope and purpose

The “double-ended (or synchronization) queue” is a model for a variety of service demanding/providing systems. In an orderly taxi rank at a railway station or airport, on one side a queue is formed by the arrival of stream of passengers who wait for taxis to their destinations while on the other side a queue of taxis waiting for passengers. Obviously, the two queues can never coexist. The concept of “impatience” enters when a taxi or passenger leaves the queue before receiving service.This concept of “reneging” is widely applicable. In health care, for example, organs are stored for transplantation for needful patients. Both the organs and the demands for them have limited lifetime. A similar scenario applies to perishable inventory systems. In a similar manner, the real-time communication networks admit impatient behaviour. A typical example is a processor-shared queue in data networks with random time-out periods or deadlines.The paper sets out the basics in a variety of theoretical model settings with the common feature of exponential arrival, service and impatience mechanisms. A brief discussion based on numerical calculation is given of some operational features of the models but the thrust is on the theoretical techniques needed to make meaningful operational assessments.