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
- les graphes d’intervalles
- l’allocation de registres qui est un problème voisin (on y trouve notamment la notion de tri topologique).
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 :
from graphviz import *
g = Digraph(format="png")On y crée les sommets par la méthode node de cet objet :
g.node("fin","Frodon jette l'anneau en Mordor")
g.node("f1","Frodon l'anneau")
g.node("f2","Frodon entre en Mordor")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
g.edge("f1","fin")
g.edge("f2","fin")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).
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).
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 :
D’autres jeux sont visibles ici :
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...
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.
Commentaires