Meeting Soft Deadlines in Single- and Multi-Server Systems

Esa Hyytiä, Rhonda Righter, Jorma Virtamo

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

7 Citations (Scopus)


We consider single-and multi-server systems, where jobs have a maximum waiting time (deadline) defined, e.g., by a service level agreement. A fixed cost is associated with deadline violations and the task is to minimize the long-run cumulative costs. Job sizes (service durations) are observed upon arrival, and current queue backlogs are known. For a single FCFS server, the optimization task is to find the optimal admission policy that may reject a job upon arrival if admitting it would cause in future one or more deadlines to be violated (in expectation). For parallel FCFS servers, the policy must (i) either accept or reject a job upon arrival, and if accepted, (ii) assign it to one of the servers. We derive efficient deadline-aware policies in the MDP framework. For a single server, we obtain the optimal admission policy. For dispatching to parallel servers, we develop efficient heuristic admission and dispatching policies, whose performances are evaluated by means of numerical examples. Additionally, we give some exact closed-form results for heavy-traffic limits.
Original languageEnglish
Title of host publicationProceedings of the International Teletraffic Congress
Subtitle of host publicationITC 28
EditorsTobias Hossfeld, Brian L. Mark, Gary Chan, Andreas Timm-Giel
Number of pages9
ISBN (Print)978-0-9883045-1-2
Publication statusPublished - Jan 2017
MoE publication typeA4 Conference publication
EventInternational Teletraffic Congress - Würzburg, Germany
Duration: 12 Sept 201616 Sept 2016
Conference number: 28


ConferenceInternational Teletraffic Congress
Abbreviated titleITC


  • Servers
  • Dispatching
  • Queueing analysis
  • Steady-state
  • Context
  • Delays
  • Admission control


Dive into the research topics of 'Meeting Soft Deadlines in Single- and Multi-Server Systems'. Together they form a unique fingerprint.

Cite this