Graphes et planification

mardi 29 décembre 2020
par  Alain BUSSER

Le programme de mathématiques en terminale technologique se termine par ce texte :

initiation aux graphes ; ordonnancement.

Dans cet article on va voir comment la théorie des graphes permet d’ordonnancer les tâches accomplies par les membres d’une équipe appelée communauté de l’Anneau.

Le problème de l’ordonnancement des tâches consiste à établir un planning pour les membres de l’équipe, tenant compte de contraintes comme celle-ci :

La tâche Gollum trouve l’anneau doit avoir lieu avant la tâche Isildur perd l’anneau mais avant la tâche Bilbon prend l’anneau à Gollum.

On représente ces contraintes par des arcs entre les tâches, dont la signification est « doit être effectuée avant » :

Pour trouver un chemin critique, on va

  • construire un graphe (orienté et sans cycle) des tâches.
  • effectuer sur ce graphe, un tri topologique.

PERT

La méthode PERT s’applique aux cas où on connaît la durée de chaque tâche (et on cherche à optimiser la durée totale). On ne la traitera pas ici.

Le sujet a déjà été traité en concours :

Même le Capes s’intéresse à ces questions, avec

Pour ordonnancer les tâches dans la communauté de l’Anneau, on propose de construire le graphe des tâches à l’aide du module graphviz de Python, puis de chercher à l’œil un éventuel tri topologique sur ce graphe. Ce tri existe car le graphe est un graphe acyclique orienté.

Le graphe est orienté (si la tâche A doit être accomplie avant la tâche B, l’inverse n’est pas vrai). L’anglais directed graph est abrégé en digraph :

Le graphe orienté s’appelle g :

  1. from graphviz import *
  2. g = Digraph(format="png")

Télécharger

On y crée les sommets par la méthode node de cet objet :

  1. g.node("fin","Frodon jette l'anneau en Mordor")
  2. g.node("f1","Frodon l'anneau")
  3. g.node("f2","Frodon entre en Mordor")

Télécharger

Le graphe, constitué de ses seuls sommets, est incomplet :

Pour en faire un vrai graphe, on utilise la méthode edge du graphe g, par exemple pour expliquer que les tâches Frodon prend l’anneau et Frodon entre en Mordor doivent être effectuées avant la tâche finale Frodon jette l’anneau en Mordor, on entre

  1. g.edge("f1","fin")
  2. g.edge("f2","fin")

Télécharger

ce qui donne le graphe

Pour l’instant, rien ne permet de savoir laquelle des deux tâches Frodon entre en Mordor et Frodon prend l’anneau doit être effectuée en premier. On continue donc la construction du graphe (mais rien n’exclut, a priori, l’existence de plusieurs solutions à ce problème d’ordonnancement de tâches).

Le graphe des tâches

