We consider a basic admission control problem in which jobs with deadlines arrive online and our goal is to maximize the total volume of executed job processing times. We assume that the deadlines have a slack of at least ϵ, that is, each deadline d satisfies d≥ (1+ϵ)· p+r with processing time p and release date r. In addition, we require the admission policy to support immediate commitment, that is, upon a job's submission, we must immediately make the decision of if and where we schedule the job, and this decision is irreversible. Our main contribution is a deterministic algorithm with nearly optimal competitive ratio for load maximization on multiple machines in the non-preemptive model. Previous results either only held for a single machine, did not support commitment, or required job preemption and migration.

Commitment and Slack for Online Load Maximization / Jamalabadi, S.; Schwiegelshohn, C.; Schwiegelshohn, U.. - (2020), pp. 339-348. (Intervento presentato al convegno 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020 tenutosi a Virtual, Online; United States) [10.1145/3350755.3400271].

Commitment and Slack for Online Load Maximization

Schwiegelshohn C.
;
2020

Abstract

We consider a basic admission control problem in which jobs with deadlines arrive online and our goal is to maximize the total volume of executed job processing times. We assume that the deadlines have a slack of at least ϵ, that is, each deadline d satisfies d≥ (1+ϵ)· p+r with processing time p and release date r. In addition, we require the admission policy to support immediate commitment, that is, upon a job's submission, we must immediately make the decision of if and where we schedule the job, and this decision is irreversible. Our main contribution is a deterministic algorithm with nearly optimal competitive ratio for load maximization on multiple machines in the non-preemptive model. Previous results either only held for a single machine, did not support commitment, or required job preemption and migration.
2020
32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020
commitment; online algorithms; scheduling
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Commitment and Slack for Online Load Maximization / Jamalabadi, S.; Schwiegelshohn, C.; Schwiegelshohn, U.. - (2020), pp. 339-348. (Intervento presentato al convegno 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020 tenutosi a Virtual, Online; United States) [10.1145/3350755.3400271].
File allegati a questo prodotto
File Dimensione Formato  
Jamalabadi_Commitment-and-Slack_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.36 MB
Formato Adobe PDF
1.36 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1464508
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact