Groupe d’études et de recherche en analyse des décisions

Coloration d'arêtes par intervalle: une réduction du problème standard au problème

Sivan Altinakar Polytechnique Montréal, Canada

Dans un graphe, une \(k\)-coloration d'arêtes associe une couleur entière dans \(\{1,...,k\}\) à chaque arête, tel qu'aucun sommet ne peut avoir deux arêtes adjacentes de même couleur. Cette formulation est utile pour modéliser des problèmes d'ordonnancement, par exemple lorsque dans une chaîne de production, un ensemble d'objets doivent être chacun traités en temps unitaires par un sous-ensemble de machines (sans ordre particulier). Ici, un sommet correspond à un objet ou à une machine, une arête entre une paire de tels sommets à la contrainte qu'un objet doit être traité par une machine, et une couleur à la case horaire pendant laquelle le traitement se produit. Dans des cas réels, il y a beaucoup de contraintes supplémentaires à ce problème simple, par exemple lorsqu'une machine ne peut pas rester inoccupée entre sa première et sa dernière tâche, et qu'il n'y a pas de place pour mettre en attente un objet entre son premier et son dernier traitement. Pour notre coloration, cela signifie que pour chaque sommet, l'ensemble des couleurs des arêtes qui y sont adjacents doit, en fonction du problème, soit former un intervalle d'entiers standard (un ensemble d'entiers consécutifs) ou un intervalle d'entiers cyclique (1 est consécutif à \(k\)).

Le but de cet exposé est de présenter une réduction du cas standard au cas cyclique du problème de coloration d'arêtes par intervalle (pour k plus grand ou égal à 12), ainsi que des manières de modéliser d'autres problèmes d'ordonnancement cyclique en termes de coloration d'arêtes par intervalle cyclique, à l'aide des outils développés pour la réduction.