Skip to Main content Skip to Navigation
Conference papers

Scheduling independent stochastic tasks under deadline and budget constraints

Abstract : This paper discusses scheduling strategies for the problem of maximizing the expected number of tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The execution times of tasks follow IID probability laws. The main questions are how many processors to enroll and whether and when to interrupt tasks that have been executing for some time. We provide complexity results and an asymptotically optimal strategy for the problem instance with discrete probability distributions and without deadline. We extend the latter strategy for the general case with continuous distributions and a deadline and we design an efficient heuristic which is shown to outperform standard approaches when running simulations for a variety of useful distribution laws.
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-01868727
Contributor : Equipe Roma <>
Submitted on : Wednesday, September 5, 2018 - 5:17:35 PM
Last modification on : Wednesday, September 16, 2020 - 10:42:50 AM
Long-term archiving on: : Thursday, December 6, 2018 - 6:33:07 PM

File

sbacpad-cameraready.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01868727, version 1

Citation

Louis-Claude Canon, Aurélie Kong Win Chang, Yves Robert, Frédéric Vivien. Scheduling independent stochastic tasks under deadline and budget constraints. SBAC-PAD 2018 - 30th International Symposium on Computer Architecture and High Performance Computing, Sep 2018, Lyon, France. pp.1-8. ⟨hal-01868727⟩

Share

Metrics

Record views

269

Files downloads

250