Online interval scheduling with a bounded number of failures

Marco Bender, Clemens Thielen, Stephan Westphal

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

3 Zitate (Scopus)

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.

OriginalspracheEnglisch
Seiten (von - bis)443-457
Seitenumfang15
FachzeitschriftJournal of Scheduling
Jahrgang20
Ausgabenummer5
DOIs
PublikationsstatusVeröffentlicht - 1 Okt. 2017
Extern publiziertJa

Fingerprint

Untersuchen Sie die Forschungsthemen von „Online interval scheduling with a bounded number of failures“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren