Stochastic and Robust Scheduling in the Cloud
| Autor: | Chen, Lin, Megow, N., Rischke, R., Stougie, L., Garg, N. |
|---|---|
| Přispěvatelé: | Garg, N., et al., null, Econometrics and Operations Research, Amsterdam Business Research Institute, Freie Universität Berlin, Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Vrije Universiteit Amsterdam [Amsterdam] (VU), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centrum Wiskunde & Informatica (CWI), Evolutionary Intelligence |
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
000 Computer science
knowledge general works Stochastic Optimiza- tion Unrelated Machine Scheduling [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Robust Optimization SDG 8 - Decent Work and Economic Growth 0102 computer and information sciences 02 engineering and technology Cloud Computing 01 natural sciences 010201 computation theory & mathematics Computer Science 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Approximation Algorithms |
| Zdroj: | Chen, L, Megow, N, Rischke, R & Stougie, L 2015, Stochastic and Robust Scheduling in the Cloud . in N Garg & et al. (eds), Leibniz International Proceedings in Informatics Volume 40 . Schloss Dagstuhl, Leibniz, pp. 175-186, APPROX 2015, 24/08/15 . https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.175 Leibniz International Proceedings in Informatics Volume 40, 175-186 STARTPAGE=175;ENDPAGE=186;TITLE=Leibniz International Proceedings in Informatics Volume 40 Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), Aug 2015, Princeton, United States. pp.175-186, ⟨10.4230/LIPIcs.APPROX-RANDOM.2015.175⟩ |
| DOI: | 10.4230/LIPIcs.APPROX-RANDOM.2015.175 |
| Popis: | International audience; 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 Pj 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|