Recherche opérationnelle

Ordonnancement et gestion de projets

Un projet, c'est une liste de tâches qui ne peuvent pas se faire dans n'importe quel ordre. Quand chacune doit-elle commencer ? Combien de temps durera l'ensemble ? Quelles tâches ne supportent aucun retard ? Et que se passe-t-il quand les ouvriers manquent ?

Le chantier de la page : construire un hangar agricole en onze tâches, de l'installation du chantier à la réception. Chaque tâche a une durée en jours ouvrés et mobilise un certain nombre d'ouvriers.

Le calendrier au plus tôt se construit tâche par tâche : chacune démarre dès que celles dont elle dépend sont finies. En rouge, les tâches qui fixent la date de fin.

Les données sont inventées. Les résultats sont calculés sur place dans votre navigateur et confrontés à une seconde méthode. Ce cahier contient déjà une page PERT et chemin critique, sur une maison de quatorze tâches, consacrée au tri topologique, au lissage des ressources, au compromis délai-coût et au biais du PERT. Celle-ci présente d'abord les bases, puis deux points que l'autre page ne traite pas : les liaisons avec chevauchement ou délai (méthode des potentiels), et le cas où les ouvriers sont trop peu nombreux pour tenir le délai.

Planche 1

Tâches, durées et relations de précédence

