Geek or not

Accueil du site > MOCA > Problèmes d’ordonnancement

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 21 mars 2006.
4062 personnes ont affiché cette page et sa popularité est de 100.

Pebkac

Mots clefs

MPM
PERT

I see dead pixels.

Outils

SYN

Problèmes d’ordonnancement

Méthode MPM


Graphe déterminé à partir de la méthode MPM

Calcul des dates au plus tôt des différentes tâches : [1] [2]

$t_j = max( t_i + d_i )$ avec $i \in \Gamma^{-1}_{j}$ et $d_i$ est la durée de la tâche $i$

Calcul des dates au plus tard des différentes tâches :

$t^{*}_{j} = min( t^{*}_{k} - d_j )$ avec $k \in \Gamma_j$

Chemin critique :

Le chemin critique d’un ordonnancement est formé par la succession des tâches déterminantes pour la durée totale du projet. C’est à dire les tâches pour lesquelles un retard éventuel se répercute automatiquement sur la date de réalisation du projet.

Les méthodes de détermination sont les suivantes :

Appliquer un algorithme de recherche des plus longs chemins entre le sommet $D$ et les autres sommets [3]
Utiliser les dates au plus tôt en retrouvant la composition du plus long chemin entre le sommet $D$ et $F$
En regardant la ou les dates au plus tôt sont les dates au plus tard

Marge des différentes tâches :

Marge totale d’une tâche
C’est le délai dont on peut retarder cette tâche sans affecter la date d’achèvement du projet.
$M_j = t^{*}_{j} - t_j$
Marge libre d’une tâche
C’est le délai dont on peut retarder cette tâche sans affecter la date de réalisation au plus tôt des tâches suivantes.
$m_j = min( t_k - t_j - d_j )$ avec $k \in \Gamma_j$
Marge certaine d’une tâche
C’est le moment où les tâches précédentes commencent à leur date au plus tard et les tâches suivantes à leur date au plus tôt.
$\mu = min( t_k - max( t^{*}_{i} + d_i ) - d_j )$ avec $k \in \Gamma_j$ et $i \in \Gamma^{-1}_{j}$

Faire l’exercice Exercice 12

pages : << 1 2 3 >>

[1] Date pour laquelle les tâches précédent sont toutes terminées
[2] C’est donc la date maximale à laquelle se terminent les prédecesseurs de la tâche en question
[3] L’algorithme de Ford

Poster un message