Ordonnancement de tâches on-line avec pénalités

Nicolas Thibault (IBISC, Evry)

Nous nous intéressons au problème d'ordonnancement suivant. Soit un
ensemble de tâches révélées une par une (on-line). Chaque tâche représente
la requête d'un client et est définie par un triplet (r,d,p), où r est sa
date d'arrivée, d sa date d'échéance et p son temps d'exécution et son
poids. Lorsqu'une tâche est révélée, l'opérateur choisit de la rejeter ou
de l'ordonnancer sur une des k machines identiques du système. Pour cela,
l'opérateur peut interrompre une tâche déjà ordonnancée s'il paie à
celle-ci une pénalité proportionnelle à son poids. Étant données ces
contraintes, le but de l'opérateur est de maximiser la somme des poids des
tâches ordonnancées moins le total des pénalités accumulées. Pour résoudre
ce problème, nous proposons un algorithme on-line dont le rapport de
compétitivité, une fois le taux de pénalité fixé, est constant.