Recherche Opérationnelle

Chapitre 3. Ordonancement des tâches

Graphes

1. Définitions élémentaires

Définition. Un graphe \(G = (X,U)\) est constitué :

– d’un ensemble fini \(X\) de points appelés sommets,

– d’un ensemble fini de lignes, appelées arêtes. Autrement dit, \(U\) une partie de \(X \times X\).

Chaque arête relie deux sommets appelés ses extrémités. Si deux extrémités d’une arête sont égales, on dit que l’arête est une boucle.

Un graphe simple est un graphe sans boucle dans lequel deux sommets sont reliés par au plus une arête.

Dans un graphe simple, une arête \(a_i\) est définie par ses extrémités \(s_i\) et \(s_i'\), on note \(a_i = s_is_i'\).

Deux sommets sont voisins s’ils sont reliés par une arête.

Le degré du sommet \(s_i\), noté \(d(s_i)\), est le nombre d’arêtes dont \(s_i\) est une extrémité.

Définition. Soit \(G\) un graphe. \(G'\) est un sous-graphe de \(G\) si \(G'\) est un graphe tel que les sommets de \(G'\) sont des sommets de \(G\) et les arêtes de \(G'\) sont des arêtes de \(G\).

Le sous-graphe engendré par un ensemble de sommets \(S'\) est le sous-graphe de \(G\) dont les arêtes sont \(S'\), avec toutes les arêtes possibles (c’est-à-dire toutes les arêtes de \(G\) dont les deux extrémités sont dans \(S'\)).

Définition. Un graphe orienté est un graphe où chaque arête est orientée par une flèche. Une arête orientée va d’une extrémité initiale à une extrémité finale.

Dans un graphe orienté

• \(d^+(s_i)\) est le nombre d’arêtes orientées ayant \(s_i\) comme extrémité initiale et
• \(d^−(s_i)\) est le nombre d’arêtes orientées ayant \(s_i\) comme extrémité finale.

Définition. Un chemin est une suite de sommets \([s_0 , s_1 ,\dots , s_p]\) telle que les arcs \((s_0 , s_1) , (s_1, s_2) , ..... , ( s_{p-1} , s_p )\) appartiennent au graphe. La valeur d’un chemin est alors la somme des valuations des arcs de ce chemin. La longueur d’un chemin est son nombre d’arcs.

Définition. Une chaîne est une suite d’arcs \(a_1\), \(a2\) , \(\dots\) , \(a_p\) telle qu’une extrémité de l’arc \(a_i\) (\(2 ≤ i ≤ p-1\)) est commune avec l’arc \(a_{i+1}\), alors que l’autre extrémité est commune avec l’arc \(a_{i-1}\). La longueur d’une chaîne est son nombre d’arcs.

2. Codage d’un graphe

2.1. Matrice associée :

Si on considère le graphe suivant

alors la matrice associée à ce graphe est donnée par \[ \mathcal{M}_G=\begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} \]

3. Théorème des poignées de mains

Soit \(G\) un graphe, \(S\) l’ensemble de ses sommets et \(n\) le nombre d’arêtes de \(G\). Alors \[ \sum_{s\in S}d(s)=2n \]

4. Distance

Définition. Soit \(G\) un graphe et \(s_i\), \(s_j\) deux sommets. La distance entre \(s_i\) et \(s_j\) est la plus petite longueur d’un chemin d”extrémité \(s_i\) et \(s_j\).

Dans un graphe orienté, la distance de \(s_i\) vers \(s_j\) est la plus petite longueur d’un chemin orienté allant de \(s_i\) à \(s_j\).

Ordonnancement des tâches

1. Introduction

L’ordonnancement est une démarche et une succession d’étape pour :

• mieux maitriser le déroulement d’un projet,
• meilleure visibilité.
• atteindre un objectif fixé dont la réalisation comporte un grand nombre des tâches successives.

Pour cela, On peut distinguer plusieurs méthodes telles que :

• La méthode PERT;
• La méthode MPM.

Ces méthodes d’ordonnancement ont été utilisées dans le domaine militaire, ensuite dans tous les domaines (économique, social).

Il s’agit d’ordonner dans le temps, un ensemble d’opérations contribuant à la réalisation du projet ; de respecter dans le déroulement de ces opérations des contraintes qui peuvent être :

Soit des contraintes d’antériorités : Une tâche \(j\) ne peut commencer que lorsqu’une tâche \(i\) est terminée ;(contrainte de succession). Soit des contraintes des dates : Une tâche ne peut commencer avant une certaine date. L’objectif consiste à minimiser la durée totale de réalisation du projet : compte tenu de la durée nécessaire à la réalisation de chacune des opérations et des contraintes qu’elles doivent respecter.

Dans la gestion d’un projet, la planification consiste à faire les étapes suivantes :

• Constituer la liste des différentes tâches à exécuter et leur durée ;
• Déterminer les relations de dépendance entre les tâches ;
• Déterminer les étapes critiques (qui n’admettent aucune prolongation) ;
• Ordonnancer les tâches dans le temps ;
• Indiquer les éventuelles contraintes.

2. Méthode PERT

La méthode PERT permet d’ évaluer la durée de réalisation d’un projet et de détecter les parties de ce projet ne supportant aucun retard.

Le projet sera subdivisé en tâches. En général, elles ne pourront toutes être réalisées simultanément, certaines tâches devront être achevées avant que d’autres ne puissent débuter.

On résumera l’information sur le projet sous la forme d’un tableau où seront indiquées les tâches, leur durée, et les contraintes d’antériorité à respecter.

Exemple :

Tâches	Tâches antérieures	Durée
A	–	6
B	–	5
C	A	4
D	B	6
E	C	5
F	A,D	6
G	E,F	4

Construction du graphe PERT :

Ce graphe sera un graphe dont les arcs seront les tâches, les valeurs des arcs étant leur durée et les sommets représenteront des états d’avancement du projet, numérotés de 1 à n. 

Le graphe devra respecter deux contraintes :

• en un sommet, toutes les tâches se trouvant sur un chemin \(y\) menant, doivent être achevées
• il n’y a pas d’arc de \(i\) vers \(j\) avec \(i\) est supérieur à \(j\).

Exemple :

Pour construire un graphe PERT dans le cas général, on procédera de la manière suivante : - Détermination des niveaux des tâches :

On attribuera le niveau 0 aux tâches qui n’ont pas de tâche antérieure.

On attribuera le niveau 1 aux tâches dont les tâches antérieures sont de niveau 0.

On déterminera ainsi le niveau de chaque tâche : les tâches de niveau \(k+1\) seront les tâches dont les tâches antérieures sont de niveau inférieur avec au moins une tâche de niveau \(k\) parmi elles.

On construira le graphe en traçant les tâches par ordre de niveau croissant. - Tâches commençantes, finissantes, convergentes :

Il sera souvent utile de détecter les tâches dites commençantes, finissantes ou convergentes.

Les tâches commençantes sont les tâches sans tâche antérieure, elles partent du sommet 1 du graphe (appelé entrée du graphe).

Les tâches finissantes sont les tâches qui ne sont pas tâche antérieure, elles arrivent au sommet terminal du graphe (appelé sortie).

Les tâches convergentes sont des tâches que l’on rencontre toujours ensemble (i.e. jamais l’une sans l’autre) dans la colonne “tâches antérieures”; dans le graphe, elles auront le même sommet terminal.

• Détermination des dates et des marges :

Une fois le graphe construit, on va déterminer les dates au plus tôt et au plus tard pour les différents sommets et les marges libres et totales pour les tâches.

Dates au plus tôt :

Pour un sommet, la date au plus tôt (notée : \(t\)) représente concrètement le temps minimum nécessaire pour atteindre ce sommet ( on ne peut pas faire mieux). Elle se déterminera de proche en proche, par ordre de sommet croissant, à partir de l’entrée du graphe, grâce à l’algorithme de Ford de recherche du chemin le plus long. Ainsi :

\(t_1 = 0\) et \(t_j = Max ( t_i + d_{ij} )\) sur tous les \(i\) précédant \(j\) avec \(d_{ij} =\) durée de la tâche \(ij\)

Dans l’exemple, \(t_1 = 0\), \(t_2 = 0+6 = 6\), \(t_3 = 0+5 = 5\), \(t_4 = 6+4 = 10\), \(t_5 = max ( 6+0 , 5+6 ) = 11\), \(t_6 = max ( 11+6 , 10+5 ) = 17\), \(t_7 = 17+4 = 21\).

La date au plus tôt de la sortie du graphe représente la durée minimale réalisable pour l’ensemble du projet ( dans l’exemple, \(t_7 = 21\), le projet durera donc au mieux 21 jours).

Dates au plus tard :

Pour un sommet, la date au plus tard (notée : T ) représente concrètement la date à laquelle cet état doit obligatoirement être atteint si l’on ne veut pas augmenter la durée totale du projet ( il ne faut pas faire pire ).

Elle se déterminera de manière analogue à \(t\), mais par ordre de sommet décroissant, depuis la sortie du graphe :

\(T_n = t_n =\) Durée du projet et \(T_i = Min ( T_j - d_{ij} )\) sur tous les \(j\) suivant \(i\).

Dans l’exemple, \(T_7 = 21\), \(T_6 = 21 - 4 = 17\), \(T_5 = 17 - 6 = 11\), \(T_4 = 17 - 5 = 12\), \(T_3 = 11 - 6 = 5\), \(T_2 = min ( 11-0 , 12-4 ) = 8\), \(T_1 = min ( 8-6 , 5-5 ) = 0\).

On aura toujours \(t_1 = T_1 = 0\) et \(t\) inférieur ou égal à \(T\) pour tout sommet.

On appelle \(T-t\) la marge de flottement du sommet.

Marges des tâches :

La marge libre d’une tâche représentera concrètement le retard maximal qu’on pourra prendre dans la réalisation d’une tâche sans retarder le début des tâches suivantes, on la notera \(ML\).

La marge totale d’une tâche représentera concrètement le retard maximal qu’on pourra prendre dans la réalisation d’une tâche sans retarder l’ensemble du projet, on la notera \(MT\).

Si on note \(ij\) la tâche allant du sommet \(i\) au sommet \(j\) : \[ML_{ij} = t_j - t_i - d_{ij} \qquad \text{ et }\qquad MT_{ij} = T_j- ti - d_{ij}\] Compte tenu du mode calcul, les marges seront toujours positives ou nulles et la marge libre d’une tâche sera toujours inférieure ou égale à sa marge totale.

On qualifiera de critique, une tâche dont la marge totale est nulle, c’est en quelque sorte une tâche “urgente”, une tâche sur laquelle il ne faut pas prendre de retard si l’on ne veut pas augmenter la durée totale du projet.

Si la durée d’une tâche augmente, une partie de cette augmentation sera absorbée par la marge de la tâche, seul le surplus se répercutera sur la durée du projet. Exemple :

Tâches	A	B	C	D	E	F	G
ML	0	0	0	0	2	0	0
MT	2	0	2	0	2	0	0

Ainsi , dans l’exemple, si la durée de la tâche E augmente de 7 jours, le projet durera 26 jours, soit 5 jours de plus (2 jours seront absorbés par la marge de la tâche E)

3. Méthode MPM

La Méthode des Potentiels Métra (MPM) est une technique d’ordonnancement basée sur la théorie des graphes, visant à optimiser la planification des tâches d’un projet.

Elle aurait été mise au point en 1958 par un chercheur français, Bernard Roy, au sein de la société de conseil Métra, dans le cadre du projet de construction du paquebot “France”.

Bien que le PERT se soit d’abord imposé en matière de gestion de projet, la MPM tend, depuis les années 1980, à le supplanter. Cette méthode s’avère, en effet, beaucoup plus souple et mieux adaptée à une automatisation du traitement des données (notamment en terme de représentation graphique et d’algorithme de calcul).

L’utilisation de la MPM permet, notamment, de déterminer la durée minimum nécessaire pour mener à bien un projet et les dates auxquelles peuvent ou doivent débuter les différentes tâches nécessaires à sa réalisation pour que cette durée minimum soit respectée.

Considérant le tableau suivant :

Comment se construit le graphe MPM ?

Première étape : classer les tâches par niveau : - Niveau 1 : tâches qui peuvent commencer immédiatement en début de projet (pas de contraintes d’antériorité).

• Niveau n : Tâches dont les tâches antérieures sont au maximum de niveau n-1.

Exemple :

Tâche	Durée (en semaine)	Tâches précédentes
A	6	-
B	2	-
C	7	B
D	8	B
E	3	A C
F	4	E D

Détermination des niveaux

\[\begin{array}{|c|c|} \hline Niveau & Tâches\\ \hline 1 & A B \\ \hline 2 & C D \\ \hline 3 & E \\ \hline 4 & F \\ \hline \end{array}\]

Deuxième étape : tracer le graphe.

Troisième étape : Calculer les dates et les marges.

• Date au plus tôt :

Date à laquelle on peut commencer la tâche parce que les tâches précédentes sont terminées.

formule : = Max (Dates au plus tôt précédentes + durées précédentes).

• Date au plus tard :

Date maximale à laquelle on peut commencer la tâche sans repousser la fin du projet.

formule : = Min (Date au plus tard suivantes) - durée de la tâche.

• Marge totale :

Retard autorisé à la tâche sans retarder la fin du projet.

formule : = Date au plus tard - Date au plus tôt.

• Marge libre :

Retard autorisé sans retarder aucune des tâches suivantes.

formule : = Min (Dates au plus tôt suivantes) - Durée de la tâche - Date au plus tôt de la tâche.

Quatrième étape : tracer le(s) chemin(s) critique(s).

• Tâche critique :

Tâche qui ne peut être retardée sans que l’ensemble du projet soit retardé en conséquent. Ce sont les tâches dont la marge totale est nulle.

• Chemin critique :

Séquence des tâches critiques, du début à la fin du projet. Il peut y avoir plusieurs chemins critiques.

Exercices Chapitre 1.

L’entreprise Duralumin fabrique pour des entreprises de quincaillerie, des pièces en inox. Ces pièces sont de trois types : A,B,C. Elles sont fabriquées par lots de 50 dans un grand atelier où sont rassemblées deux machines pour la découpe de l’inox, une machine pour l’emboutissage, deux machines pour le polissage et la finition. Chaque machine fonctionne 120 heures par mois.

Les caractéristiques de fabrication sont rassemblées dans le tableau suivant : \[\begin{equation} \begin{array}{|c|c|c|c|c|} \hline & \text { Coût de l'heure } & \text { Lot A } & \text { Lot B } & \text { Lot C } \\ \hline \text { Découpe } & 20 \text { € } & 1 {~h} & 1,5 {~h} & 1,5 {~h} \\ \text { Emboutissage } & 30 \text { € } & 0,5 {~h} & 0 {~h} & 1 {~h} \\ \text { Polissage et finition } & 40 \text { € } & 2 {~h} & 1 {~h} & 1 {~h} \\ \hline \text { Inox } & & 50 \text { € } & 85 \text { € } & 68 \text { € } \\ \text { Prix de vente (hors taxe) } & & 200 \text { € } & 200 \text { € } & 210 \text { € } \\ \hline \end{array} \end{equation}\]

1. Calculer la marge unitaire de chaque lot.
2. Montrer que le programme de production qui maximise le résultat s’écrit \[\begin{equation} max(Z=35 x+45 y+42 z)\\ sc : \left\{\begin{array}{l} x \geq 0, y \geq 0, z \geq 0 \\ x+\frac{3}{2} y+\frac{3}{2} z \leq 240 \\ \frac{1}{2} x +z\leq 120\\ 2 x+y +z\leq 240 \end{array}\right. \end{equation}\]
3. Déterminer et résoudre le problème dual.

Exercices Chapitre 2.

Exercice 1. On donne :

Tâche	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P
T. antérieures	I P	A C H	G		I P	A		I P		A G	M N O	A F K	D E	I P	D E	G
Durée	3	5	2	4	8	1	7	5	5	6	3	4	7	1	2	6

1. Déterminer les niveaux.
2. Méthode PERT :

• Construire le graphe PERT.
• Déterminer la durée minimale de réalisation de ce projet.
  

3. Méthode MPM :

• Construire le graphe MPM.
• Déterminer la durée minimale de réalisation de ce projet.

4. Calculer les marges

Exercice 2. La mise en exploitation d’un nouveau gisement minier demande la réalisation d’un certain nombre de tâches. Le tableau suivant représente ces différentes tâches avec leurs relations d’antériorité.

\[ \begin{array}{|c|l|c|c|} \hline \text { Tâche } & \text { Description } & \begin{array}{r} \text { Durée (enjours)} \\ \end{array} & \begin{array}{r} \text { Tâches antérieures} \end{array} \\ \hline \text { A } & \text { obtention d'un permis d'exploitation } & 120 & - \\ \hline \text { B } & \text { établissement d'une piste de } 6 {~km} & 180 & {~A} \\ \hline {C} & \begin{array}{l} \text { transport et installation à pied d'œurre } \\ \text { de } 2 \text { sondeuses } \end{array} & 3 & {~B} \\ \hline {D} & \begin{array}{l} \text { création de bâtiments provisoires pour } \\ \text { le bureau des plans, le logement des } \\ \text { ouvriers sondeurs } \end{array} & 30 & {~B} \\ \hline {E} & \text { goudronnage de la piste } & 60 & {~B} \\ \hline {F} & \text { adduction d'eau } & 90 & {D} \\ \hline {G} & \text { campagne de sondage } & 240 & {C}, {D} \\ \hline {H} & \text { forage et équipement de trois puits } & 180 & {E}, {F}, {G} \\ \hline {I} & \begin{array}{l} \text { transport et installation au fond du } \\ \text { matériel d'exploitation } \end{array} & 30 & {~J}, {H} \\ \hline {J} & \begin{array}{l} \text { construction de bureaux et logements, } \\ \text { ouvriers et ingénieurs } \end{array} & 240 & {E}, {F}, {G} \\ \hline {K} & \text { traçage et aménagement du fond } & 360 & {~J}, {H} \\ \hline {L} & \text { construction d'une laverie } & 240 & {~J}, {H} \\ \hline \end{array} \]

1. Déterminer les niveaux.
2. Méthode PERT :

• Construire le graphe PERT.
• Déterminer la durée minimale de réalisation de ce projet.

3. Méthode MPM :

• Construire le graphe MPM.
• Déterminer la durée minimale de réalisation de ce projet.

4. Calculer les marges

Exercice 3. La réalisation d’un projet exige que soient effectuées dix opérations A, B, C, D, E, F, G, H, I, J.

Les conditions d’antériorité qui relient ces tâches figurent dans la matrice associée ci-dessous :

\[Départ\] \[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline & {A} & {B} & {C} & {D} & {E} & {F} & {G} & {H} & {I} & {J} \\ \hline {A} & & & & & & & & & & \\ \hline B & 1 & & & & & & & & & \\ \hline C & 1 & & & & & & & & & \\ \hline D & & & & & & & & & & \\ \hline E & 1 & & 1 & & & & & & & \\ \hline F & 1 & & 1 & & 1 & & & & & \\ \hline G & 1 & 1 & 1 & & & & & & & 1 \\ \hline H & & & & 1 & & & & & & \\ \hline I & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & & 1 \\ \hline J & 1 & & 1 & & & & & & & \\ \hline \end{array}\] Les durées des tâches sont les suivantes : \[\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|} \hline Tâches & A & B & C & D & E & F & G & H & I & J \\ \hline Durée & 4 & 8 & 5 & 2 & 12 & 4 & 7 & 10 & 6 & 5 \\ \hline \end{array}\]

Mêmes questions

Exercice 4. Une entreprise décide de lancer un nouveau produit sur le marché. Les services commerciaux ont déterminé l’ensemble des tâches nécessaires à cette action : {a, b, c, d, e, f, g, h, i, j, k}.

Les conditions d’antériorité liant ces tâches et les durées de celle-ci sont rassemblé dans le tableau ci-dessous :

\[\begin{equation} \begin{array}{|c|c|c|} \hline \text { Tâches } & \text { Tâches antérieures } & \text { Durée des tâches } \\ \hline {A} & {E} & 4 \\ \hline {B} & {J}, {E} & 6 \\ \hline {C} & \text { Aucune } & 12 \\ \hline {D} & \text { Aucune } & 14 \\ \hline {E} & \text { Aucune } & 8 \\ \hline {F} & {D} & 2 \\ \hline {G} & {F}, {D} & 10 \\ \hline {H} & {A}, {C}, {D} & 6 \\ \hline {I} & {H}, {A}, {C}, {E}, {K}, {D}, {F} & 8 \\ \hline {J} & {E} & 12 \\ \hline {K} & {F}, {D} & 2 \\ \hline \end{array} \end{equation}\] Mêmes questions