Name
Abstract | ||
|---|---|---|
We study the dynamic scheduling problem for jobs with fixed start and end times on multiple machines. The problem is to maintain an optimal schedule under the update operations: insertions and deletions of jobs. Call the period of time in a schedule between two consecutive jobs in a given machine an idle interval. We show that for any set of jobs there exists a schedule such that the corresponding set of idle intervals forms a tree under the set-theoretic inclusion. Based on this result, we provide a data structure that updates the optimal schedule in O(d+log n) worst-case time, where d is the depth of the set idle intervals and n is the number of jobs. Furthermore, we show this bound to be tight for any data structure that maintains a nested schedule. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-13075-0_19 | ALGORITHMS AND COMPUTATION, ISAAC 2014 |
Field | DocType | Volume |
Combinatorics,Fair-share scheduling,Interval scheduling,Computer science,Idle,Flow shop scheduling,Two-level scheduling,Rate-monotonic scheduling,Earliest deadline first scheduling,Dynamic priority scheduling | Conference | 8889 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander Gavruskin | 1 | 9 | 2.13 |
| Bakhadyr Khoussainov | 2 | 604 | 72.96 |
| Mikhail Kokho | 3 | 3 | 1.82 |
| Jiamou Liu | 4 | 49 | 23.19 |