Name
Abstract | ||
|---|---|---|
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 machine that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis, it is commonly required that jobs contain some slack $\varepsilon>0$, which means that the feasible time window for scheduling a job is at least $1+\varepsilon$ times its processing time. In this paper, we resolve 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 give an algorithm with an optimal competitive ratio of $\Theta(1/\varepsilon)$ for the online throughput maximization problem when a scheduler must commit upon starting a job. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment. If commitment decisions must be made before a job's slack becomes less than a $\delta$-fraction of its size, we prove a competitive ratio of $\mathcal{O}(\varepsilon/((\varepsilon - \delta)\delta))$ for $0 < \delta < \varepsilon$. This result interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithms does admit any bounded competitive ratio. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.4230/LIPIcs.ESA.2020.41 | ESA |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eberle Franziska | 1 | 0 | 0.34 |
| nicole megow | 2 | 302 | 26.73 |
| Kevin Schewior | 3 | 37 | 9.79 |