Voici un script possible pour la construction du graphe des tâches :

  1. from graphviz import *
  2. g = Digraph(format="pdf")
  3. g.node("g1","Gollum trouve l'anneau")
  4. g.node("g2","Bilbon prend l'anneau")
  5. g.node("i2","Isildur perd l'anneau")
  6. g.node("fin","Frodon jette l'anneau en Mordor")
  7. g.node("f1","Frodon prend l'anneau")
  8. g.node("f2","Frodon entre en Mordor")
  9. g.node("g3","Gollum sort de prison")
  10. g.node("g4","Gollum captif en Mordor")
  11. g.node("pn","bataille de la porte noire")
  12. g.node("m1","Gandalf devient le blanc")
  13. g.node("m2","Saroumane exclu")
  14. g.node("m3","Gandalf perdu dans la Moria")
  15. g.node("mp1","Merry captif")
  16. g.node("mp2","Pippin captif")
  17. g.node("mp3","rencontre avec les Ents")
  18. g.node("mp4","bataille de l'Isengard")
  19. g.node("i1","Isildur prend l'anneau")
  20. g.node("g5","Aragorn capture Gollum")
  21. g.node("g6","Gollum se sauve en Moria")
  22. g.node("S1","Sauron forge l'anneau")
  23. g.node("S2","Sauron perd l'anneau")
  24. g.node("S3","Les soldats trahissent")
  25. g.node("S4","Les soldats morts-vivants")
  26. g.node("S5","Aragorn rescussite les soldats")
  27.  
  28. g.edge("i2","g1")
  29. g.edge("g1","g2")
  30. g.edge("f1","f2")
  31. g.edge("f2","fin")
  32. g.edge("i2","f2")
  33. g.edge("g2","g4")
  34. g.edge("g2","f1")
  35. g.edge("g4","g3")
  36. g.edge("g6","f2")
  37. g.edge("pn","f2")
  38. g.edge("mp4","pn")
  39. g.edge("mp3","mp4")
  40. g.edge("mp1","mp3")
  41. g.edge("mp2","mp3")
  42. g.edge("mp4","m2")
  43. g.edge("m2","m1")
  44. g.edge("m3","m1")
  45. g.edge("m1","pn")
  46. g.edge("i1","i2")
  47. g.edge("m3","mp1")
  48. g.edge("m3","mp2")
  49. g.edge("f1","g6")
  50. g.edge("g6","m3")
  51. g.edge("g3","g5")
  52. g.edge("g5","g6")
  53. g.edge("S1","S2")
  54. g.edge("S2","i1")
  55. g.edge("S1","S3")
  56. g.edge("S3","S2")
  57. g.edge("S3","S4")
  58. g.edge("i1","S4")
  59. g.edge("S4","S5")
  60. g.edge("S5","pn")
  61. g.edge("m1","S5")
  62.  
  63. g.render("ordonnancement",view=True)

Télécharger

Son exécution produit le graphe que voici :

On voit que par défaut, graphviz essaye de montrer (de haut en bas) un ordre topologique. Celui-ci consiste en un résumé du livre le Seigneur des anneaux mais avec des choix possibles (par exemple Gollum peut s’évader du Mordor avant, ou après, que Bilbon donne l’anneau à Frodon).

Tâches et processus

Si on assimile chacun des personnages cités ci-dessus à un processus (informatique), alors chacun n’effectue sa (ou ses) tâche qu’après avoir attendu que les tâches précédentes aient été effectuées.

Par exemple, Bilbon attend que Gollum perde l’anneau pour le prendre, et ensuite, Frodon attend que Bilbon lui cède l’anneau pour commencer à accomplir sa mission qui est de détruire l’anneau.

De même, depuis qu’Isildur les a condamnés à être des sortes de processus zombies, les soldats de l’armée des Morts sont en attente d’être éveillés afin de racheter leur faute. C’est Aragorn qui les sollicite pour gagner la bataille des Champs de Pelennor et ainsi réussir à attirer l’attention de Sauron suffisamment, durant la bataille de la Porte Noire, pour permettre à Frodon de détruire l’anneau en Mordor. Cela a pour effet de libérer les soldats fantômes et de les placer dans l’état « terminé » qu’ils attendaient depuis des millénaires.

D’autres changements d’état apparaissent dans cette histoire, l’un des plus notables étant la transformation du magicien mineur Gandalf le gris, en Gandalf le blanc, remplaçant de Saroumane.

Processus et interblocage

Cette partie est au programme de NSI [1]. Comme pour un réseau de Petri, on convient de représenter les processus par des sommets circulaires, et les sommets rectangulaires représentent des ressources avec lesquelles les processus interagissent de deux manières différentes :

  • un arc allant du processus Frodon vers la ressource anneau, signifie que l’anneau est actuellement avec Frodon, et ne peut être utilisé par un autre processus :
  • un arc allant de la ressource anneau vers le processus Sauron signifie, au contraire, que Sauron a besoin de l’anneau :

