Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadatas

Cited literature [54 references]  Display  Hide  Download

https://hal.inria.fr/hal-02989801
Contributor : Equipe Roma <>
Submitted on : Thursday, November 5, 2020 - 12:09:04 PM
Last modification on : Monday, November 16, 2020 - 9:56:04 AM

File

rr9373.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02989801, version 1

Citation

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⟩

Share

Metrics

Record views

25

Files downloads

66