Home » Publication » 22316

Dettaglio pubblicazione

2020, Annual ACM Symposium on Parallelism in Algorithms and Architectures, Pages 339-348

Commitment and Slack for Online Load Maximization (04b Atto di convegno in volume)

Jamalabadi S., Schwiegelshohn C., Schwiegelshohn U.

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.
ISBN: 9781450369350
Gruppo di ricerca: Algorithms and Data Science
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma