A discrete-time queue with customers with geometric deadlines

This paper studies a discrete-time queueing system where each customer has a maximum allowed sojourn time in the system, referred to as the “deadline” of the customer. More specifically, we model the deadlines of the consecutive customers as independent and geometrically distributed random variables. Customers enter the system according to a general independent arrival process, i.e., the numbers of arrivals during consecutive time slots are i.i.d. random variables with arbitrary distribution. Service times of the customers are deterministically equal to one slot each. For this queueing model, we are able to obtain exact formulas for such quantities as the generating function and the expected value of the system content, the mean customer delay and the deadline-expiration ratio. These formulas, however, contain infinite sums and infinite products, which implies that truncations are required to actually compute numerical values. Therefore, we also derive some easy-to-evaluate approximate results for the main performance measures, based on a polynomial approximation technique. We believe this technique, in its own right, is also one of the major (methodological) contributions of the paper.Possible applications of this type of queueing model are numerous: the (variable) deadlines could model, for instance, the fact that customers may become impatient and leave the queue unserved if they have to wait too long in line, but they could also reflect the fact that the service of a customer is not useful anymore if it cannot be delivered soon enough, etc.