Ordonnancements collectifs

Les problèmes d'ordonnancement, où l'on cherche à affecter à une tâche une date de début et une date de fin dans le temps, sont des problèmes très utilisés et très étudiés depuis des décennies. Une problématique très récente consiste à étudier ces problèmes dans le cas où plusieurs utilisateurs partagent des tâches communes à ordonnancer, et ont chacun leur opinion sur l'ordonnancement souhaité.

Cette problématique peut être rencontrée par exemple dans le cas de l'ordonnancement de travaux publics (chaque utilisateur - citoyen - a des préférences sur l'ordre de travaux à effectuer). Elle peut aussi être rencontrée dans le cas du partage d'une salle commune (chaque tâche - spectacle, conférence, etc - est plus ou moins "urgente" selon les utilisateurs).

Le problème consiste alors, étant donné les ordonnancements préférés de plusieurs individus, de retourner un ordonnancement collectif, qui est un bon compromis des ordonnancements préférés des individus. Ainsi, cette thématique est à la frontière du domaine de l'ordonnancement et de celui du choix social.

Le but de ce projet est :

d'implémenter des algorithmes pour résoudre ces problèmes. Ces algorithmes seront

- des algorithmes gloutons qui sont des adaptations au problème de l'ordonnancement d'algorithmes connus dans un autre contexte en choix social.

- des algorithmes venus du domaine de l'ordonnancement. Il pourra ici s'agir d'heuristiques ou d'algorithmes exacts (via un solveur de programmes linéaires en nombres entiers, ou un algorithme de branch and bound).

De concevoir une interface simple d'utilisation permettant de visualiser des ordonnancements préférés par des utilisateurs et de voir l'ordonnancement collectif proposé.

Selon l'avancement du stage et les goûts des étudiants, il peut également être intéressant de proposer et d'implémenter de nouvelles heuristiques retournant un ordonnancement collectif, ou de proposer une interface évoluée ou une application en ligne.