Scheduling Independent Stochastic Tasks Under Deadline and Budget Constraints

  • Louis-Claude Canon CNRS ENS de Lyon Inria, Université Claude-Bernard Lyon 1
  • Aurélie Kong Win Chang CNRS ENS de Lyon Inria, Université Claude-Bernard Lyon 2
  • Yves Robert CNRS ENS de Lyon Inria, Université Claude-Bernard Lyon 3
  • Frédéric Vivien CNRS ENS de Lyon Inria, Université Claude-Bernard Lyon 4

Resumo


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.
Palavras-chave: Task analysis, Program processors, Optimal scheduling, Processor scheduling, Cloud computing, Computational modeling, Probability distribution, independent tasks, stochastic cost, scheduling, budget, deadline, cloud platform
Publicado
24/09/2018
Como Citar

Selecione um Formato
CANON, Louis-Claude; CHANG, Aurélie Kong Win; ROBERT, Yves; VIVIEN, Frédéric. Scheduling Independent Stochastic Tasks Under Deadline and Budget Constraints. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 30. , 2018, Lyon/FR. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . p. 33-40.