Présentation de la méthode des potentiels ou de la méthode "PERT"
Différents ordonnancements
Un problème d'ordonnancement de projet à ressources illimitées n'a en général pas qu'une seule solution, mais de très nombreuses solutions possibles (voire une infinité si on ne limite pas le temps).
Aussi, on s'intéresse à des ordonnancements ayant des propriétés particulières : en particulier, l'ordonnancement au plus tôt qui minimise la date à laquelle le projet sera terminé et qui donne un maximum de sécurité par rapport à des retards potentiels ou au contraire, l'ordonnancement au plus tard pour terminer à une date donnée qui permet d'engager les frais associés à la réalisation de chaque tâche le plus tard possible.
Nous allons définir ces ordonnancements, puis montrer comment on peut les obtenir en utilisant des algorithmes de cheminement.
Tâches fictives de début et de fin de projet
Si un graphe potentiel-tâches comporte plusieurs tâches sans prédécesseur, on ajoute une tâche fictive numérotée 0 qui correspond au fait que l'on démarre le projet.
Si un graphe potentiel-tâches comporte plusieurs tâches sans successeur, on ajoute une tâche fictive numérotée n+1 qui correspond à la constatation que le projet est complétement fini.
On peut ajouter cette tâche fictive numérotée n+1 même s'il y a une seule tâche finale, de manière à pouvoir constater que la dernière tâche est effectivement finie (on ajoute ainsi sa durée sur le dernier arc).
Définition : Ordonnancement au plus tôt
On note ASAP(i) (pour As Soon As Possible) l'instant de début au plus tôt de la tâche i.
On donne arbitrairement la valeur 0 à la tâche 0.
Fondamental :
ASAP(i) est égal à la longueur du plus long chemin de la tâche 0 à la tâche i.
Exemple d'un graphe potentiel-tâches avec tâche fictive de début et de fin
Algorithme de calcul des dates au plus tôt
On peut utiliser les algorithmes de cheminement qui calculent le plus long chemin de 0 à tout point i.
Ces algorithmes de cheminement ont été présentés dans le module de base sur la théorie des graphes (présenté pour rechercher des plus courts chemins, il faut les modifier légèrement pour obtenir des plus longs chemins).
Comme notre graphe est sans circuit et ne contient qu'un seul point sans prédécesseur,
on peut résumer ainsi la méthode la plus simple qui peut être utiliser ici et qui correspond également à une approche de calcul des plus longs chemins en utilisant la programmation dynamique.
Pour tout i faire
ASAP(i)=-1;
fin pour tout i;
ASAP(0)=0;
nbc=1;
tantque nbc < n faire
pour tout point i tel que ASAP(i)=-1 et ASAP(j)>-1 pour tous les prédécesseurs j de i faire
ASAP(i) = la plus grande valeur des (ASAP(j)+aj,i) pour tous les j prédécesseurs de i
nbc=nbc+1 ;
finpourtout i;
fintantque;
Exemple de calculs des dates au plus tôt
Le numéro des tâches est en noir. Les dates au plus tôt sont en rouge.
Définition : Ordonnancements au plus tard
On note ALAP(i) (pour As Late As Possible) l'instant de début au plus tard de la tâche i.
Un ordonnancement au plus tard particulier est tel que ALAP(n+1)=ASAP(n+1),
il s'agit de l'ordonnancement au plus tard qui termine au plus tôt.
Mais on peut également se donner une date de fin au plus tard D > ASAP(n+1)
et calculer l'ordonnancement au plus tard pour terminer à la date D, tout l'ordonnancement au plus tard est alors décalé de D.
Algorithme de calcul des dates au plus tard
On peut utiliser les algorithmes de cheminement qui calculent le plus long chemin de n+1 à tout point i et on obtient la date au plus tard ALAP(i) en prenant ALAP(n+1) et en lui ôtant la longueur du plus long chemin de i à n+1.
En utilisant directement la programmation dynamique, on peut aussi résumer ainsi l'algorithme de calcul des dates au plus tard.
Pour tout i faire
ALAP(i)=+∞;
Fin pour i;
ALAP(n+1)=ASAP(n+1) ou D;
nbc=1;
tantque nbc < n faire
pour tout point i tel que ALAP(i)=+∞ et ALAP(j)<+∞ pour tous les successeurs j de i faire
ALAP(i) = la plus petite valeur des (ALAP(j)-ai,j) pour tous les j successeurs de i
nbc=nbc+1 ;
finpourtout
fintantque
Exemple de calculs des dates au plus tard pour terminer au plus tôt
Le numéro des tâches est en noir. Les dates au plus tôt sont en rouge.
Les dates au plus tard pour terminer au plus tôt sont en bleu.
Exemple de calculs des dates au plus tard pour terminer à une date donnée
Le numéro des tâches est en noir. Les dates au plus tôt sont en rouge.
Les dates au plus tard pour terminer à l'instant 30 sont en bleu.
Définition : Ordonnancement quelconque
On note t(i) la date de début de la tâche i pour un ordonnancement réalisable quelconque.
On a ASAP(i) ≤ t(i) ≤ ALAP(i).
Mais aussi t(i) + ai,j ≤ t(j) pour toute contrainte de précédence.
Définition : Marges totales
Pour un ordonnancement quelconque, on note MT(i) la marge totale de la tâche i.
On a : MT(i) = ALAP(i)-t(i)
Remarque :
Si toutes les autres tâches sont sans problème, la marge totale de la tâche i correspond au maximum de retard que l'on peut prendre sur la tâche i en suivant l'ordonnancement t sans remettre en cause la date de fin prévue pour le projet (ALAP(n+1)).
Néanmoins, ce retard pourra nécessiter de remettre en cause la partie de l'ordonnancement t qui suit la tâche i.
Définition : tâches critiques, chemins critiques, sous-graphes critiques
Une tâche critique a une marge totale nulle.
Un chemin est critique si toutes les tâches correspondantes sont critiques et si les arcs (i,j), qui le composent, vérifient ti = tj + ai,j.
Le sous-graphe critique est composé de la réunion de tous les chemins critiques.
Remarque :
Si ALAP(n+1)=ASAP(n+1), alors il existe au moins un chemin critique qui va de 0 à n+1.
Calcul des marges totales pour l'ordonnancement au plus tôt correspondant aux deux exemples précédents
Le numéro des tâches est en noir. Les dates au plus tôt sont en rouge. Les dates au plus tard pour terminer au plus tôt sont en bleu.
Les marges totales par rapport à l'ordonnancement au plus tôt sont en vert.
Le graphe comporte un chemin critique.
Le numéro des tâches est en noir. Les dates au plus tôt sont en rouge. Les dates au plus tard pour terminer à l'instant 30 sont en bleu.
Les marges totales par rapport à l'ordonnancement au plus tôt sont en vert.
Définition : Marges libres (à droite)
Soit t un ordonnancement quelconque et i une tâche quelconque (1≤i≤n).
mi,j=t(i)-ai,j ;
min = min(mi,j) pour les tâches j qui suivent i.
ML(i)=min-t(i)
Remarque :
Quand ai,j= durée de i, ML(i) représente le maximum de retard que l'on peut prendre sur la tâche i sans avoir à changer la partie de l'ordonnancement t qui suit la tâche i.
Les deux exemples précédents sont complétés avec un ordonnancement quelconque et ses marges libres
En violet l'ordonnancement quelconque généré aléatoirement. En vert derrière les marges libres de cet ordonnancement.
Animation sur l'algorithme "PERT"
cliquez sur Anim et laissez vous guidez par les explications fournies afin de calculer en pas à pas, l'ordonnancement au plus tôt, l'ordonnancement au plus tard décalé d'une valeur que vous pouvez choisir, les marges totales avec éventuellement les chemins critiques et pour finir, vous pouvez générer de manière aléatoire un ordonnancement quelconque et calculer ses marges libres.
