Algorithmes pour l'ordonnancement équitable

Les problèmes d'ordonnancement traitent de l'affectation de tâches à des machines, et de l'exécution de ces tâches au cours du temps : il s'agit de savoir où - sur quelle machine - et quand commencera chaque tâche.
Les travaux en théorie de l’ordonnancement ont longtemps consisté à concevoir des algorithmes centralisés dont le but est d'optimiser soit l'utilisation des machines, soit la performance moyenne des tâches. Très peu de critères d'équité ont été étudiés (hormis le critère classique qui consiste à minimiser le coût maximal d'un agent). Nous nous intéressons ici au calcul d’un ordonnancement équitable et plus particulièrement d’un ordonnancement « sans envie ».

Plus précisément, le problème considéré est le suivant : n agents possèdent chacun k tâches à exécuter sur un ensemble de m machines partagées. Chaque tâche est supposée avoir la même durée de 1 unité de temps. Chaque agent possède un objectif : il souhaite par exemple minimiser la date moyenne des dates de fin de ses tâches, ou bien la date maximale de fin de ses tâches. Les tâches peuvent éventuellement avoir des deadlines, et dans ce cas le but d’un agent peut être de minimiser le nombre de ses tâches en retard, ou bien la somme des retards de ses tâches. Un ordonnancement peut-être vu comme un problème d’allocation des tâches des agents, aux machines. Sur chaque machine, chaque tâche est associée à un slot (créneau de temps où elle sera exécutée). Un ordonnancement associe donc à chaque agent un ensemble de slots sur des machines, au cours desquels les tâches de l’agent seront exécutées. Nous souhaitons retourner un ordonnancement sans envie c’est-à-dire tel qu’aucun agent ne préfère l’ensemble des slots d’exécution affectés à un autre agent.

Nous avons développé des algorithmes permettant de calculer des ordonnancements équitables basés sur l’algorithme du round-robin, dans lequel les agents choisissent chacun leur tour un slot de temps disponible pour exécuter une de leurs tâches. L’objectif de ce projet est d’implémenter ces algorithmes et de permettre leur évaluation expérimentale via la mise en place d’un générateur automatique d’instances. Selon le souhait des étudiants, il pourra également être possible de proposer et d'implémenter de nouveaux algorithmes retournant des ordonnancements équitables. Le langage préconisé est Python.

Encadrants : Aurélie Beynier, Fanny Pascual, Nicolas Maudet

Encadrant: 
Beynier, Pascual, Maudet
Nombre d'étudiants: 
2
Attribué: 
No
Deprecated: 
Yes

User login