Name
Abstract | ||
|---|---|---|
We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. As to the techniques applied, this paper shows how the dual fitting technique can be put to work for stochastic and nonpreemptive scheduling problems. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-59250-3_19 | INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2017 |
DocType | Volume | ISSN |
Conference | 10328 | 0302-9743 |
Citations | PageRank | References |
2 | 0.42 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Varun Gupta | 1 | 681 | 42.04 |
| Benjamin Moseley | 2 | 554 | 50.11 |
| Marc Uetz | 3 | 456 | 43.99 |
| Qiaomin Xie | 4 | 133 | 11.65 |