Comme la ressource anneau est à la fois possédée par Frodon et voulue par Sauron, il y a une situation de blocage. Celle-ci ne peut être résolue que lorsque Frodon abandonne l’anneau permettant ainsi à Sauron de le récupérer :

Mais il y a une autre situation de blocage, concernant la ressource Mordor, avec une situation inverse de la précédente :

Là c’est Sauron qui dispose de la ressource Mordor (il y est installé) alors que Frodon en a besoin (il doit y aller pour détruire l’anneau qui est en sa possession).

La présence simultanée de ces situations de blocage constitue un interblocage.

Le cas présent a été décrit par Edsger Dijkstra dans cet article de 1971 sous le nom de dîner des philosophes. Dans cet autre article de 1971, E. Coffman définit la notion d’interblocage (mais sans les réseaux de Petri).

Pour rappel, voici un jeu sur réseau de Petri :

Jeu sur réseau de Petri

D’autres jeux sont visibles ici :

Jeux sur réseaux de Petri

La présence de cycles de ce genre empêche l’existence d’un chemin critique dans le graphe des tâches. De fait, la situation d’interblocage n’est levée que parce que Gandalf, Aragorn et les autres incitent Sauron à abandonner la ressource Mordor pour la bataille de la Porte Noire...

Je te vois

Dans Le Seigneur des anneaux (série de films), à chaque fois que quelqu’un met l’anneau, l’œil de Sauron se tourne vers lui et il entend la voix caverneuse de Sauron dire d’un ton menaçant « Je te vois ». Cette phrase est également perçue comme menaçante lorsqu’elle est prononcée par Dark Vador dans Star Wars. Ce qui peut expliquer que, lorsqu’un professeur de philosophie a prononcé ces trois mots devant Nicolas Sarkozy, ledit professeur a immédiatement été placé en garde à vue.

Pourtant, dans Avatar (film, 2009), prononcés par un na’vi, ces mots signifient plutôt « je me sens en phase avec toi » qui n’a pas grand-chose de menaçant. Le caractère injurieux de cette phrase reste donc à démontrer...

Ceci dit, la phrase « je te vois » est une relation. Cette relation n’est pas transitive (si Bilbon voit Gandalf en portant l’anneau, ce qui fait qu’à ce moment, Sauron voit Bilbon, cela ne signifie pas nécessairement que Sauron voit Gandalf). Mais si on suppose qu’elle l’est, la sémantique de Kripke permet d’appliquer des graphes orientés à la logique modale. Un exemple (concernant plus paticulièrement la logique temporelle) est visible ici.

Voici une introduction à la logique temporelle et une autre, à la logique épistémique.

Transposé dans le domaine de l’agencement de tâches, il s’agit alors essentiellement de savoir si l’ensemble des tâches sera accompli en un temps fini. On a vu dans cet article que cela dépend essentiellement de la présence ou absence de cycles dans le graphe.

L’existence de chemins critiques dans les diagrammes PERT nous apprend que le succès d’une tâche dépend essentiellement de l’efficacité des « petites mains » (le début du graphe des tâches ; ceux dont le travail profite aux managers). Ce qui est illustré par le principe de Peter et plus encore par le principe de Dilbert : donner un poste de responsabilité à une petite main, c’est courir le risque de se priver de ses compétences là où on en a le plus besoin. Dans le récit de Tolkien, on voit d’ailleurs des refus de promotion :

  • Dans un premier temps, Gandalf préfère laisser à Saroumane le rôle de mage blanc.
  • Sam préfère porter Frodon portant l’anneau, plutôt que porter l’anneau directement.
  • Et Galadriel, lorsque Frodon lui propose l’anneau, dit le mot de la fin :

De grandes choses viennent parfois de petites personnes.


[1L’extrait intéressant ici est le suivant :

Décrire la création d’un processus, l’ordonnancement de plusieurs processus par le système.
Mettre en évidence le risque de l’interblocage (deadlock).


Commentaires