Chez Adesoft, nous sommes persuadés que les recherches et les technologies peuvent nous aider à accomplir de grandes choses ! Dans cette optique, nous avons toujours pensé nos solutions pour qu’elles soient à la pointe de l’innovation. Nos équipes R&D se démènent chaque jour pour trouver la solution la plus optimale, la réponse la plus efficace, l’utilisation la plus simple pour vous. Afin d’aller encore plus loin dans notre volonté d’innover, nous vous avions annoncé que nous faisions appel à l’UTT (Université Technologique de Troyes) dans le cadre d’un partenariat. Presque un an après, où en sommes-nous ?

Dans cet article, découvrez les prémisses du travail commun que nous avons mené afin d’intégrer la théorie des graphes à nos solutions de planification. Pénétrez dans l’envers du décor et déchiffrez avec nous cette technique !

La théorie des graphes en elle-même

Pour commencer, la théorie des graphes, qu’est-ce que c’est ?

Comme vous pouvez le constater, dans “théorie des graphes”, il y a “graphes”. En somme, un graphe est une structure qui est utilisée afin de modéliser un cas dans lequel plusieurs objets sont interconnectés. Pour mieux visualiser ces graphes, vous pouvez vous appuyer sur l’illustration ci-dessous, les liens entre les utilisateurs d’un réseau social comme LinkedIn étant de bons exemples. Un graphe a donc des sommets, qui représentent les utilisateurs du réseau social, et des arêtes, qui relient deux personnes si elles sont connectées entre elles dans le réseau social.

De manière plus formelle, la “théorie des graphes” est un domaine mathématique étudiant les représentations des graphes, leurs explorations et les algorithmes manipulant ces structures. Le tout, permettant de résoudre les problèmes de graphes, qui modélisent des problèmes du monde réel dans de nombreux domaines, en particulier l’information, les réseaux, les bases de données et la planification des emplois du temps.

La théorie des graphes et la planification

L’un des exemples pour lequel la théorie des graphes est utilisée est la coloration des graphes. Cette dernière consiste à colorer les sommets avec un ensemble de couleurs de manière à ce que chaque sommets adjacents (ayant une arête commune) soit colorés avec des couleurs différentes. L’exemple qui est souvent utilisé est lorsque l’on souhaite colorer les pays d’une carte en voulant colorer les pays voisins avec des couleurs différentes. Fun fact : 4 couleurs suffisent pour colorer tous les pays du monde !

Et du coup, comment appliquer la théorie des graphes à la planification ?

Essayons de voir comment la coloration de graphes peut être utilisée dans les problèmes de planification d’emplois du temps. Supposons que nous ayons N évènements à planifier. Chacun de ces évènements pouvant utiliser mj ressources parmi les R ressources dont nous disposons. Nous créons alors un graphe où les sommets sont les évènements. Puis, nous relions les évènements i, j… par une arête s’ils utilisent la même ressource. L’arête signifie que les évènements sont en conflit et ne peuvent pas être programmés en même temps. Le graphe résultant est appelé graphe de conflit.

Si nous appliquons un algorithme puissant de coloration de graphes sur le graphe de conflit, nous pouvons attribuer un créneau horaire à chaque couleur de nos évènements et les programmer en fonction de leurs couleurs. Nous pouvons alors nous assurer qu’il n’y aura pas de conflits en termes d’utilisation des ressources. Il s’agit d’une modélisation simpliste d’un problème de planification. En pratique, nous gérons de nombreuses contraintes de disponibilité des ressources et de charge de travail qui sont toutes traitées et intégrées dans ADE.

Ressources mobilisées :

Ganguli, R. & Roy, S. (2017), A study on course timetable scheduling using graph coloring approach, International Journal of Computational and Applied Mathematics, 12(2), 469-485.

Redl, T. A. (2007), University timetabling via graph coloring: An alternative approach, Congressus Numerantium, 187, 174.

Miner, S., Elmohamed, S. & Yau, H. W. (1995), Optimizing timetabling solutions using graph coloring, NPAC, Syracuse University, 99-106.