Scheduling independent stochastic tasks deadline and budget constraints - Franche-Comté Electronique, Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2018

Scheduling independent stochastic tasks deadline and budget constraints

Résumé

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.
Fichier principal
Vignette du fichier
rr9178.pdf (860.2 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01811885 , version 1 (11-06-2018)

Identifiants

  • HAL Id : hal-01811885 , version 1

Citer

Louis-Claude Canon, Aurélie Kong Win Chang, Yves Robert, Frédéric Vivien. Scheduling independent stochastic tasks deadline and budget constraints. [Research Report] RR-9178, Inria - Research Centre Grenoble – Rhône-Alpes. 2018, pp.1-34. ⟨hal-01811885⟩
162 Consultations
186 Téléchargements

Partager

Gmail Facebook X LinkedIn More