Abstract | ||
---|---|---|
BSTRACTThe active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to g jobs during each timestep. The goal in the active-time problem is to minimize the number of active steps, i.e., timesteps in which at least one job is scheduled. This paper presents a 9/5-approximation algorithm for a special case of the active-time scheduling problem in which job windows are laminar (nested). This result improves on the previous best 2-approximation for the general case. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1145/3490148.3538554 | ACM Symposium on Parallel Algorithms and Architectures |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nairen Cao | 1 | 0 | 1.35 |
Jeremy T. Fineman | 2 | 587 | 36.10 |
Shi Li | 3 | 208 | 22.01 |
Julián Mestre | 4 | 0 | 0.34 |
Katina Russell | 5 | 0 | 1.35 |
Seeun William Umboh | 6 | 0 | 0.34 |