Name
Abstract | ||
|---|---|---|
We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a minimum number of machines. Our main result is a general O(log m)-competitive algorithm for the online problem, where m is the optimal number of machines used in an offline solution. This is the first improvement to an intriguing problem in nearly two decades. To date, the best known result is a O(log(p(max)/p(min)))-competitive algorithm by Phillips et al. [Optimal time-critical scheduling via resource augmentation, STOC, 1997] that depends on the ratio of maximum and minimum job sizes, P-max and p(min). Even for m = 2 no better algorithm was known. Our algorithm is in this case constant-competitive. When applied to laminar or agreeable instances, our algorithm achieves a competitive ratio of O(1) even independently of m. The following two key components lead to our new result. First, we derive a new lower bound on the optimum value that relates the laxity and the number of jobs with intersecting time windows. Then, we design a new algorithm that is tailored to this lower bound and balances the delay of jobs by taking the number of currently running jobs into account. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/17M116032X | SIAM JOURNAL ON COMPUTING |
Keywords | DocType | Volume |
online algorithms,multiprocessor scheduling,competitive analysis | Journal | 47 |
Issue | ISSN | Citations |
6 | 0097-5397 | 1 |
PageRank | References | Authors |
0.36 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lin Chen | 1 | 3 | 2.09 |
| nicole megow | 2 | 302 | 26.73 |
| Kevin Schewior | 3 | 37 | 9.79 |