Stochastic and robust scheduling in the cloud

Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

Users of cloud computing services are offered rapid access to computing resources via the Internet. Cloud providers use different pricing options such as (i) time slot reservation in advance at a fixed price and (ii) on-demand service at a (hourly) pay-as-used basis. Choosing the best combination of pricing options is a challenging task for users, in particular, when the instantiation of computing jobs underlies uncertainty. We propose a natural model for two-stage scheduling under uncertainty that captures such resource provisioning and scheduling problem in the cloud. Reserving a time unit for processing jobs incurs some cost, which depends on when the reservation is made: a priori decisions, based only on distributional information, are much cheaper than on-demand decisions when the actual scenario is known. We consider both stochastic and robust versions of scheduling unrelated machines with objectives of minimizing the sum of weighted completion times Σj wjCj and the makespan maxj Cj. Our main contribution is an (8+ε)-approximation algorithm for the min-sum objective for the stochastic polynomial-scenario model. The same technique gives a (7.11 + ε)-approximation for minimizing the makespan. The key ingredient is an LP-based separation of jobs and time slots to be considered in either the first or the second stage only, and then approximately solving the separated problems. At the expense of another ε our results hold for any arbitrary scenario distribution given by means of a black-box. Our techniques also yield approximation algorithms for robust two-stage scheduling.

Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
EditorsNaveen Garg, Klaus Jansen, Anup Rao, Jose D. P. Rolim
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages175-186
Number of pages12
ISBN (Electronic)9783939897897
DOIs
StatePublished - Aug 1 2015
Event18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 - Princeton, United States
Duration: Aug 24 2015Aug 26 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume40
ISSN (Print)1868-8969

Conference

Conference18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
Country/TerritoryUnited States
CityPrinceton
Period08/24/1508/26/15

Keywords

  • Approximation algorithms
  • Cloud computing
  • Robust optimization
  • Stochastic optimization
  • Unrelated machine scheduling

Fingerprint

Dive into the research topics of 'Stochastic and robust scheduling in the cloud'. Together they form a unique fingerprint.

Cite this