Une relation de précédence dit qu'une tâche ne peut pas commencer avant une autre. La plus courante est « fin-début » : on coule les fondations quand le terrassement est fini. Mais le réel en connaît d'autres : un délai obligatoire (le séchage d'un béton), ou un chevauchement (on commence la couverture avant la fin du montage). Bernard Roy, en 1958, a montré qu'on les traite toutes de la même façon : chaque liaison devient une inégalité entre dates de début, « S_j ≥ S_i + w ». C'est la méthode des potentiels.

Le graphe du projet : une boîte par tâche, une flèche par précédence, avec la valeur w de l'inégalité. Les boîtes sont placées selon leur date de début au plus tôt. Rouge : tâches critiques.

Séchage du dallage avant l'électricité (fin-début + délai)

–

Durée du chantier (méthode des potentiels)–

Contrôle : plus long des chemins énumérés–

Chemins du début à la fin–

Tâches critiques–

Relation	Exemple	Inégalité sur les débuts
Fin-début, avec délai l	Le béton sèche l jours avant l'électricité	S_j ≥ S_i + d_i + l
Début-début, avec décalage l	La couverture démarre 3 jours après le début du montage	S_j ≥ S_i + l
Fin-fin, avec décalage l	La couverture finit au moins 1 jour après le montage	S_j + d_j ≥ S_i + d_i + l

Ce qu'il faut retenir. Le séchage ne change rien jusqu'à 7 jours : le dallage a 7 jours de marge. Au-delà, chaque jour de séchage allonge le chantier d'un jour. Le chevauchement fait gagner 3 jours (27 → 24), mais rend le bardage critique : gagner du temps d'un côté en fait perdre la marge ailleurs. Enfin, une boucle de précédences rend tout calendrier impossible : la méthode la détecte, car les dates n'arrêtent jamais d'augmenter.

Planche 2

Le diagramme de Gantt

Henry Gantt le popularise vers 1910 : une ligne par tâche, une barre de sa date de début à sa date de fin. On y lit d'un coup d'œil qui travaille quand. Faites glisser les barres pour composer votre propre calendrier : les précédences violées s'affichent en rouge.

Faites glisser une barre horizontalement. Flèche rouge : précédence violée. En bas, le nombre d'ouvriers présents chaque jour.

–

Fin du chantier–

Précédences violées–

Pic d'ouvriers–

Travail total (ouvriers × jours)–

Ce qu'il faut retenir. Le Gantt est un affichage, pas une méthode : il montre un calendrier, mais ne dit pas lequel choisir. Tout au plus tôt, le chantier finit au 27e jour avec un pic de 7 ouvriers. Tout au plus tard, il finit aussi au 27e jour, mais le pic monte à 9 et la moindre surprise devient un retard. Entre les deux, chaque tâche a une liberté que les planches suivantes mesurent.

Planche 3

Les méthodes PERT et CPM

Deux méthodes sont nées presque ensemble, à la fin des années 1950. Le CPM (méthode du chemin critique, chez l'industriel Du Pont, 1957) suppose des durées connues. Le PERT (pour le programme de missiles Polaris de la marine américaine, 1958) donne trois estimations par tâche, pour tenir compte de l'incertitude. Les calculs de base sont les mêmes : deux passes sur le réseau.

Dans chaque boîte : en haut, début et fin au plus tôt ; en bas, début et fin au plus tard. Bleu : passe avant (de gauche à droite). Vert : passe arrière (de droite à gauche).

–

Passe avant : une tâche commence au plus tôt quand toutes ses devancières sont finies, soit le maximum de leurs dates de fin. Passe arrière : en partant de la fin du chantier, une tâche doit finir au plus tard quand sa première suivante doit commencer, soit le minimum de leurs dates de début au plus tard.

Pour chaque tâche : une durée optimiste a, la plus probable m, et une pessimiste b. Le PERT retient la moyenne (a + 4m + b) / 6 et l'écart-type (b − a) / 6, puis additionne le long du chemin critique. Le curseur d'incertitude écarte a et b de m.

Histogramme : durée du chantier sur 20 000 chantiers simulés, chaque tâche tirée selon sa loi bêta. Courbe : la loi normale annoncée par le PERT. Trait rouge : l'échéance.

Incertitude (1 = estimations du tableau)

Échéance promise au client

Durée moyenne selon le PERT–

Écart-type du chemin critique–

Probabilité de tenir l'échéance : PERT–

Probabilité mesurée sur 20 000 simulations–

Durée moyenne simulée–

Ce qu'il faut retenir. Le CPM donne le calendrier, le PERT y ajoute une probabilité. Mais le PERT ne regarde qu'un chemin : si un autre chemin presque critique prend du retard, il peut devenir le plus long. La simulation tient compte de tous les chemins, et donne une probabilité un peu plus basse. C'est l'objet de la planche 5 de la page PERT et chemin critique.

Planche 4

Chemin critique et marges : quelles tâches déterminent la durée ?

Le chemin critique est la suite de tâches la plus longue du début à la fin : sa longueur est la durée du chantier. Une tâche critique n'a aucune marge : le moindre jour de retard retarde tout. Les autres peuvent glisser. Cliquez sur une tâche, puis allongez-la ou raccourcissez-la.

Gantt au plus tôt. Barre pleine : la tâche. Vert : sa marge libre (glisser sans gêner personne). Vert clair : le reste de sa marge totale (glisser sans retarder le chantier, mais en repoussant une suivante). Cliquez sur une tâche pour la choisir.

Durée du chantier selon la durée de la tâche choisie, calculée pour chaque valeur. Plate tant que la marge l'absorbe, puis montant d'un jour par jour : le coude est à la marge totale.

Durée de la tâche

–

Marge totale ; marge libre–

Durée du chantier–

Effet d'un jour de plus ; d'un jour de moins–

Contrôle : coude de la courbe contre la marge totale–

Les 6 chemins du début à la fin, avec leur longueur. Le plus long est critique. Raccourcir une tâche critique fait gagner du temps, mais seulement jusqu'à ce qu'un autre chemin prenne le relais.

Ce qu'il faut retenir. Accélérer une tâche qui n'est pas critique ne sert à rien. Accélérer une tâche critique fait gagner un jour par jour, mais pas indéfiniment : raccourcir la couverture (G) fait gagner un jour par jour jusqu'à 1 jour de couverture (24 jours de chantier), puis plus rien : le chemin par le bardage (H), long de 24 jours, prend le relais. Le chemin critique n'est pas une propriété fixe des tâches, il dépend des durées. La tâche D (charpente) n'a qu'un jour de marge : elle est presque critique, et c'est elle qu'il faut surveiller après le chemin critique.

Planche 5

Ordonnancement avec ressources limitées

L'entreprise n'a que quelques ouvriers. Deux tâches qui se chevauchent dans le temps doivent maintenant tenir ensemble sous ce plafond. Le chemin critique ne suffit plus : le chantier peut durer bien plus longtemps que lui. On place les tâches une par une, dans un ordre donné par une règle de priorité, chacune au plus tôt là où les ouvriers sont disponibles.

En haut, le calendrier obtenu. Hachures : le retard subi par chaque tâche par rapport à sa date au plus tôt, faute d'ouvriers. En bas, les ouvriers présents chaque jour ; trait rouge : le plafond.

Ouvriers disponibles

–

Borne : chemin critique ; travail ÷ ouvriers–

Durée avec la règle choisie–

Optimum–

Contrôle : ordres d'exécution examinés–

Tâches retardées faute d'ouvriers–

Durée du chantier selon le nombre d'ouvriers : optimum (barres) et chaque règle (points). À partir de 6 ouvriers, l'optimum retrouve les 27 jours du chemin critique, mais certaines règles ont besoin de 7 ouvriers.

Ce qu'il faut retenir. Avec 6 ouvriers, il suffit de décaler des tâches dans leurs marges : 27 jours, comme sans contrainte. Avec 5, il faut allonger le chantier, à 31 jours au mieux. Les règles de priorité donnent des résultats très différents : 31, 34 ou 35 jours. Retenir la règle « fin au plus tard d'abord » est un bon réflexe, mais aucune règle n'est toujours la meilleure : à 4 ouvriers, « plus longue d'abord » gagne. Ici, on peut vérifier l'optimum en essayant les 139 ordres compatibles avec les précédences. Sur un vrai chantier de centaines de tâches, c'est impossible, et ce problème est l'un des plus difficiles de la recherche opérationnelle.

Ce qu'il faut garder

Le réseau

Des tâches, des durées, des précédences : chaque liaison, avec ou sans délai, devient une inégalité sur les dates. La plus longue chaîne de ces inégalités donne la durée du projet.

Les marges

Deux passes, avant et arrière, donnent les dates au plus tôt et au plus tard. Leur différence est la marge. Zéro marge : la tâche est critique. Une petite marge : elle est à surveiller.

Les ressources

Avec des ouvriers limités, le chemin critique ne dit plus tout. Les règles de priorité donnent vite un calendrier, sans garantie ; le meilleur calendrier est un problème difficile.

Pour aller plus loin

Dans ce cahier. PERT et chemin critique (tri topologique, lissage, compromis délai-coût, biais du PERT) ; La recherche opérationnelle (première rencontre avec l'ordonnancement) ; Introduction à la recherche opérationnelle (Bernard Roy et la méthode des potentiels, 1958).

Sur les calculs. Les dates s'obtiennent en relâchant les inégalités jusqu'à stabilité, comme un plus long chemin. Si elles augmentent encore après autant de passes qu'il y a de tâches, il existe une boucle. Pour le PERT, chaque durée suit une loi bêta de bornes a et b et de mode m ; les 20 000 chantiers sont recalculés en entier. Avec ressources, le placement tâche par tâche (schéma sériel) appliqué à tous les ordres compatibles avec les précédences atteint toujours l'optimum : c'est ce qui permet le contrôle exact.