Le modèle PERT (Program Evaluation and Review Technique)

C'est un graphe où les tâches et les contraintes de précédence sont représentées par des arcs. Les sommets correspondent à des instants privilégiés du déroulement du processus : les dates de début et de fin de chaque tâche. Les arcs représentant les tâches ont pour coût $d_i$ alors que les arcs de précédence ont un coût nul. On rajoute deux sommets fictifs représentant respectivement les dates de début et de fin du projet. Le ``réseau'' PERT est très proche du diagramme de Gantt mais permet de modéliser les contraintes. Il a été mis au point aux Etats-Unis pour résoudre les problèmes liés à la construction de sous-marins nucléaires.

Figure 4.2: Réseau PERT associé au problème du chantier