Supervision : Fanny PASCUAL

Ordonnancement en présence de plusieurs acteurs : de la théorie de l’ordonnancement au choix social computationnel

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. Une "tâche'' peut représenter tout évènement qui a une durée dans le temps : cela peut être l’exécution d’un programme informatique, la construction d’une infrastructure, ou bien la réservation d’une salle. Par "machine'', il faut entendre "ressource'', une ressource pouvant généralement héberger, ou traiter, une seule tâche à la fois. Les travaux dans ce domaine ont longtemps consisté à concevoir des algorithmes dont le but est d’optimiser soit l’utilisation des machines, soit la performance moyenne des tâches. Le but a ainsi souvent été de minimiser la date à laquelle toutes les tâches sont terminées, ou de minimiser la date de fin moyenne d’une tâche. Depuis le début des années 2000, des problèmes d’ordonnancement en présence de différents acteurs ont été étudiés. Ces travaux consistent généralement soit à étudier des situations d’équilibres quand des acteurs individualistes affectent eux-mêmes des tâches aux machines, soit à optimiser le critère d’un acteur, en ayant une borne sur le coût des autres acteurs. Très peu de critères d’équité ont été appliqués aux problèmes d’ordonnancement.
La théorie du choix social computationnel, domaine né au début des années 2000, utilise les concepts du choix social pour résoudre des problèmes issus de l’informatique. Elle étudie des problèmes variés comme la théorie du vote, le partage de ressources ou d'autres problème de décision collective.
On s’intéresse lors de cette thèse à des situations faisant intervenir le temps, et donc à des problèmes d’ordonnancement, où plusieurs personnes interviennent, chaque personne ayant ses propres intérêts ou ses propres préférences.

2021-2022 Publications

• 2022
  • M. Durand, F. Pascual, O. Spanjaard : “A Non-utilitarian Discrete Choice Model for Preference Aggregation”, Proceedings of the 15^th Scalable Uncertainty Management conference (SUM 2022), vol. 13562, Lecture Notes in Computer Science, Paris, France, pp. 157-171, (Springer International Publishing) (2022)
  • M. Durand, F. Pascual : “Collective Schedules: Axioms and Algorithms”, Symposium on Algorithmic Game Theory - SAGT 2022, vol. 13584, Lecture Notes in Computer Science, Colchester, United Kingdom, pp. 454-471, (Springer International Publishing) (2022)
  • M. Durand, F. Pascual : “Ordonnancements collectifs : Étude axiomatique et algorithmique”, 23^e congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Villeurbanne - Lyon, France (2022)
• 2021
  • M. Durand, F. Pascual : “Efficiency and Equity in the Multiple Organization Scheduling Problem”, International Workshop on Project Management and Scheduling, Toulouse, France (2021)
  • M. Durand, F. Pascual : “Efficiency and equity in the multi organization scheduling problem”, Theoretical Computer Science, vol. 864, pp. 103-117, (Elsevier) (2021)