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, 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.
Gruppo di ricerca: Algorithms and Data Science