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.
Original language | English |
---|---|
Title of host publication | Integer Programming and Combinatorial Optimization |
Subtitle of host publication | 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings |
Editors | Friedrich Eisenbrand, Jochen Koenemann |
Publisher | Springer |
Pages | 228-240 |
Number of pages | 13 |
ISBN (Electronic) | 978-3-319-59250-3 |
ISBN (Print) | 978-3-319-59249-7 |
DOIs | |
Publication status | Published - Jun 2017 |
Event | 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada Duration: 26 Jun 2017 → 28 Jun 2017 Conference number: 19 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 10328 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 |
---|---|
Abbreviated title | IPCO |
Country/Territory | Canada |
City | Waterloo |
Period | 26/06/17 → 28/06/17 |