Queueing performance with impatient customers

Zheng Xue Zhao, Shivendra S. Panwar, Don Towsley

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

Abstract

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
Pages400-409
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
Volume1
ISSN (Print)0743-166X

Other

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

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

  • Cite this

    Zhao, Z. X., Panwar, S. S., & Towsley, D. (1991). Queueing performance with impatient customers. In Networking in the 90s (pp. 400-409). (Proceedings - IEEE INFOCOM; Vol. 1). Publ by IEEE.