Document Open Access Logo

Stochastic and Robust Scheduling in the Cloud

Authors Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.175.pdf
  • Filesize: 491 kB
  • 12 pages

Document Identifiers

Author Details

Lin Chen
Nicole Megow
Roman Rischke
Leen Stougie

Cite As Get BibTex

Lin Chen, Nicole Megow, Roman Rischke, and Leen Stougie. Stochastic and Robust Scheduling in the Cloud. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 175-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.175

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 and the makespan. Our main contribution is an (8+eps)-approximation algorithm for the min-sum objective for the stochastic polynomial-scenario model. The same technique gives a (7.11+eps)-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 epsilon 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.

Subject Classification

Keywords
  • Approximation Algorithms
  • Robust Optimization
  • Stochastic Optimization
  • Unrelated Machine Scheduling
  • Cloud Computing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amazon EC2 Pricing Options: https://aws.amazon.com/ec2/pricing/. Google Scholar
  2. Talal Al-Khamis and Rym M'Hallah. A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity. Computers & OR, 38(12):1747-1759, 2011. Google Scholar
  3. Gerard M. Campbell. A two-stage stochastic program for scheduling and allocating cross-trained workers. JORS, 62(6):1038-1047, 2011. Google Scholar
  4. Sivadon Chaisiri, Bu-Sung Lee, and Dusit Niyato. Optimization of resource provisioning cost in cloud computing. IEEE Trans. Serv. Comput., 5(2):164-177, 2012. Google Scholar
  5. Moses Charikar, Chandra Chekuri, and Martin Pál. Sampling bounds for stochastic optimization. In Proc. of APPROX and RANDOM 2005, pages 257-269, 2005. Google Scholar
  6. Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie, and José Verschae. Optimal algorithms and a PTAS for cost-aware scheduling. To appear in Proc. of MFCS 2015, 2015. Google Scholar
  7. Kedar Dhamdhere, Vineet Goyal, R. Ravi, and Mohit Singh. How to pay, come what may: Approximation algorithms for demand-robust covering problems. In Proc. of FOCS 2005, pages 367-376, 2005. Google Scholar
  8. Shane Dye, Leen Stougie, and Asgeir Tomasgard. The stochastic single resource service-provision problem. Naval Res. Logist., 50(8):869-887, 2003. Google Scholar
  9. Uriel Feige, Kamal Jain, Mohammad Mahdian, and Vahab S. Mirrokni. Robust combinatorial optimization with exponential scenarios. In Proc. of IPCO 2007, pages 439-453, 2007. Google Scholar
  10. Michel X. Goemans. Improved approximation algorthims for scheduling with release dates. In Proc. of SODA 1997, pages 591-598, 1997. Google Scholar
  11. Anupam Gupta, Martin Pál, R. Ravi, and Amitabh Sinha. Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems. SIAM J. Comput., 40(5):1361-1401, 2011. Google Scholar
  12. Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, and Mohammad R. Salavatipour. Two-stage robust network design with exponential scenarios. Algorithmica, 65(2):391-408, 2013. Google Scholar
  13. Anton J. Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM J. Optim., 12(2):479-502, 2001. Google Scholar
  14. Janardhan Kulkarni and Kamesh Munagala. Algorithms for cost aware scheduling. In Proc. of WAOA 2012, pages 201-214, 2013. Google Scholar
  15. Eugene L. Lawler and Jacques Labetoulle. On preemptive scheduling of unrelated parallel processors by linear programming. J. ACM, 25(4):612-619, 1978. Google Scholar
  16. Stefano Leonardi, Nicole Megow, Roman Rischke, Leen Stougie, Chaitanya Swamy, and José Verschae. Scheduling with time-varying cost: Deterministic and stochastic models. Presentation at the 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2013), 2013. Google Scholar
  17. Michael L. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, 2008. Google Scholar
  18. Maurice Queyranne and Maxim Sviridenko. A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective. J. Algorithms, 45(2):202-212, 2002. Google Scholar
  19. Andreas S. Schulz and Martin Skutella. Random-based scheduling: New approximations and LP lower bounds. In Proc. of APPROX and RANDOM 1997, pages 119-133, 1997. Google Scholar
  20. Andreas S. Schulz and Martin Skutella. Scheduling unrelated machines by randomized rounding. SIAM J. Discrete Math., 15(4):450-469, 2002. Google Scholar
  21. David B. Shmoys and Mauro Sozio. Approximation algorithms for 2-stage stochastic scheduling problems. In Proc. of IPCO 2007, pages 145-157. Springer, 2007. Google Scholar
  22. David B. Shmoys and Chaitanya Swamy. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM, 53(6):978-1012, 2006. Google Scholar
  23. René A. Sitters. Approximability of average completion time scheduling on unrelated machines. In Proc. of ESA 2008, pages 768-779, 2008. Google Scholar
  24. Martin Skutella. List scheduling in order of α-points on a single machine. In Evripidis Bampis, Klaus Jansen, and Claire Kenyon, editors, Efficient Approximation and Online Algorithms, volume 3484 of LNCS, pages 250-291. Springer, 2006. Google Scholar
  25. Chaitanya Swamy and David B. Shmoys. Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News, 37(1):33-46, 2006. Google Scholar
  26. Chaitanya Swamy and David B. Shmoys. Sampling-based approximation algorithms for multistage stochastic optimization. SIAM J. Comput., 41(4):975-1004, 2012. Google Scholar
  27. G. Wan and X. Qi. Scheduling with variable time slot costs. Naval Research Logistics, 57:159-171, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact