Stochastic Online Scheduling on Unrelated Machines

Varun Gupta, Benjamin Moseley, Marc Jochen Uetz, Qiaomin Xie

Research output: Book/ReportReportOther research output

136 Downloads (Pure)

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 languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages21
Publication statusPublished - Nov 2016

Publication series

NameCTIT technical report
PublisherUniversity of Twente, Centre for Telematics and Information Technology (CTIT)
No.TR-CTIT-16-13
ISSN (Print)1381-3625

Keywords

  • IR-103778
  • EWI-27625
  • Stochastic Scheduling
  • Approximation Algorithm

Cite this