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].
Titolo: | Commitment and Slack for Online Load Maximization | |
Autori: | ||
Data di pubblicazione: | 2020 | |
Citazione: | 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]. | |
Handle: | http://hdl.handle.net/11573/1464508 | |
ISBN: | 9781450369350 | |
Appartiene alla tipologia: | 04b Atto di convegno in volume |
File allegati a questo prodotto
File | Note | Tipologia | Licenza | |
---|---|---|---|---|
Jamalabadi_Commitment-and-Slack_2020.pdf | Versione editoriale (versione pubblicata con il layout dell'editore) | Tutti i diritti riservati (All rights reserved) | Administrator Richiedi una copia |