Online interval scheduling with a bounded number of failures

Marco Bender, Clemens Thielen, Stephan Westphal

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

We consider the problem of scheduling intervals on m identical machines where each interval can be seen as a job with fixed start and end time. The goal is to accept a maximum cardinality subset of the given intervals and assign these intervals to the machines subject to the constraint that no two intervals assigned to the same machine overlap. We analyze an online version of this problem where, initially, a set of n potential intervals and an upper bound k on the number of failing intervals is given. If an interval fails, it can be accepted neither by the online algorithm nor by the adversary. An online algorithm learns that an interval fails at the time when it is supposed to be started. If a non-failing interval is accepted, it cannot be aborted and must be processed non-preemptively until completion. For different settings of this problem, we present deterministic and randomized online algorithms and prove lower bounds on the competitive ratio.

Original languageEnglish
Pages (from-to)443-457
Number of pages15
JournalJournal of Scheduling
Volume20
Issue number5
DOIs
StatePublished - 1 Oct 2017
Externally publishedYes

Keywords

  • Competitive Analysis
  • Interval Scheduling
  • Online Optimization

Fingerprint

Dive into the research topics of 'Online interval scheduling with a bounded number of failures'. Together they form a unique fingerprint.

Cite this