Chez Ptit Gars

Accueil > Informatique > RCP101 : Recherche opérationnelle et aide à la décision > PERT

PERT

lundi 13 juillet 2009, par Pti Gars

METHODE MPM (méthode des potentiels Metra- 1958)

Graphe potentiel tâche

  • Graphe orienté sans circuit de valeur positive :
    • sommets : tâches
    • arcs : contraintes d’antériorité entre deux tâches valués avec la durée de la tâche
  • La recherche du plus long chemin sur le graphe valué par les durées des tâches détermine la date au plus tôt de réalisation du projet.
  • Ce plus long chemin est appelé chemin critique

METHODE PERT (1956- Program evaluation and review technique)

  • Graphe potentiels événements
  • Graphe orienté sans circuit de valeur positive
    • sommets= événements : fin ou début de tâche.
    • Arcs :
      • opérations élémentaires du processus
      • valués par délais d’exécution
  • La recherche du plus long chemin sur le graphe valué par les durée des tâches détermine la date au plus tôt de réalisation du projet.
  • Ce plus long chemin est appelé chemin critique

i : Numéro de tâche
t_{i} : dates de début au plus tôt
t*_{i} : date de début au plus tard

Recherche du plus long chemin :

  • Date au plus tôt de fin de projet
  • Chemin critique

MARGE : Période pendant laquelle une tâche peut glisser dans le temps sans affecter les dates d’une autre tâche ou la date de fin du projet.

Marge totale mesure le degré de liberté dont on dispose pour programmer une tâche sans remettre en cause la durée d’exécution minimale du projet.

= Différence entre la date de début au plus tard et la date de début au plutôt de chaque tâche

Marge libre : Espace de temps pendant lequel on peut recalculer une tâche sans retarder d’autres Tâches

Différence entre la date de début au plus tôt du descendant (successeur) le plus précoce – 1 et la date de fin au plus tôt de la tâche
Exemple : LA tâche 1 se termine fin de semaine 18 et la tâche 2 commence en début de semaine 19, il y a donc une marge entre les deux tâches = (19-1)-18 = 0

Exemple

valeur des marges

  • marges certaines M_{i} = t*_{i} - t_{i}
    • application :
      • Ma= 0-0=0 ; Mb=1-0=1 ; Mc=3-0=3 ; Md=4-3=1 ; Me=5-3=2 ; Mf=6-6=0 ; Mg=9-9=0
  • Marges libres : m_{i} = min(tj - ti-vi) j \in \Gamma +(i)
    • application :
      • m_{a}=min(tf-ta-6)=6-0-6=0 ;
      • m_{b}=min(td-tb-3) ; (te-tb-3)= min(3-0-3) ; (3-0-3)=0
      • m_{c}=min(tg-tc-6)= min(9-0-6)=3
      • m_{d}=min(tf-td-2)= min(6-3-2)=1
      • m_{e}=min(tg-te-4)= min(9-3-4)=2
      • m_{f}=0 ;mg=0