Queueing performance with impatient customers

The problem of scheduling impatient customers in a non-preemptive G/GI/1 queue is considered. Every customer has a random deadline to the beginning of its service. Given the distribution of the customer deadlines (rather than their exact values), a scheduling policy decides the customer service order and also which customer(s) to reject. The objective is to find an optimal policy which maximizes the number of customers served before their deadlines. It is shown that LIFO (last-in first-out) is an optimal service order when the deadlines are i.i.d. (independently identically distributed) random variables with a concave cumulative distribution function. There is an optimal policy in the LIFO-TO (time-out) class, as defined by the authors. For the M/GI/1 queue, it is proved that unforced idle times are not allowed under this optimal policy. It is also shown that the optimal LIFO-TO policy assigns a fixed critical time (i.e., its maximum waiting time) to every customer. When the customer waiting times are unknown, the optimal policy for an M/M/1 queue becomes the LIFO-PO (push-out) policy, with a fixed buffer size used as a rejection threshold.