Queueing performance with impatient customers

Zheng Xue Zhao, Shivendra S. Panwar, Don Towsley

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationNetworking in the 90s
PublisherPubl by IEEE
Number of pages10
ISBN (Print)0879426942
StatePublished - 1991
EventProceedings of the 10th Annual Joint Conference of the IEEE and Communications Societies - IEEE INFOCOM '91 - Bal Harbour, FL, USA
Duration: Apr 7 1991Apr 11 1991

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherProceedings of the 10th Annual Joint Conference of the IEEE and Communications Societies - IEEE INFOCOM '91
CityBal Harbour, FL, USA

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Queueing performance with impatient customers'. Together they form a unique fingerprint.

Cite this