Optimal Scheduling Policies for a Class of Queues with Customer Deadlines to the Beginning of Service

Shivendra S. Panwar, Don Towsley, Jack K. Wolf

Research output: Contribution to journalArticle

Abstract

Many problems can be modeled as single-server queues with impatient customers. An example is that of the transmission of voice packets over a packet-switched network. If the voice packets do not reach their destination within a certain time interval of their transmission, they are useless to the receiver and considered lost. It is therefore desirable to schedule the customers such that the fraction of customers served within their respective deadlines is maximized. For this measure of performance, it is shown that the shortest time to extinction (STE) policy is optimal for a class of continuous and discrete time nonpreemptive M/G/1 queues that do not allow unforced idle times. When unforced idle times are allowed, the best policies belong to the class of shortest time to extinction with inserted idle time (STEI) policies. An STEI policy requires that the customer closest to his or her deadline be scheduled whenever it schedules a customer. It also has the choice of inserting idle times while the queue is nonempty. It is also shown that the STE policy is optimal for the discrete time G/D/1 queue where all customers receive one unit of service. The paper concludes with a comparison of the expected customer loss using an STE policy with that of the first-come, first-served (FCFS) scheduling policy for one specific queue.

Original languageEnglish (US)
Pages (from-to)832-844
Number of pages13
JournalJournal of the ACM (JACM)
Volume35
Issue number4
DOIs
StatePublished - Oct 1 1988

Keywords

  • Control of Queues
  • Markov decision processes
  • packetized voice communications
  • queues with impatient customers
  • stochastic scheduling theory

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Optimal Scheduling Policies for a Class of Queues with Customer Deadlines to the Beginning of Service'. Together they form a unique fingerprint.

  • Cite this