next up previous
suivant: Conséquence monter: Le problème de l'ordonnancement précédent: Le modèle Potentiel-tâches

Résolution

Que ce soit en utilisant le modèle PERT ou le modèle Potentiel-Tâches, la solution du problème d'ordonnancement est donnée par la résolution d'un problème de plus long chemin (donné par l'algorithme de Bellmann) entre le début et la fin du projet. En effet, si l'on recherche le plus long chemin, celui-ci va utiliser le plus grand nombre de tâches possibles en suivant les arcs les plus longs. Le graphe ne contient pas de circuit car les contraintes de précédence fournissent un ordre partiel sur les tâches. On utilisera donc une forme adaptée de l'algorithme de Bellmann pour calculer les plus longs chemins.
\begin{defi}[Chemin critique]
On appelle \emph{chemin critique} tout plus long chemin entre
le d\'ebut et la fin du projet.
\end{defi}

\begin{theo}[R\'esultats sur le graphe Potentiel-t\^{a}ches]
Soit un graphe p...
... est $L$
\item $\pi_i=p_i$
\item $\eta_i=L-q_i$
\end{enumerate}
\end{theo}


Sous-sections

Bruno Garcia 2000-12-17