Solution du problème 30 : De l’organisation de colloques au déchargement des camions, tout n’est qu’affaire de coloriage.
Dans les deux problématiques évoquées il s’agit de prendre en compte des contraintes d’incompatibilités temporelles d’usage de ressources tout en cherchant à optimiser la durée du projet constitué de l’ensemble des tâches à effectuer.
Dans le problème 1 les tâches à effectuer correspondent au déroulement des ateliers, les contraintes traduisent l’impossibilité du déroulement simultané de deux ateliers nécessitant le même expert. Les mathématiciens proposent de traduire ces données par la constitution d’un graphe (c’est à dire un réseau abstrait) dont les « sommets » (les noeuds) sont associés aux tâches et les contraintes sont traduites par des « arêtes » (les liaisons inter-noeuds). Les contraintes du projet décrit dans le Tableau 1 se résument par le Graphe 1 : graphe des incompatibilités
Les sommets sont associés aux ateliers et il existe un arc entre deux sommets si les ateliers associés ne peuvent se dérouler en même temps (car faisant appel au même expert). Ce faisant, nous n’avons fait que retraduire dans un autre langage l’énoncé du problème, il faut le résoudre. C’est là où interviennent les couleurs : colorons avec un minimum de couleurs différentes les sommets du graphe à condition que deux sommets adjacents (reliés par un arc) soient de couleurs différentes. Si on sait résoudre ce problème le planning sera fait car il suffit d’associer à chaque couleur une demi-journée de déroulement d’atelier.
Le recherche d’une solution optimale (au sens du nombre de couleurs) dans le cas général est assez complexe mais il est possible d’utiliser une procédure heuristique qui, sans assurer l’optimalité, fournit une bonne solution.
Appliquons la ici :
1. Rangeons les sommets dans l’ordre décroissant du nombre de liens adjacents : A8 (5 liens) puis A1 (4), A6 (4), A2, A5, A7, A3, A4.
2. En parcourant la liste attribuer une nouvelle couleur au premier sommet « incolore » rencontré et colorer avec cette couleur tous les autres sommets « incolores » non adjacent à un sommet de cette couleur.
3. Revenir en 2 tant qu’il reste des sommets « incolores »
Ce qui donne pour notre graphe le résultat suivant en n’utilisant que 3 couleurs (cf. Graphe 2 : coloration avec le rouge puis le vert et le bleu)
Le projet peut donc se dérouler en 3 demi-journées : la demi-journée rouge (A5,A8), la verte (A1,A3,A6) et la bleue (A2, A4,A7).
Remarquons que la solution trouvée est une des meilleures car on ne peut pas utiliser 2 couleurs seulement, il suffit de considérer le triangle A4, A5, A6 pour lequel il faut obligatoirement 3 couleurs.
Problème n°2 : On traitera avec la même méthode l’affectation des 4 prestataires de transports aux 6 quais de déchargement (Q1,Q2,...Q6). La tâche élémentaire est alors le couple prestataire-quai. Sur le plan de contraintes, non seulement un prestataire ne peut être sur 2 quais simultanément mais un quai ne peut recevoir qu’un seul prestataire à la fois.
Dans ce cas il est même possible de s’affranchir de la construction du graphe en considérant le Tableau 2 : il suffit de colorer toutes les cases « X » de telle sorte que la même couleur ne soit pas répétée dans une ligne ou une colonne. En appliquant la procédure on commencera par les cases qui ont le plus de voisines marquées « X ». On obtient le résultat suivant (cf. Tableau 3) :
Le déchargement peut s’effectuer en 3×20 min = 1 heure. Ici encore c’est une des solutions optimales car il existe des rangées avec 3 cases occupées donc trois tranches sont nécessaires au minimum.
Le planning de déchargement peut être le suivant (cf. Tableau 4) :
