Laurent Gourvès (LAMSADE, Paris)

"Jeux d'ordonnancement avec délais de mise en route (selfish scheduling with setup times)"

Laurent Gourvès, Jérôme Monnot, Orestis Telelis


On traite un problème sur m machines identiques. Chaque tâche est définie
par un type et une durée
d'exécution, tous deux connus. A chaque type est associée une mise en
route de durée connue et correspondant
au chargement d'une application (ou environement) nécessaire à l'exécution
de la tâche. Une machine excutant
plusieurs tâches d'un même type n'effectue la mise en route associée
qu'une seule fois. Cependant, si plusieurs
machines doivent exécuter des tâches d'un même type alors chacune doit
faire la mise en route.

On étudie une situation de jeu où chaque tâche est contrôllée par un
agent. Chaque agent cherche à placer sa
tâche sur la machine lui assurant une date de fin d'exécution minimale,
étant donnés les choix de placement des
autres agents. Les agents ne portent aucun intérêt à la qualité globale de
l'ordonnancement (ici, le makespan), seule
leur propre tâche compte.

On s'intéresse aux équilibres de Nash, situations où aucun agent n'a
intérêt à modifier son choix. On montre leur
existence pour toute instance du jeu, et on cherche à borner le rapport,
dans le pire cas, entre le
makespan induit par un équilibre de Nash et le makspan optimal. Des outils
algorithmiques sont envisagés afin de
réduire ce rapport.