Stochastic online scheduling on unrelated machines

Varun Gupta; Benjamin Moseley; Marc Uetz; Qiaomin Xie

doi:10.1007/978-3-319-59250-3_19

Stochastic online scheduling on unrelated machines

Varun Gupta, Benjamin Moseley, Marc Uetz^*, Qiaomin Xie

^*Corresponding author for this work

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

13 Citations (Scopus)

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	https://doi.org/10.1007/978-3-319-59250-3_19
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

Access to Document

10.1007/978-3-319-59250-3_19

Cite this

Gupta, V., Moseley, B., Uetz, M., & Xie, Q. (2017). Stochastic online scheduling on unrelated machines. In F. Eisenbrand, & J. Koenemann (Eds.), Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings (pp. 228-240). (Lecture Notes in Computer Science ; Vol. 10328). Springer. https://doi.org/10.1007/978-3-319-59250-3_19

Gupta, Varun ; Moseley, Benjamin ; Uetz, Marc ; Xie, Qiaomin. / Stochastic online scheduling on unrelated machines. Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings. editor / Friedrich Eisenbrand ; Jochen Koenemann. Springer, 2017. pp. 228-240 (Lecture Notes in Computer Science ).

@inproceedings{6fd63730a21240768486cee6bd10909e,

title = "Stochastic online scheduling on unrelated machines",

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.",

author = "Varun Gupta and Benjamin Moseley and Marc Uetz and Qiaomin Xie",

year = "2017",

month = jun,

doi = "10.1007/978-3-319-59250-3_19",

language = "English",

isbn = "978-3-319-59249-7",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "228--240",

editor = "Friedrich Eisenbrand and Jochen Koenemann",

booktitle = "Integer Programming and Combinatorial Optimization",

address = "Netherlands",

note = "19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017, IPCO ; Conference date: 26-06-2017 Through 28-06-2017",

}

Gupta, V, Moseley, B, Uetz, M & Xie, Q 2017, Stochastic online scheduling on unrelated machines. in F Eisenbrand & J Koenemann (eds), Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings. Lecture Notes in Computer Science , vol. 10328, Springer, pp. 228-240, 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017, Waterloo, Canada, 26/06/17. https://doi.org/10.1007/978-3-319-59250-3_19

Stochastic online scheduling on unrelated machines. / Gupta, Varun; Moseley, Benjamin; Uetz, Marc; Xie, Qiaomin.

Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings. ed. / Friedrich Eisenbrand; Jochen Koenemann. Springer, 2017. p. 228-240 (Lecture Notes in Computer Science ; Vol. 10328).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Stochastic online scheduling on unrelated machines

AU - Gupta, Varun

AU - Moseley, Benjamin

AU - Uetz, Marc

AU - Xie, Qiaomin

N1 - Conference code: 19

PY - 2017/6

Y1 - 2017/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85020530866&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59250-3_19

DO - 10.1007/978-3-319-59250-3_19

M3 - Conference contribution

AN - SCOPUS:85020530866

SN - 978-3-319-59249-7

T3 - Lecture Notes in Computer Science

SP - 228

EP - 240

BT - Integer Programming and Combinatorial Optimization

A2 - Eisenbrand, Friedrich

A2 - Koenemann, Jochen

PB - Springer

T2 - 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017

Y2 - 26 June 2017 through 28 June 2017

ER -

Gupta V, Moseley B, Uetz M, Xie Q. Stochastic online scheduling on unrelated machines. In Eisenbrand F, Koenemann J, editors, Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings. Springer. 2017. p. 228-240. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-319-59250-3_19

Stochastic online scheduling on unrelated machines

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this