Le problème d'ordonnancement multi-organisations (POMO) modélise des situations où plusieurs organisations indépendantes, par exemple des universités, possèdent chacune des tâches à exécuter et des ressources qui permettent l'exécution des tâches. Par exemple, chaque université peut avoir un cluster de machines servant à exécuter des programmes informatiques soumis par les membres de l'université.
Chacune peut choisir d'exécuter des tâches sur ses machines, obtenant ainsi une solution dite "locale". Le but du problème POMO est d'étudier comment ces organisations peuvent coopérer et partager leurs machines afin d'obtenir une solution dite "globale" plus satisfaisante pour toutes les organisations impliquées. Dans la solution globale les tâches peuvent être exécutées sur n'importe quelle machine, sans restriction sur l'organisation qui la possède.
Pour vérifier qu'aucune organisation n'est pénalisée par le partage de ressources, on introduit une contrainte, appelée contrainte de rationalité, qui stipule que dans la solution globale, aucune organisation ne doit être moins satisfaite que dans sa solution locale, la satisfaction d'une organisation étant exprimée par une fonction objectif connue.
On sait qu'il existe toujours une solution qui satisfait la contrainte de rationalité, on cherche donc une solution qui respecte cette contrainte et qui minimise une fonction objectif donnée.
Le projet consiste en l'implémentation de méthodes de résolution exactes pour le problème POMO à l'aide de deux méthodes principales : la programmation linéaire et, possiblement, la programmation par contrainte (étudiée dans l'UE Résolution de Problème, il est donc fortement recommandé de suivre cette UE si vous choisissez ce projet). A l'issue de ce travail d'implémentation, il faudra également tester les deux méthodes et comparer leur temps d'exécution. On pourra également implémenter d'autres méthodes heuristiques à titre de comparaison.
L'implémentation se fera à priori en Python, mais peut également se faire dans un autre langage si les étudiants le souhaitent.
Adresse mail de contact: martin.durand@lip6.fr