Meeting Soft Deadlines in Single- and Multi-Server Systems

Esa Hyytiä, Rhonda Righter, Jorma Virtamo

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

6 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
Publication statusPublished - Jan 2017
MoE publication typeA4 Article in a conference publication
EventInternational Teletraffic Congress - Würzburg, Germany
Duration: 12 Sep 201616 Sep 2016
Conference number: 28


ConferenceInternational Teletraffic Congress
Abbreviated titleITC


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

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

  • Projects

    Faster Queues for Big Data - Nopeammat jonot suurten tietomassojen käsittelyyn

    Hyytiä, E., Aalto, S., Viitasaari, L., Osti, P., Wu, X. & Bilenne, O.


    Project: Academy of Finland: Other research funding

    Towards Optimal Performance-Energy Trade-off in Server Farms

    Aalto, S., Gebrehiwot, M., Hyytiä, E., Lassila, P. & Osti, P.


    Project: Academy of Finland: Other research funding

    Cite this

    Hyytiä, E., Righter, R., & Virtamo, J. (2017). Meeting Soft Deadlines in Single- and Multi-Server Systems. In T. Hossfeld, B. L. Mark, G. Chan, & A. Timm-Giel (Eds.), Proceedings of the International Teletraffic Congress: ITC 28 (pp. 166-174)