Skip to Main content Skip to Navigation

Resource-Constrained Scheduling of Stochastic Tasks With Unknown Probability Distribution

Abstract : This work introduces scheduling strategies to maximize the expected numberof independent tasks that can be executed on a cloud platform within a given budgetand under a deadline constraint. Task execution times are not known before execution;instead, the only information available to the scheduler is that they obey some (unknown)probability distribution. The scheduler needs to acquire some information before decidingfor a cutting threshold: instead of allowing all tasks to run until completion, one maywant to interrupt long-running tasks at some point. In addition, the cutting thresholdmay be reevaluated as new information is acquired when the execution progresses further.This works presents several strategies to determine a good cutting threshold, and to decidewhen to re-evaluate it. In particular, we use the Kaplan-Meier estimator to account fortasks that are still running when making a decision. The efficiency of our strategies isassessed through an extensive set of simulations with various budget and deadline values,and ranging over 14 probability distributions.
Document type :
Complete list of metadata

Cited literature [54 references]  Display  Hide  Download
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Thursday, November 5, 2020 - 12:09:04 PM
Last modification on : Saturday, September 11, 2021 - 3:19:00 AM
Long-term archiving on: : Saturday, February 6, 2021 - 7:07:32 PM


Files produced by the author(s)


  • HAL Id : hal-02989801, version 1


Yiqin Gao, Yves Robert, Frédéric Vivien. Resource-Constrained Scheduling of Stochastic Tasks With Unknown Probability Distribution. [Research Report] RR-9373, Inria - Research Centre Grenoble – Rhône-Alpes. 2020. ⟨hal-02989801⟩



Record views


Files downloads