Resource-Constrained Scheduling of Stochastic Tasks With Unknown Probability Distribution

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.Ce travail présente des stratégies d’ordonnancement permettant de maximiser le nombre attendu de tâches indépendantes pouvant être exécutées sur une plateforme de type cloud avec un budget donné et une contrainte de date limite. Le temps d’exécution des tâches est inconnu, on sait seulement qu’ils obéissent à une distribution de probabilité (inconnue). L’ordonnanceur peut décider à tout moment d’interrompre l’exécution d’une tâche (longue) en cours d’exécution et d’en lancer une nouvelle, mais le budget déjà utilisé pour la tâche interrompue est perdu. Le seuil d’interruption d’une tâche peut être recalculé au fur et à mesure que l’exécution progresse globalement. Ce travail présente plusieurs stratégies pour déterminer un bon seuil d’interruption, et pour décider quand le ré-évaluer. Nous utilisons l’estimateur de Kaplan-Meier pour prendre en compte les tâches en cours d’exécution au moment où la décision est prise. L’efficacité de nos stratégies est évaluée via un vaste ensemble de simulations, avec diverses valeurs de budget et de date limite, et portant sur 14 distributions de probabilit