Logo des Repositoriums
Zur Startseite
  • English
  • Deutsch
Anmelden
  1. Startseite
  2. SuUB
  3. Forschungsdokumente
  4. Online Throughput Maximization on Unrelated Machines: Commitment is No Burden
 
Zitierlink DOI
10.26092/elib/3189
Verlagslink DOI
10.1145/3569582

Online Throughput Maximization on Unrelated Machines: Commitment is No Burden

Veröffentlichungsdatum
2023-02-20
Autoren
Eberle, Franziska  
Megow, Nicole  
Schewior, Kevin  
Zusammenfassung
We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a single or multiple possibly unrelated machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis on a single machine, we require
that jobs contain some slack ε > 0, which means that the feasible time window for scheduling a job is at least 1 + ε times its processing time on each eligible machine. Our contribution is two-fold: (i) We give the first non-trivial online algorithms for throughput maximization on unrelated machines, and (ii), this is the main focus of our paper, we answer the question on how to handle commitment requirements which enforce that a scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services, and disallows last-minute rejections of critical tasks. We present an algorithm for unrelated machines that is Θ( 1ε )-competitive when the scheduler must commit upon starting a job. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be
made before a job’s slack becomes less than a δ-fraction of its size, we prove a competitive ratio of O( 1ε−δ ) for 0 < δ < ε. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithm admits any bounded competitive ratio. While we mainly focus on scheduling without migration, our results also hold when comparing against a migratory optimal solution in case of identical machines.
Schlagwörter
Deadline scheduling

; 

Throughput

; 

Online algorithms

; 

Competitive analysis

; 

Unrelated machines
Verlag
Association for Computing Machinery
Institution
Universität Bremen  
Fachbereich
Fachbereich 03: Mathematik/Informatik (FB 03)  
Dokumenttyp
Artikel/Aufsatz
Zeitschrift/Sammelwerk
ACM Transactions on Algorithms  
Band
19
Heft
1
Startseite
1
Endseite
25
Zweitveröffentlichung
Ja
Dokumentversion
Postprint
Lizenz
Alle Rechte vorbehalten
Sprache
Englisch
Dateien
Lade...
Vorschaubild
Name

Eberle_Megow_Schewior_Online Throughput Maximization on Unrelated Machines_2023_accepted-version.pdf

Size

1.18 MB

Format

Adobe PDF

Checksum

(MD5):baf8a19d7f4be8601d6bcc59396236d0

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Datenschutzbestimmungen
  • Endnutzervereinbarung
  • Feedback schicken