Planification Et Gestion de Projet

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE.

Ministre de l'Enseignement Suprieur et de la Recherche Scientique.

UNIVERSITE MOULOUD MAMMERI, TIZI-OUZOU

Facult des Sciences

Dpartement de Mathmatiques

Mmoire d'ingnieur d'tat

en

Recherche Oprationnelle

Thme

Planication et gestion de projets.

Cas:

Ralisation d'une station terminale El-Kala au sein du groupement

SAIPEM.

Prsent par

AOUACHE Farid et BELHARET Mourad

Encadr par

Dr OUKACHA BRAHIM

Devant le jury d'examen compos de :

AIDENE Mohamed Professeur UMMTO Prsident

OUKACHA Brahim M.C.A UMMTO Rapporteur

OUANES Mohand M.C.A UMMTO Examinateur

LOUADJ Kahina M.C.B UMMTO Examinatrice

BENALIA Karim SAIPEM Invit

Soutenu le 11 / 07 / 2012

Remerciements

Nous remercions Dieu de nous avoir donn la force et la volont de mener ce projet terme.

Nous exprimons notre plus grande reconnaissance et nos plus vifs remerciements notre pro-

moteur : Dr OUKACHA Brahim ainsi qu' notre encadreur : BENALIA Karim pour leurs soutiens

dans la direction du projet et pour avoir guid ce travail en conjuguant habilement disponibilit,

conseils et critiques constructives.

Nous remercions aussi tous nos camarades de la facult des mathmatiques en particulier nos

amis de la promotion. On leur exprime notre profonde sympathie et leur souhaitant beaucoup de

bien.

Nous n'oublierons pas le grand mrite de nos chers parents qui nous ont soutenus et apports

un appui moral.

Nous remercions aussi chaleureusement nos professeurs pour la qualit de leurs enseignements.

Enn, que tous ceux et celles que nous avons involontairement oublis et qui ont particip de

prs ou de loin la ralisation de ce modeste travail, trouvent ici l'expression de notre gratitude.

Le binme :

F. AOUACHE et M. BELHARET

Ddicaces

Je ddie ce modeste mmoire

A ma trs chre mre et mon trs cher pre pour leur dvouement, leur disponibilit, leur

sacrice et leur aection tout au long de mes tudes.

A mon frre et sa femme Fatima et a mes trs chres surs Lynda et Siham et leurs enfants

Zo et Abdou

A ma tres chre Sabiha qui m'a tellement soutenue durant tout ce temps l.

A tous mes amis (es) en particulier Nacima,Nora, Rak, Mimo, Amar, Chaea et Mouloud.

A tous mes amis de la promotion RO 2011-2012.

Mourad

Je ddie ce modeste mmoire

A ma trs chre mre et mon trs cher pre pour leur dvouement, leur disponibilit, leur

sacrice et leur aection tout au long de mes tudes.

A mes frre, Boussad et Hakim, ma soeur Samira, son mari Hakim et leur lle Noira, mon oncle

Amo.

A ma grande famille en particulier, le petit Sami, Lamia, et Dyhia.

A ma tres chre Kaly qui m'a tellement soutenue durant tout ce temps l.

A mes amis (es), Dahmane, Zina, Eva, Faya, Moumouh, Malik, Mimo amazigh, chikh Chaea,

Rak, Nora, et clodio. A tous mes amis de la promotion RO 2012.

A toutes les personnes que je connaissent et qui m'ont aider de prs ou de loin.

Farid

2

Table des matires

Introduction gnrale 9

1 Gnralits et dnitions 12

1.1 Transport par canalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1.1 Gaz naturel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1.2 Gazoduc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1.3 Oloduc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.1.4 Les terminaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2 Projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2.1 Tche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2.2 Jalon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2.3 Ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2.4 Le triangle du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2.5 La gestion de projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.2.6 Les tapes de la gestion des projets . . . . . . . . . . . . . . . . . . . . . . . 16

1.2.7 La planication de projet ( tape prvisionnelle) . . . . . . . . . . . . . . . . 17

1.2.7.1 Consistance : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.2.7.2 Objectifs : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.2.8 WBS ( Work Breakdown Structure )(structure de rpartition de travaille) . . 17

1.2.9 OBS (Organisation Breakdown Structure ) . . . . . . . . . . . . . . . . . . . 18

1.2.10 Matrice RACI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.2.11 Cahier des charges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.2.11.1 Dnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.2.11.2 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.2.11.3 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3 Thorie des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3.1 Dnitions et concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.3.1.1 Qu'est-ce qu'un graphe? . . . . . . . . . . . . . . . . . . . . . . . . 20

1.4 Modes de reprsentation d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.4.1 Listes de succession . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.4.2 Matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.4.3 Matrice d'incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.5 Etude de la connexit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.5.1 Chanes et cycles, lmentaires et simples . . . . . . . . . . . . . . . . . . . . 24

1.5.2 Chemins et circuits, lmentaires et simples . . . . . . . . . . . . . . . . . . 24

1.5.3 Graphes connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.5.4 Graphes fortement connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1

1.5.5 Rseaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.6 Utilisation de la technique de la programmation linaire . . . . . . . . . . . . . . . . 25

1.7 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.8 Gnralits sur la programmation linaire . . . . . . . . . . . . . . . . . . . . . . . 25

1.8.1 Dnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.8.2 Forme matricielle classique et quelque conversions . . . . . . . . . . . . . . . 26

1.8.3 Algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.8.4 La notion de dualit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.8.5 Les lments d'un modle d'optimisation . . . . . . . . . . . . . . . . . . . . 27

2 Modlisation du problme d'ordonnancement du projet 29

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.2 Reprsentation AoA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.2.1 Graphe de la mthode PERT . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3 Reprsentation des activits sur les nuds ( AoN) . . . . . . . . . . . . . . . . . . . 33

2.3.1 Graphe de la mthode du potentiel . . . . . . . . . . . . . . . . . . . . . . . 33

2.4 Modlisation par la programmation linaire . . . . . . . . . . . . . . . . . . . . . . . 34

2.4.1 L'ordonnancement avec les contraintes temporelles . . . . . . . . . . . . . . . 34

2.5 La mthode PDM (Precedence Diagramming Method) . . . . . . . . . . . . . . . . 35

2.5.1 Dnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5.2 Mthodologie de construction d'un graphe PDM . . . . . . . . . . . . . . . . 35

2.5.3 Etablir la liste des tches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.5.4 Dterminer les conditions d'antriorit . . . . . . . . . . . . . . . . . . . . . 39

2.5.5 Estimer les ressources ncessaires aux activits. . . . . . . . . . . . . . . . . 40

2.5.6 Estimer la dure de chaque tche. . . . . . . . . . . . . . . . . . . . . . . . 40

2.5.7 Elaborer l'chancier. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.5.8 Classement des tches par rang ou par niveaux. . . . . . . . . . . . . . . . . 42

2.5.9 Tracer le rseau PDM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.5.10 Calculer les dates " au plus tt " et " au plus tard " . . . . . . . . . . . . . 43

2.5.11 Calculer les marges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.5.12 Dterminer le chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.5.13 Algorithme de recherche d'un plus court chemin . . . . . . . . . . . . . . . . 45

2.5.14 Construction du diagramme de Gantt. . . . . . . . . . . . . . . . . . . . . . 46

2.6 Rsum des mthodes de planications . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.7 Mthode de la chane critique( CCPM ) . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.7.1 La thorie de la chane critique . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.7.2 Les cinq eets indsirables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.8 Processus de planication par la chane critique . . . . . . . . . . . . . . . . . . . . 53

2.8.1 La performance humaine sur la chane critique . . . . . . . . . . . . . . . . . 55

2.8.2 Comment eectuer la mise en place de cette mthode . . . . . . . . . . . . . 58

2.9 Suivi des cots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

2.9.1 Les donnes de rfrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

2.9.2 Les donnes rvises date t . . . . . . . . . . . . . . . . . . . . . . . . . . 642.9.3 Les grandeurs comparer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2.9.4 Analyse de l'cart de planning . . . . . . . . . . . . . . . . . . . . . . . . . . 65

2.9.5 Analyse de l'cart du cot . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.10 Comparaison entre le chemin critique et la chane critique . . . . . . . . . . . . . . . 67

2

3 Application des techniques d'ordonnancement notre projet 69

3.1 Prsentation du groupement SAIPEM . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.1.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.1.2 Organigramme du SAIPEM . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.1.3 Domaines d'activits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.1.3.1 Les titres de forages enregistrs par SAIPEM . . . . . . . . . . . . 72

3.2 Position du problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.2.1 Prsentation gnrale du projet Gazoduc GK3 . . . . . . . . . . . . . . . . . 72

3.2.2 Etude pralable du projet GK3 . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.2.2.1 Dcoupage du projet . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.3 Application de la mthode du chemin critique (PDM) notre problme . . . . . . . 76

3.3.1 Lister les tches, conditions d'antriorits et stimation des dures . . . . . . 76

3.3.2 Elaborer l'chancier du projet . . . . . . . . . . . . . . . . . . . . . . . . . 77

3.3.2.1 Classement des tches par niveaux . . . . . . . . . . . . . . . . . . 77

3.3.2.2 Tracer le graphe AoN . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.3.2.3 Calcul des dates au plus tt et plus tard . . . . . . . . . . . . . . . 78

3.3.2.4 Calcul des marges totales . . . . . . . . . . . . . . . . . . . . . . . 81

3.3.2.5 Dtrmination du chemin critique . . . . . . . . . . . . . . . . . . . 81

3.3.3 Visualisation du cot total du projet . . . . . . . . . . . . . . . . . . . . . . 84

3.4 Application de la mthode de la chane critique (CCPM) notre problme . . . . . 85

3.4.1 Rduire la dure des tches 50% . . . . . . . . . . . . . . . . . . . . . . . 85

3.4.2 Elaborer l'chancier du projet . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.4.2.1 Classement des tches par niveau . . . . . . . . . . . . . . . . . . . 86

3.4.2.2 Tracer le graphe AoN . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.4.3 Planier les tches en partant de la n du projet . . . . . . . . . . . . . . . . 86

3.4.3.1 Calcul des dates au plus tard et au plus tt . . . . . . . . . . . . . 86

3.4.4 Identication des conits de ressources . . . . . . . . . . . . . . . . . . . . . 90

3.4.4.1 Recenser la totalit des ressources . . . . . . . . . . . . . . . . . . . 90

3.4.4.2 Identifer les conits entre les ressources . . . . . . . . . . . . . . . . 95

3.4.5 Grer les conits et Identier la chane critique . . . . . . . . . . . . . . . . 95

3.4.6 Protger avec les Buers Projet et les Buers Auxiliaires . . . . . . . . . . . 95

3.4.7 Positionner les comptes rebours . . . . . . . . . . . . . . . . . . . . . . . . 96

3.4.8 Piloter le projet avec les comptes rebours et les Buers . . . . . . . . . . . 96

4 Utilisation des logiciels: Visual Xpress, Microsoft Project et CCPM+ 97

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4.2 Logiciel Visual Xpress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4.2.1 Rle du logiciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4.2.2 Interface du logiciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4.2.3 Syntaxe de Visual Xpress . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.2.3.1 Un simple exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.2.3.2 Structure gnrale du langage Visual Xpress . . . . . . . . . . . . . 100

4.2.3.3 Les tapes d'excution d'un programme sous logiciel Visual Xpress 100

4.3 Logiciel Microsoft Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4.3.1 Rle du logiciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

4.3.2 Environnement gnrale du logiciel . . . . . . . . . . . . . . . . . . . . . . . 101

4.4 Logiciel CCPM+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

3

4.4.1 Introduction : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.4.2 Mode de fonctionnement : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.4.3 Les direntes fonctionnalits de CCPM+ : . . . . . . . . . . . . . . . . . . . 103

4.5 Utilisation de Visual Express pour la planication de notre projet . . . . . . . . . . 103

4.5.1 Ralisation d'un planning prvisionnel . . . . . . . . . . . . . . . . . . . . . 103

4.5.1.1 Modlisation du problme . . . . . . . . . . . . . . . . . . . . . . . 103

4.5.1.2 Programmation par langage Visual Xpress . . . . . . . . . . . . . . 104

4.5.1.3 Le programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4.5.1.4 Rsultat d'excution du programme . . . . . . . . . . . . . . . . . 105

4.6 Utilisation de MS-Project 2010 pour la planication de notre projet selon la mthode

PDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.6.1 Les principales tapes suivre . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.6.2 Optimisation de la planication prvisionnelle . . . . . . . . . . . . . . . . . 109

4.6.2.1 Tableau des ressources. . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.6.2.2 Aectation des ressources. . . . . . . . . . . . . . . . . . . . . . . . 110

4.6.2.3 Audit et rsolution de conit de ressources . . . . . . . . . . . . . . 110

4.6.2.4 Rsultat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.7 Utilisation de CCPM+ pour la planication de notre projet selon la mthode CCPM112

4.7.1 Les principales tapes suivre . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.8 Comparaison des rsultats obtenus avec la mthode du chemin critique (PDM) et

la chane critique (CCPM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

4.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

A Distribution statistique de la dure d'une tche 122

A.1 Distribution uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

A.2 La distribution Bta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

A.3 Distribution Normale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

A.3.1 L'approche classique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Bibliographie 127

4

Table des gures

1.1 Le triangle du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2 L'tape prvisionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3 Exemple de WBS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.4 Deux reprsentations graphiques d'un mme graphe . . . . . . . . . . . . . . . . . . 20

1.5 Les artes e et f n'ont pas de point commun . . . . . . . . . . . . . . . . . . . . . . 21

1.6 Un graphe lmentaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.1 Reprsentation AoA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2 Regroupement des activits (simultanment excutes) par une activit . . . . . . . 31

2.3 Maintient des activits (simultanment excutes) introduisant des activits ctives 32

2.4 Reprsentation graphique de la mthode PERT . . . . . . . . . . . . . . . . . . . . 33

2.5 Reprsentation AoN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.6 Prsentation graphique de la mthode du potentiel . . . . . . . . . . . . . . . . . . 34

2.7 Reprsentation d'une tche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.8 Le lien Finish-to-Start(Fin-Dbut) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.9 Le lien Start-to-Finish(Dbut-Fin) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.10 Le lien Finish-to-Finish(Fin-Fin) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.11 Le lien Start-to-Start (Dbut-Dbut) . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.12 Lag appliqu un lien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.13 Lead appliqu un lien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.14 tape dbut d'un graphe PDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.15 tape n d'un graphe PDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.16 Distribution Bta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.17 Graphe des prcdences (PDM) associ . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.18 Exemple de chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

2.19 Diagramme de Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

2.20 Rsum des mthodes de planication . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.21 Temps de ralisation d'une tche . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.22 Estimation de la dure d'une tche . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.23 Syndrome de l'tudiant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.24 Une tche la fois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

2.25 Plusieurs tches la fois (multitache) . . . . . . . . . . . . . . . . . . . . . . . . . . 52

2.26 Interdpendance des tches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.27 Les marges temporelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

2.28 Les marges temporelles d'alimentation de la chane critique . . . . . . . . . . . . . . 55

2.29 Environnement multi-projets avec le Chemin Critique . . . . . . . . . . . . . . . . . 57

2.30 Environnement multi-projets avec la Chane Critique . . . . . . . . . . . . . . . . . 58

2.31 Chemin critique avec la mthode CPM . . . . . . . . . . . . . . . . . . . . . . . . . 58

5

2.32 Division des tches par 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.33 Identication des conits de ressources . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.34 Gestion des conits de ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

2.35 Identication de la chane critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

2.36 Buer projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

2.37 Buer auxiliaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

2.38 Les comptes rebours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

2.39 Suivi des cot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2.40 Les carts de cot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.1 L'organigramme de SAIPEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3.2 Gazoduc GK3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

3.3 Station El Kala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.4 Graphe PDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.5 Chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3.6 Cots prvisionnels du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

3.7 Graphe PDM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

3.8 Le diagramme de Gantt aprs avoir appliquer les ressources . . . . . . . . . . . . . . 95

4.1 Fentre principale de logiciel Visual Xpress . . . . . . . . . . . . . . . . . . . . . . . 98

4.2 La fentre principale du MS Project 2010 . . . . . . . . . . . . . . . . . . . . . . . . 101

4.3 CCPM+ intgre dans MsProject . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.4 Rsultat d'excution du programme . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.5 Calendrier de droulement des tches de projet . . . . . . . . . . . . . . . . . . . . 106

4.6 Fentre informations sur le projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

4.7 Calendrier de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

4.8 L'interface des tches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4.9 Diagramme Gantt et chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4.10 Tableau des ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.11 Tableau d'aectation des ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

4.12 Tableau d'aectation des ressources dans la zone de travail . . . . . . . . . . . . . . 110

4.13 Graphe de sur-utilisation de la ressource "Ouvrier" . . . . . . . . . . . . . . . . . . 111

4.14 Fentre audit des ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

4.15 Diagramme de Gantt aprs rsolution de conit de ressources . . . . . . . . . . . . . 112

4.16 Fentre informations sur le projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4.17 Fentre informations sur les tches . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4.18 Saisie des donnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

4.19 Nivellement des ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

4.20 Chevauchement des ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

4.21 Chane critique avant l'application des buers . . . . . . . . . . . . . . . . . . . . . 115

4.22 Chevauchement et surutilisation des ressources . . . . . . . . . . . . . . . . . . . . . 116

4.23 Chane critique aprs renivelement . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

4.24 Chane critique nale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

4.25 Inserer les tampons ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

4.26 Graphe pour piloter le projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

A.1 Distribution uniforme de probabilit . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

A.2 Distribution bta de probabilit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

6

A.3 Distribution normale de probabilit . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

A.4 Intervalle 95 % sur la dure du projet . . . . . . . . . . . . . . . . . . . . . . . . . 126

7

Liste des tableaux

2.1 Tableau d'ordonnancement des tches . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2 La liste des tches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.3 Les relations d'anticidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.4 Estimation des ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.5 Estimation des dures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.6 Tableau des rangs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.1 Tableau des listes des tches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

3.2 Tableau des niveaux des tches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3.3 Tableau des listes des tches avec les dures estimes 50% des dures initiales. . . 85

3.4 Tableau des ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

4.1 Tableau des rsultats naux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

A.1 mthode classique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

8

Introduction gnrale

9

Un projet est un ensemble d'activits se succdant et ayant pour but la ralisation d'un objec-

tif unique, bien dtermin. Avant sa concrtisation, un projet passe par plusieurs phases appeles

"Cycle de vie" du projet : Conception, Planication et Contrle.

Le concept de gestion de projets englobe des techniques et mthodes organisationnelles, des

outils de planication et de suivi de projet(contrle). Le principal objectif est d'optimiser des pa-

ramtres propres au projet c'est--dire : Dures, cots et qualits. La planication, reprsente une

tape trs importante lors de l'laboration d'un projet, c'est durant cette tape que sont estimes

les dures des activits ainsi que le nombre de ressources ncessaires pour leur droulement.

L'ordonnancement intervient dans le squencement des activits du projet, il xe l'ordre dans

lequel elles doivent tre ralises et calcule les besoins en ressources chaque tape de l'ordonnan-

cement. C'est dans cette tape galement qu'intervient le calcul des dates au plus tt et au plus

tard des tches.

La phase de contrle a aussi son importance dans le suivi du projet, elle permet de situer, de

savoir o en est la ralisation par rapport ce qui a t pralablement plani et faire le point

sur l'tat d'avancement du projet.

Dans ce mmoire il sera surtout question du problme de l'ordonnancement, tant l'une des

causes majeures de l'chec de certains projets. L'optimisation de la dure d'un projet soumise des

contraintes de prcdence entre les tches et des limitations sur la disponibilit des ressources,

constituent de toute vidence un objectif essentiel de la gestion de projets.

En pratique, on est souvent confront ces direntes contraintes qui sont un rel d

relever. Face ces problmes d'ordonnancement dicilement matrisables, les managers ont souvent

recours des modles plus faciles rsoudre o ces contraintes sont partiellement relaxes et dont

l'ordonnancement peut constituer des bornes pour l'ordonnancement rel. On distingue dans ce

sens deux types de modles relaxs.

Le modle temporelle dans lequel on ignore les contraintes de ressources( on suppose une

disponibilit illimite en ressources)

Le modle bas sur les ressources dans lequel les contraintes de prcdence entre les activits

sont ignores.

Initialement, le diagramme barres( Gantt) tait la reprsentation la plus utilise en planication et

ordonnancement. Ce diagramme tait rput pour sa simplicit et surtout pour son accessibilit. Il

s'avre actuellement peu ecace a lui seul et peu adapt pour la gestion de projets assez complexes.

L'apparition de la thorie des graphes et ses mthodes dans les annes 50 a permis d'amliorer les

techniques d'ordonnancement. Ceci a donn naissance des mthodes pour la reprsentation des

projets. On distinguera deux modles dirents de reprsentation :

La reprsentation AoA (Activity on Arc) : dans ce modle, les activits sont reprsentes par

les arcs du graphe tandis que les nuds dterminent ses vnements (n ou dbut d'activits

par exemple)

Reprsentation AoN(Activity on Nodes) : dans ce modle les activits sont reprsentes par

les sommets, les arcs dans ce cas dterminent les relations de prcdence entre les activits

du projet.

Chacun des modles cits donne lieu une mthode d'analyse ou d'ordonnancement temporelle,

on parlera de la mthode PERT dans le cas d'une reprsentation AoA et de la mthode PDM dans

10

le cas d'une reprsentation AoN. Cette analyse temporelle concerne notamment le calcul des dates

de dbut et de n de chaque activit et de direntes marges associes chaque activit. Cette

analyse nous permet de trouver "un chemin critique" qui est compos des activits "critiques"

c'est--dire les activits dont l'excution ne peut tre dire sans que la dure du projet ne soit

allonge. L'ordonnancement des activits non critiques ( en fait celle dont les marges totales ne

sont pas nulles), sera fait compte tenu des marges calcules, cette situation se rencontre surtout

lorsqu'on prend en compte des contraintes de ressources (en quantit renouvelable mais limite).

Les mthodes de la programmation linaires peuvent constituer un modle pour le problme

de l'ordonnancement. Dans le cas de l'ordonnancement temporel (c'est--dire avec relaxation des

contraintes de ressources) , la nature mme du problme permet d'accorder la prfrence aux

mthodes spciques dcrites plus haut : la mthode PERT et celle dite PDM.

Dans le cas d'un ordonnancement impliquant la prise en compte des contraintes de ressource ,

les mthodes de la programmation linaire s'avrent peu ecaces.

Direntes mthodes qui prennent en considration les contraintes de ressources sont dvelop-

pes.

Des approches (ou heuristiques) permettant d'obtenir des ordonnancements approchs mais leurs

inconvnients est la plus grande complexit pour leurs implimentations sur calculateurs.

La mthode de la chane critique qui prend en considration les contraintes de prcdence et de

ressources, et les comportements humain qui conduisent des fois l'chec du projet et qui est d'une

application facile.

Cette mthode de la chane critique peu connue mais qui s'avre trs ecace vu les rsultats ob-

tenus par les entreprises qu'ils l'on djas appliques, tend devenir la mthode privilgie.

Notre travail est ainsi organis :

1. Dans le chapitre 1, nous abordons quelques notions et dnitions relatives a la gestion de

projet et quelques terminologies de transport de gaz par canalisation et quelques dnitions

sur la thorie des graphes et la programmation linaire.

2. Le chapitre 2 porte sur direntes approches de modlisation du problme d'ordonnancement.

On utilisera la programmation linaire et la reprsentation rseau de la thorie des graphes.

Pour la gestion et l'ordonnancement de projet , il existe deux types de reprsentation, celle

dite AoA( activits sur les arcs ) et celle dite AoN (activits sur les nuds) dont nous

intressons deux mthodes tels que PDM et CCPM.

3. Aprs la modlisation, le chapitre 3 porte sur l'application des mthodes prcdentes sur

notre projet.

4. Chapitre 4 est ddi l'application de Ms Project CCPM+ et Visual Xpress a notre projet.

11

CHAPITRE 1. GNRALITS ET DFINITIONS

Chapitre 1

Gnralits et dnitions

12


1.1 Transport par canalisation

[wik] Le transport par canalisation est un mode de transport de matires gazeuses ou liquides.

En eet, les produits gnralement viss par ce terme sont :

Le ptrole et autres hydrocarbures liquides.

Le gaz naturel et autres gaz combustibles.

Les produits chimiques.

Selon le produit transport, les canalisations ont des noms ainsi des rglementations, des tech-

niques de construction et d'exploitation direntes. Les principaux systmes de transport par

canalisation concernent :

Le gaz naturel, transport par le gazoduc.

Les hydrocarbures, transport par les oloduc.

Les reseaux de transports par canalisation sont composs de tronons de conduites et d'ouvrages

connexes remplissant des fonctions prcises :

Les stations d'injection ou de dpart constituent les points d'entre du reseau de transport.

Les stations de compression( pour les gazes ) ou stations de pompage( pour les liquides ).

Les postes de livraison permettre de mettre la matire transporte disposition des destina-

taires intermdiaires ou naux.

Les stations d'arrive marquent l'extrmit d'un reseau de transport.

les postes de dtente ou de poste de rgulation permettent de diminuer la pression de uide

l'aval.

Les postes de sectionnement permettre d'isoler un tronon de canalisation an d'assurer sa

maintenance ou de limiter les consquence nfastes en cas de fuite.

1.1.1 Gaz naturel

On appelle gaz naturel un mlange d'hydrocarbures saturs gazeux (mthane, ethane, propane,

butane), contenant aussi des hydrocarbures liquides (pentane, hexane, et homologues suprieures)

et d'autre composants tels que l'oxyde de carbone, le dioxyde de carbone de carbone, l'azote,

l'hydrogne sulfur. Il peut contenir aussi de l'hydrogne et de l'oxygne mais en faible quantit,

il est produit partir de couche souterraines poreuses o il ml ptrole. En rgle gnrale, le

mthane est le principal constituant, il reprsente environ 70% 95% du volume total du mlange,

et c'est pourquoi on emploie souvent le mot "mthane" pour dsigner le gaz naturel lui-mme.

1.1.2 Gazoduc

Un gazoduc est une canalisation destine au transport de matires gazeuses sous pression, la

plupart du temps des hydrocarbures, sur de longues distances. La majorit des gazoducs acheminent

du gaz naturel entre les zones d'extraction et les zones de consommation ou d'exportation. On

estime la longueur totale des gazoducs dans le monde un million de kilomtres, soit plus de

25 fois la circonfrence terrestre. Les gazoducs sont en majorit terrestres, soit enfouis environ

un mtre de profondeur dans les zones habites , soit poss mme le sol en zone dsertique,

ou en zone sol dur (permafrost). Leur diamtre varie entre 50 millimtres (2 pouces) et 1400

13


millimtres (56 pouces) pour les plus importants. Toutefois, le tarissement des sources de proximit

et l'loignement croissant des zones d'exploitation ont conduit l'tablissement de gazoducs sous-

marins. Selon leur nature d'usage, les gazoducs peuvent tre classs en trois familles principales :

gazoducs de collecte : ramenant le gaz sorti des gisements ou des stockages souterrains

vers des sites de traitement.

gazoduc de transport ou de transit : acheminant sous haute pression le gaz

trait (dshydrat,ssulfur,. . . ) aux portes des zones urbaines ou des sites industriels de

consommation.

gazoducs de distribution : rpartissant le gaz basse pression au plus prs des consom-

mateurs domestiques ou des petites industries.

1.1.3 Oloduc

Les oloducs sont des gros tuyaux qui peuvent transporter de grandes quantits de ptrole,

jusqu' plusieurs dizaines de millions de tonnes par an. Le ptrole y circule grce sa mise en

pression par des stations de pompage situes tous les 60 100 km. Sa vitesse dans les tuyaux est

d'environ 2 mtres par seconde (7 km/h). Un oloduc est un ensemble constitu :

D'une canalisation (pipeline).

D'une station de pompage de dpart.

D'une ou plusieurs stations de pompage intermdiaires.

D'un terminal de dpart et d'arrive (bacs de stockage).

1.1.4 Les terminaux

Dans l'industrie ptrolire, le terme terminal dsigne l'une ou l'autre extrmit d'un itinraire

de transport d'hydrocarbures utilis pour la rception ou l'expdition de ceux-ci terre ou en mer,

il peut dsigner les parcs de stockage d'un produit, comme il peut dsigner des raneries ou des

ports situs aux extrmits nales des pipelines. Les relais de pression sont assurs, en certains

points de la ligne, par les stations de pompage. D'une manire gnrale, les terminaux dsignent

les extrmits d'une canalisation.

1.2 Projet

[Nic75] Le mot projet provient du terme latin "projicere" qui signie "jeter quelque chose vers

l'avant", ainsi le mot projet signiait dans l'antiquit :"quelque chose qui vient avant que le reste

ne soit fait". Quand le mot projet a t initialement adopt, il se rapportait au plant de quelque

chose et non l'excution proprement dite de ce dernier. L'utilisation du mot projet changera dans

les annes 50 quand plusieurs techniques de gestion sont apparues. Le concept a dvi de son sens

initial pour couvrir la fois le projet et les objets qui le composent. Actuellement un projet est un

ensemble d'actions raliser pour atteindre un objectif dni dans le cadre d'une mission prcise

et pour la ralisation desquelles on a identi non seulement un dbut mais aussi une n.

14


1.2.1 Tche

Un projet est constitu d'un ensemble de tches, une tche est une activit ayant un dbut et

une n, elle est caractrise par les lments suivant :

Identit (nom de la tche)

Dure estime.

Relie au moins une autre tche du projet.

Consomme des ressources (matrielles, humains, nancires).

1.2.2 Jalon

Un jalon (milestone) est un vnement particulier qui marque le dbut ou la n d'une partie

bien identie du projet. Il est en gnral associ une date prcise. C'est un repre prdtermin

et signicatif dans le cours du projet.

1.2.3 Ressources

La ralisation de chaque tche identie dans le projet entrane la consommation des ressources.

Ces ressources peuvent tre de direntes natures (matrielles, humaines, nancire).

1.2.4 Le triangle du projet

[Tou90] Les principes de base de la gestion de projet sont reprsents par le triangle du projet, un

symbole rendu populaire par Harold Kerzner. Ll est caractris par 3 objectifs lis et antagonistes:

Le dlai : il s'agit du temps ncessaire pour achever le projet tel qu'il est dcrit dans les

prvisions.

Le cot : le cot du projet est bas sur les cots des ressources, c'est--dire le personnel,

l'quipement et les matriels ncessaires la ralisation des tches.

La qualit : il s'agit des objectifs et des tches du projet ainsi que du travail ncessaire pour

atteindre ces objectifs.

Fig. 1.1 Le triangle du projet

15


C'est trois points sont interdpendants et doivent tre pris en compte soigneusement.Un projet

peut se prsenter comme un point dans ce repre( point rouge), on peut amliorer une composante

mais avec une dtrioration des deux autres, il faut donc comprendre qu'il existe 3 possibilits:

Rapide et pas cher Mauvaise qualit : C'est ce que demandent beaucoup de clients, sans serendre compte qu'un projet vite fait et moindre cot aura forcment des lacunes. Cela peut

tre satisfaisant pour un prototype qui doit valider un concept. Mais il faut bien expliquer

les risques que cela peut faire prendre moyen terme.

Rapide et de bonne qualit Cher : Si le client peut se le permettre, c'est la solution parfaite.Un projet trs important sera trait de manire prioritaire sur les autres, se verra aecter

plus de moyens humains et techniques. Et donc forcment, cela a un cot important.

Bonne qualit et pas cher Lent : Un projet bien fait, mais qui ne cote pas cher? Il vaprendre du temps tre ralis. Pour diminuer les cots, ce projet va se retrouver jouer le

" bouche-trou " ; sa priorit est plus faible, et "on y travaille quand on a du temps". Pareil

pour les ressources techniques, qui sont disponibles d'abord pour les autres projets.

1.2.5 La gestion de projet

[Val] La gestion de projet est le processus qui consiste planier, organiser et grer les tches et

les ressources an d'atteindre un objectif dni, gnralement en respectant des limites de temps,

de ressources ou de cots.

1.2.6 Les tapes de la gestion des projets

la gestion de projet est dcoupe en deux phases:

une phase prvisionnelle durant laquelle on ordonnace et on hirarchise les tches qui concur-

rent la ralisation du projet, on prvoit et on value toutes les informations les concernant(

dlais, ressources, cots).

une phase dite le suivi des activits, pendant laquelle on observe les dcalages ventuels qui

peuvent survenir entre ce qui a t prvu et ce qui est eectivement ralis.

Fig. 1.2 L'tape prvisionnelle

16


1.2.7 La planication de projet ( tape prvisionnelle)

1.2.7.1 Consistance :

La planication d'un projet consiste :

1. Dcouper le projet en phases.

2. Dcouper les phases en tches.

3. Dnir la logique d'enchanement des tches.

4. Analyser les rsultats( dlai nal, chemin critique, les marges,...)

5. Optimiser le planning, en changeant certain enchanement logique ou/et en modiant la dur

de certaines tches.

6. Editer le planning sous une forme temporelle claire et bien adapte aux divers utilisateurs.

1.2.7.2 Objectifs :

Les objectifs principaux de la planication des projets sont les suivants:

minimiser la dure d'excution totale du projet,

minimiser le cot total du projet,

gestion optimale des ressources.

1.2.8 WBS ( Work Breakdown Structure )(structure de rpartition de

travaille)

[CFEW07] Le WBS rpond au quoi-faire? C'est une dcomposition arborescente oriente d'un

projet, ce qui montre une subdivision de l'eort requis pour atteindre un objectif. Dans un projet le

WBS est dvelopp en commenant par l'objectif nal et successivement le subdiviser en lments

grables en termes de taille, la dure et la responsabilit qui comprennent toutes les mesures

ncessaires pour atteindre l'objectif.

Fig. 1.3 Exemple de WBS

17


1.2.9 OBS (Organisation Breakdown Structure )

L'OBS rpond au qui est responsable de quoi? et qui fait quoi?. Il fait le lien entre les tches et

les personnes( physiques ou morales ). Il permet de dnir les responsabilits et les actions dans les

tches. Dans la pratique, cependant, on ne produit pas une arborescence calque sur le WBS mais

une matrice avec les tches d'un cot et les personnes de l'autre. Le remplissage de cette matrice

fait alors oce d'OBS.

1.2.10 Matrice RACI

RACI reprsente une matrice des responsabilits qui indique les rles et les responsabilits des

intervenants au sein de chaque processus et activit. Cette matrice reprsente l'organisation du

travail en reliant dans un tableau commun le WBS et L'OBS. La matrice RACI donne une vision

simple et claire de qui fait quoi dans le projet en permettant d'viter une redondance de rles

ou une dilution des responsabilits. Elle est remplie non seulement de faon binaire mais avec les

quatre lettres du RACI qui signient :

R : Pour le ou les responsables oprationnels ( Responsible ), c'est--dire ceux qui eectuent la

tche.

A : Pour le responsable nal (Accountable), c'est--dire celui qui rend des comptes.

C : Pour le ou les personnes consultes (Consulted).

I : Pour le ou les personnes informes( Informed ).

1.2.11 Cahier des charges

1.2.11.1 Dnition

Un cahier des charges est un document contractuel dcrivant ce qui est attendu du matre

d'oeuvre par le matre d'ouvrage. Il s'agit donc d'un document dcrivant, de la faon la plus

prcise possible, avec un vocabulaire simple, les besoins auxquels le matre d'oeuvre doit rpondre.

Dans la mesure o seul le matre d'oeuvre est rellement comptent pour proposer une solution

technique approprie, le cahier des charges doit prfrentiellement faire apparatre le besoin de

manire fonctionnelle, indpendamment de toute solution demande doit s'insrer. Il s'agit ainsi

d'un document permettant d'une part de garantir au matre d'ouvrage que les livrables seront

conformes ce qui est crit, d'autre part d'viter que le matre d'ouvrage modie son souhait

au fur et mesure du projet et demande au matre d'oeuvre des nouvelles fonctionnalits non

prvues initialement. Un cahier des charges doit galement contenir tous les lments permettant

au matre d'oeuvre de juger de la taille du projet et sa complexit an d'tre en mesure de proposer

une ore la plus adapte possible en termes de cot, de dlai, de ressources humaines et d'assurance

qualit. Il s'agit ce titre d'un document de rfrence, permettant de lever toute ambigut sur

ce qui tait attendu, ainsi qu'un outil de dialogue permettant au matre d'oeuvre d'interroger le

matre d'ouvrage an d'aner sa comprhension de la demande. Un cahier des charges n'est pas

pour autant ncessairement statique. Son contenu peut tout fait tre modi au cours du projet,

mme si dans l'idal tout devrait tre dni ds le dbut, sur la base d'un avenant accept par les

deux parties.

18


1.2.11.2 Contexte

Un cahier des charges commence gnralement par une section dcrivant le contexte, c'est--dire

le positionnement politique et stratgique du projet.

1.2.11.3 Objectifs

Le cahier des charges doit permettre de comprendre le but recherch, an de permettre au

matre d'oeuvre d'en saisir.

1.3 Thorie des graphes

[Eri] La reprsentation d'un problme par un dessin, un plan, une esquisse contribue souvent

sa comprhension. Le langage des graphes est construit, l'origine, sur ce principe. Nombres de

mthodes, de proprits, de proccdures ont t penses ou trouves partir d'un schma pour

tre ensuite formalises et dveloppes. Chacun d'entre nous a, au moins une fois, vu ou utilis

un plan de mtro, une carte de lignes ferroviaires, un plan lectrique, un arbre gnalogique ou

un organigramme d'entreprise ; ainsi, tout le monde sait plus ou moins intuitivement ce qu'est un

graphe.

La thorie des graphes permet de transcrire concrtement des faits on les modlisant l'aide

d'objets mathmatiques, an de rsoudre des problmes tels:

Les problmes d'ordonnancement, qui ont pour but la recherche d'un ordre optimal des tches

pour une ralisation complexe: il s'agit de trouver un ordre de ralisation des travaux, en

minimisant le temps total et le cot total.

Les problmes d'aectations (organiser des quipes de travail pour qu'elles soient le plus

ecaces possibles).

Les problmes de maintenance (minimiser les stocks de pices de rechange, ou les cots dus

l'arrt des machines).

Les problmes de comptition et de concurence.

Les problmes de classication de produits, ou d'individus.

On peut faire remonter les origines de la thorie des graphes Euler (1736) avec la rsolution

du fameux problme des "Ponts de Koenigsberg"; et Hamilton avec le clbre jeu du "Parcours

autour du monde" (1859) posant la premire fois un problme qui, dans sa version plus rcente dite

du "voyageur de commerce" tient toujous les chercheurs en haleine. Mais la thorie des graphes

a rellement pris son dpart pendant la seconde guerre mondiale, plus prcisment en Angleterre

en 1940, sous le nom d'Operation Research. L'tat Major alli, qui devait accrotre l'ecacit de

ses oprations, en cona le travail au physicien Blackett. Il s'agissait de rechercher la meilleure

rotation des quipages dans les avions, l'implantation optimale des radars, plus tard l'organisation

des convois transatlantique . . .

Avec l'apparition des ordinateurs et le dveloppement des algorithmes, les graphes ont cess

de se limiter aux rcrations mathmatiques pour pntrer progressivement tous les domaines de

la science. Aujourd'hui la thorie et les algorithmes de graphes se sont imposs comme une dis-

cipline incontournable aussi bien dans les sciences de base (physique, Chimie, Biologie, Sciences

19


Humaines, Informatique) que dans les Sciences de l'Ingnieur (Automatique, Optimisation des sys-

tmes, conomie et Recherche Oprationnelle, Analyse de Donnes, Ingnierie des grands rseaux

de communication de type Internet,etc.).

Cette volution tient la fois la puissance de modlisation procure par les graphes, et la

disponibilit d'une vaste panolpie d'algorithmes ecaces qui ne cesse de s'enrichir au l du temps.

1.3.1 Dnitions et concepts de base

1.3.1.1 Qu'est-ce qu'un graphe?

Dnition 1 (Graphe)

On appelle graphe G = (X,A) la donne d'un ensemble X dont les lments sont appelssommets et d'une partie de A symtrique ((x,y) A (y,x) A) dont les lments sontappels artes.

En prsence d'une arte a = (x,y) qui peut tre note simplement xy, on dit que x et y sontles extrmits de a, que a est incidente en x et en y, et que y est un successeur ou voisin dex (et vice versa).On dit qu'un graphe est sans boucle si A ne contient pas d'arte de la forme (x,x), c'est--direjoignant un sommet lui-mme.

Le nombre de sommets est appel ordre du graphe.

Un graphe ne possdant pas de boucle ni d'artes parallles (deux artes distinctes joignant la

mme paire de sommets) est appel graphe simple ou 1-graphe. En revanche un p-graphe ou graphe

gnralis est un graphe pour lequel il n'existe jamais plus de p artes de la forme (x,x).

Graphiquement, les sommets peuvent tre reprsents par des points et l'arte a = (x,y) par untrait reliant x y. On notera que la disposition des points et la longueur ou la forme (rectiligneou incurve) des traits n'a aucune importance. Seule l'incidence des direntes artes et sommets

compte. A titre d'exemple, les deux graphes de la gure 1.3 sont identiques.

Fig. 1.4 Deux reprsentations graphiques d'un mme graphe

20


Dans le trac graphique d'un graphe, deux artes peuvent sembler avoir une intersection en un

point qui n'est pas un sommet. C'est le cas, par exemple, des artes e et f du graphe de la gure

1.4. De telles artes peuvent tre vues comme tant places dans des plans dirents et n'ayant

donc aucun point commun.

Fig. 1.5 Les artes e et f n'ont pas de point commun

Les graphes ainsi dnis sont dits "graphes non orients". Dans certaines situations cependant,

l'orientation des artes est importante.

Dnition 2 (Graphe Orient)

On appelle graphe orient ou digraphe G = (X,A) la donne d'un ensemble X dont leslments sont appels sommets et d'une partie A de X x X dont les lments sont appelsarcs.

En prsence d'un arc a = (x,y) qui peut tre note simplement xy, on dit que x est l'origine(ou extrmit initiale) et y l'extrmit (terminale) de a, que a est sortant en x et incident eny, et que y est un successeur de x tandis que x est un prdcesseur de y. On dit aussi que xet y sont adjacents.

Dnition 3 (Degr d'un sommet)

On appelle degr sortant ou demi-degr extrieur d'un sommet x le nombre d'arcs de la formea = (x,y) avec y 6= x, c'est--dire le nombre d'lments de (x) {x}.On note ds(x) ce degr.On appelle degr entrant ou demi-degr intrieur d'un sommet x le nombre d'arcs de la formea = (y,x) avec y 6= x, c'est--dire le nombre d'lments de 1(x) {x}.On note de(x) ce degr.On appelle degr de x (ou valence) la somme du degr entrant et du degr sortant.

Un sommet de degr entrant non nul et de degr sortant nul est appel puits, tandis qu'un

sommet de degr entrant nul et de degr sortant non nul est appel source.

Le concept de graphe symtrique est trs proche de celui des graphes non orients. En fait,

tout graphe symtrique, on peut associer un graphe non orient en substituant aux arcs a1 = (x,y)et a2 = (y,x), une arte a = (y,x).

21


Dnition 4 (Graphe complet)

Un graphe G = (X,A) est dit complet si, pour toute paire de sommets (x,y), il existe aumoins un arc de la forme (x,y) ou (y,x).Un graphe simple complet d'ordre n est not Kn. Un sous-ensemble de sommets C X telque deux sommets quelconques de C sont relis par une arte est appel une clique.

1.4 Modes de reprsentation d'un graphe

Comme nous l'avons mentionn prcdemment, l'essor de la thorie des graphes est essentielle-

ment d l'avnement de puissants calculateurs. Il est donc lgitime de s'intresser la manire de

reprsenter les graphes sur ordinateur. Plusieurs modes de reprsentation peuvent tre envisags

selon la nature des traitements que l'on souhaite appliquer au graphe considr.

1.4.1 Listes de succession

Un graphe peut tre reprsent l'aide d'un dictionnaire; il s'agit d'une table simple entre

o chaque ligne correspond un sommet et comporte la liste des successeurs ou des prdcesseurs

de ce sommet. Considrons le graphe de la gure 1.6.

Fig. 1.6 Un graphe lmentaire

Celui-ci peut tre reprsent par les deux tables suivantes :

X +(x) X (x)1 2,3,4,5 1 5

2 3 2 1

3 4 3 1,2

4 - 4 1,3,5

5 1,4 5 1

22


1.4.2 Matrice d'adjacence

Les outils classiques d'algbre linaire peuvent galement tre utiliss pour coder les graphes.

La premire ide consiste considrer chaque arc comme un lien entre deux sommets.

Dnition 7 (Matrice d'adjacence)

Considrons un graphe G = (X,A) comportant n sommets. La matrice d'adjacence de G estgale la matrice U = (uij) de dimension n x n telle que

uij =

{1 si(i,j) A(c'est--dire (i,j) est une arte)0 sinon

Une telle matrice, ne contenant que des 0 et des 1 est appele, de manire gnrale, unematrice boolenne.

Un graphe orient quelconque a une matrice d'adjacence quelconque, alors qu'un graphe non

orient possde une matrice d'adjacence symtrique. L'absence de boucle se traduit par une dia-

gonale nulle. La matrice d'adjacence du graphe de la gure 1.6 est la suivante :

U =

0 1 1 1 10 0 1 0 00 0 0 1 00 0 0 0 01 0 0 1 0

Ce mode de reprsentation engendre des matrices trs creuses (i.e.comprenant beaucoup de

zros). Cependant la recherche de chemins ou de chanes s'exctue aisment avec une telle repr-

sentation. De plus, la matrice d'adjacence possde quelques proprits qui peuvent tre exploites.

Considrons un graphe G et sa matrice d'adjacence associe U :

Lla somme des lments de la ime ligne de U est gale au degr sortant ds(xi) du sommetxi de G.

La somme des lments de la jme colonne de U est gale au degr entrant de(xj) du sommetxj de G.

U est symtrique si, et seulement si, le graphe G est symtrique

1.4.3 Matrice d'incidence

La seconde ide permettant une reprsentation matricielle d'un graphe exploite la relation d'in-

cidence entre artes et sommets.

Dnition 8 (Matrice d'incidence)

Considrons un graphe orient sans boucle G = (X,A) comportant n sommets x1, . . . ,xn etm artes a1, . . . ,am. On appelle matrice d'incidence (aux arcs) de G la matrice M = (mij)de dimension n x m telle que :

mij =

1 si xi est l'extrmit initiale de aj1 si xi est l'extrmit terminale de aj0 si xi n'est pas une extrmit de aj

23


Pour un graphe non orient sans boucle, la matrice d'incidence (aux artes) est dnie par :

mij =

{1 si xi est une extrmit de aj0 sinon

La matrice d'incidence du graphe de la gure 1.6 s'crit sous la forme suivante :

M =

1 0 1 0 1 1 1 01 1 0 0 0 0 0 00 1 1 1 0 0 0 00 0 0 1 1 0 0 10 0 0 0 0 1 1 1

1.5 Etude de la connexit

1.5.1 Chanes et cycles, lmentaires et simples

Dnition 6 (chane)

Une chane est une squence nie et alterne de sommets et d'artes, dbutant et nissant

par des sommets, telle que chaque arte est incidente avec les sommets qui l'encadre dans la

squence. Une arte ne doit pas intervenir plusieurs fois dans la squence contrairement un

sommet.

Le premier et le dernier sommet sont appels (sommets) extrmits de la chane. La longueur

de la chane est gale au nombre d'artes qui la composent.

Si aucun des sommets composant la squence n'apparat plus d'une fois, la chane est dite

chane lmentaire.

Si aucune des artes composant la squence n'apparat plus d'une fois, la chane est dite

chane simple.

Un cycle est une chane dont les extrmits concident.

Un cycle lmentaire (tel que l'on ne rencontre pas deux fois le mme sommet en le par-

courant) est un cycle minimal pour l'inclusion, c'est--dire ne contenant stricte- ment aucun

autre cycle.

1.5.2 Chemins et circuits, lmentaires et simples

Toutes les dnitions prcdentes, s'appliquant au cas des graphes non orients, peuvent tre

transposes au cas des graphes orients.

Dnition 7 (chemin)

Un chemin est une squence nie et alterne de sommets et d'arcs, dbutant et nissant par

des sommets, telle que chaque arc est sortant d'un sommet et incident au sommet suivant

dans la squence (cela correspond la notion de chane "oriente").

Si aucun des sommets composant la squence n'apparat plus d'une fois, le chemin est dit

chemin lmentaire.

Si aucune des artes composant la squence n'apparat plus d'une fois, le chemin est dit

chemin simple.

Un circuit est un chemin dont les extrmits concident.

En parcourant un circuit lmentaire, on ne rencontre pas deux fois le mme sommet.

24


1.5.3 Graphes connexes

Dnition 8 (graphe connexe)

Un graphe G est connexe s'il existe au moins une chane entre une paire quelconque de

sommets de G.

1.5.4 Graphes fortement connexes

Dnition 9 (graphe fortement connexe)

Un graphe oriente est dit fortement connexe s'il existe un chemin joignant deux sommets

quelconques.

1.5.5 Rseaux

Dnition 10 (Rseau)

Un graphe fortement connexe, sans boucle et ayant plus d'un sommet, est appel un rseau.

On appelle noeud d'un rseau un sommet qui a plus de deux arcs incidents. Les autres

sommets sont appels antinoeuds.

On appelle branche tout chemin pour lequel seuls les premiers et derniers sommets sont des

noeuds.

1.6 Utilisation de la technique de la programmation linaire

1.7 Introduction

La programmation linaire est un outil trs puissant de la recherche oprationnelle. c'est un

outil gnrique qui peut rsoudre un grand nombre de problmes. En eet, une fois un problme

modlis sous la forme d'quation linaire, des mthodes assurent la rsolution du problme de

manire exacte.

1.8 Gnralits sur la programmation linaire

1.8.1 Dnition

[MB05] La programmation linaire (PL) a t introduite par le russe Kantorovitch et la premire

solution a t faite par l'amricain G.B.Dantzig en 1951. Gnralement, on appelle programme

mathmatique un problme d'optimisation d'une fonction objectif de plusieurs variable en prsence

de contraintes. Le programme est dit linaire si la fonction et les contraintes sont toutes des

conbinaisons linaires de variables.

Il a la forme gnrale suivante :

25


max ou minz =

nj=1 cixj

s.c :n

j=1 aijxj , = ou bi i = 1...mxj 0 j = 1...n Il comport n variables non ngatives.

m contraintes d'galit ou d'ingalit.

Une fonction objectif ( fonction de cot ou fonction conomique) optimiser.

Le coecient de cot ou de prot de la variable xj est not cj, celui de la variable xj dans lacontrainte i est not aij. La contrainte i a un second membre constant bi. Les contraintes simplesde positivits ne sont pas incluses dans les m contraintes, car sont gres part par les algorithmes.

1.8.2 Forme matricielle classique et quelque conversions

Notons X = (x1,x2,,,,xn)tle vecteur des variables, b = (b1,b2,,,bm)

tcelui des seconds membres

des contraintes, C = (c1,c2,,,cn)tles cots ou prot associs aux variables et A la matrice m ndes aij. On peut alors crire un programme linaire sous forme matricielle.Deux formes sont courantes :

La forme canonique avec des contraintes utilise pour la rsolution graphique.max c.x

A.x bx 0

La forme standard avec galits, pour la rsolution algbrique par des algorithmes (algorithme

de simplexe). Par convention, la forme standard est exprime avec des seconds membres

positifs. max c.x

A.x = bx 0Ces formes ne servent qu' simplier les prsentations thoriques. Dans la ralit, bien sur, un

PL peut comporter la fois des galits et des ingalits. On peut facilement convertir les formes

mixtes en classique. Ainsi, toute contrainte d'galit peut tre remplace par deux ingalits.

nj=1

aijxj = bi { n

j=1 aij xj binj=1 aij xj biOn peut convertir une ingalit en galit en ajoutant ou soustrayant une variable d'cart ei 0propre chaque contrainte i.n

j=1 aij xj bi, ei 0n

j=1 aijxj + ei = biSi l'objectif consiste minimiser une fonction linaire, Z = C.X, on peut passer d'une maxi-misation une minimisation, car maximiser Z revient minimiser Z.L'exigence de variables positives n'est pas restrictive, car une variable xj non contrainte ensigne peut toujours s'crire comme une dirence x

j xj de deux variables non ngatives.

26


1.8.3 Algorithme du simplexe

L'algorithme du simplexe est une mthode de rsolution des programmes linaires fonde sur

l'ide que l'on peut, partir d'une solution de base quelconque, progresser vers l'optimum par

une suite d'itrations. Il sera naturellement possible de comparer toutes les solutions de base,

on constate qu'elles sont en trs grand nombre; ainsi, dans un programme n variables et mcontraintes, il y en a:

Cmn =n!

m!(nm)!Par consquence, mme en retenant uniquement toutes les solutions possibles (variables positives

ou nulles), il en aurait beaucoup examiner. Le mathmaticien Dantzig nous a procur des critres

qui permettent de limiter le nombre d'itrations.

En utilisant ces critres, nous sommes certains d'amliorer la situation chaque itration et de

progresser vers l'optimum sans retour en arrire.

1.8.4 La notion de dualit

Tous les programmes linaires peuvent s'crire sous la forme gnrale suivante:

maxz = ctx

s.c : Ax bx 0O c et x sont des vecteurs de taille n,b un vecteur de taille m, et A une matrice de taille m x n.Si on dsigne cette reprsentation sous le terme de forme primale, on dsigne alors sous le terme

de forme duale le problme suivant:

minw = bty

s.c : Aty cy 0O A,b et c sont les mmes et y un vecteur de taille m.Les deux problmes sont trs fortement lis. Si l'un d'entre eux possde une solution optimale,

alors l'autre aussi. De plus, les deux solutions optimales ont alors la mme valeur (w = z). Sil'un d'entre eux est non-born, l'autre ne possde pas de solution.

La dualit est trs utilise en programmation linaire, notamment pour faciliter les calculs. Par

exemple, un PL avec dix variable et deux contraintes ne peut pas tre rsolu graphiquement, tandis

que cela ne pose pas de problme pour son dual deux variables et dix contraintes.

1.8.5 Les lments d'un modle d'optimisation

Variable de dcision

La premire tape dans le processus de modlisation est d'identier concrtement toutes les

variables de dcision (inconnues) de la situation modliser.

27


Fonction objectif

A chaque variable de dcision, correspond un coecient conomique indiquant la contribution

unitaire de la variable correspondante l'objectif poursuivi. Ensuite, on dduit la fonction

objectif que l'on veut optimiser ( maximiser ou minimiser).

Contraintes

Dans la problmatique de la dcision, il faut tre en mesure d'identier tout genre de res-

triction (main d'oeuvre, espace, budget,. . . ) qui peut limiter les valeurs que peuvent prendre

les variables de dcision. Existe-t-il galement des restrictions ou exigences minimales sur les

variables de dcision (contraintes du march, politique de l'entreprise,. . . ).

A chaque restriction, limitation ou exigences, correspond habituellement une contrainte qui

prendra la forme d'une quation.

L'ensemble des contraintes ainsi formules constitue le domaine des solutions possibles au

modle.

28

CHAPITRE 2. MODLISATION DU PROBLME D'ORDONNANCEMENT DU PROJET

Chapitre 2

Modlisation du problme

d'ordonnancement du projet

29


2.1 Introduction

On dit qu'on a aaire un problme d'ordonnancement lorsque, en vue de la ralisation d'un

objectif quelconque, il faut accomplir de multiples tches, elles-mmes soumises un ensemble de

contraintes.

Les contraintes auxquelles sont soumises les diverses tches qui concourent la ralisation de l'ob-

jectif sont de divers types. On distingue:

Les contraintes du type potentiel, qui sont les contraintes de localisation temporelle (la tche

i ne doit pas commencer avant telle date ou, au contraire, doit tre acheve telle date), les

contraintes de succession (la tche j ne peut commencer avant que la tche i ne soit termine,

ou simplement, parvenue un certain degr d'achvement);

Les contraintes de type disjonctif,imposant la disjonction de deux intervalles de temps, rela-

tifs, par exemple, l'excution de deux tches i et j, qui ne peuvent tre ralises simultan-

ment (car c'est le mme ouvrier qui les ralise par exemple); dans certains cas, les contraintes

disjonctives peuvent tre ramenes au type potentiel;

Les contraintes de type cumulatif,les moyens ncessaires l'excution d'un certain nombre

de tches sont chaque instant limits; par exemple, le nombre de camions utilisables ou la

somme dpense par les travaux raliss l'instant t ne doit pas dpasser un certain seuil,etc.

Quand le processus de ralisation d'un objectif est dcomposable en tche, ces tches tant soumises

des contraintes diverses, il importe de dterminer un ordre d'excution des tches, compatible avec

les contraintes. Trouver un tel ordre, c'est obtenir une solution du problme d'ordonnancement.

Toutefois, parmi les diverses solutions, il en est de meilleures et de moins bonnes relativement

un critre donn.

Ainsi, il existera probablement une solution moins coteuse, une autre plus rapide, une troisime

plus quilibre que les autres. Au sens mathmatique, rsoudre un problme d'ordonnancement,

c'est en dterminer une solution quelconque; au sens de la recherche oprationnelle, c'est choisir,

parmi toutes les solutions, la solution optimale,par rapport un critre x l'avance.

La phase d'ordonnancement constitue une tape cruciale dans la gestion d'un projet. Il s'agit dans

cette tape de planier de manire optimale et raliste le droulement de chacune des activits

constituant le projet, en respectant les direntes contraintes de prcdence entre les tches et les

limitations dans la disponibilit des ressources ncessaires l'excution des activits. La thorie

des graphes et des mthodes s'avrent un outil trs commode pour la formulation du problme

de l'ordonnancement dans le langage mathmatique, prcisment dans celui de la programmation

linaire. Dans ce chapitre, nous prsentons les lments et notions fondamentales qui permettent

une telle formulation. Il existe deux approches cet eet :

La mthode dite AoN( Activity-On- Node), dans laquelle les tches du projet sont reprsen-

tes par les nuds du graphe correspondant, les arcs dcrivent les rgles de prcdence entre

les direntes tches du projet.

La mthode AoA( activity-On- Arow).

2.2 Reprsentation AoA

Dans cette reprsentation chaque activit est reprsente par un arc et chaque vnement par

un nud. Le nud de dbut de l'arc correspond au dbut de l'activit, le nud d'arriv correspond

30


la n de l'activit ou de la tche. La relation de prcdence classique n-dbut avec marge nulle

entre deux activits a et b (note aussi a b) signie que l'activit b peut dbuter aussi tt quel'activit a est acheve. Graphiquement cela est traduit par la concidence du nud terminal del'arc reprsentant l'activit a avec le nud initial de l'arc reprsentant l'activit b.

Fig. 2.1 Reprsentation AoA

La reprsentation AoA se caractrise par les proprits suivantes :

1. Une activit ne peut dbuter qu'aprs l'achvement de toutes celles qui la prcdent. En

d'autres termes lorsque l'vnement correspondant son nud de dbut est compltement

ralis.

2. Les arcs dterminent le squencement logique des vnements.

3. Les nuds sont numrots sans rptition et dans un ordre de croissance induit par les rgles

de prcdence. La matrice d'adjacence du graphe associ est en consquence carre, super-

diagonale : l'vnement (i,j) de cette matrice vaut 1 s'il y a un arc allant de i j et 0 sinon-la

diagonale est nulle.

4. Dans les calculs, une activit est dnie par ses nuds de dbut et n. Deux nuds distincts

peuvent tre relis par au plus une activit.

5. Par construction le graphe n'a pas de cycle.

6. Par construction dans un AoA, il peut y avoir un nud de dbut (sans prdcesseur) et un

unique nud de n des activits(sans successeurs). Le nud de n des activits correspond

au nud terminal de toutes les activits sans successeurs.

Les rgles 1 et 6 sont aussi imposes par la logique interne de certains algorithmes. Pour prserver

ces rgles, il est parfois utile d'introduire des activits et vnements ctifs ( dures nulles). Ces

activits et vnements ctifs, sont notamment ncessaires dans les cas suivants :

Prserver l'unicit des activits : Lorsque plusieurs activits s'excutent simultanment, on

peut soit les regrouper et les reprsenter par une unique activit, soit les maintenir en intro-

duisant des activits ctives.

Fig. 2.2 Regroupement des activits (simultanment excutes) par une activit

31


Fig. 2.3 Maintient des activits (simultanment excutes) introduisant des activits ctives

Pour satisfaire la condition d'unicit des vnements " dbut et n " de projet lorsque ce

n'est pas le cas dans le graphe original, on peut introduire cet eet des activits ou autres

nuds ctifs.

2.2.1 Graphe de la mthode PERT

La mthode PERT(Program Evaluation Review Technique) est dveloppe au tats- unis

d'amerique en 1958 pour la planication de la construction des sous- marins Polaris. Son graphe

est sous forme de AoA. Le graphe de la mthode PERT est souvent dicile construire du fait

qu'on est souvent amen introduire des arcs ctifs qui ne correspondent aucune tche. Dans la

mthode PERT, chaque tche est donc associe un arc du graphe. La longueur de l'arc corres-

pondant la dure de la tche en question. Les sommets sont utiliss pour traduire les relations

de succession temporelle. Ainsi, si la tche j doit suivre la tche i , l'extrmit terminale de l'arc

correspondant la tche i concidera avec l'extrmit initiale de l'arc reprsentant la tche j. Nousavons le tableau suivant qui reprsente les tche avec leurs dures et la contrainte de prcdence.

Tache Dure Prcdence

1 5 -

2 4 1

3 2 2

4 2 3

5 3 4

6 5 3

7 3 2

8 3 7

9 4 6,8

10 10 5,9

11 12 10

Tab. 2.1 Tableau d'ordonnancement des tches

Alors nous obtenons le graphe suivant :

32


Fig. 2.4 Reprsentation graphique de la mthode PERT

2.3 Reprsentation des activits sur les nuds ( AoN)

Dans la reprsentation AoN, chaque activit est reprsente par un nud et chaque arc orient

reprsente une relation de prcdence requise entre deux activits.

Exemple : un projet compos des activits a, b, c, d et e, avec a prcde d, a prcde c, b prcdee, c prcde e, on aura le graphe suivant :

Fig. 2.5 Reprsentation AoN

Les nuds ctifs S et T reprsentent respectivement le dbut et la n du projet. Cette repr-sentation ne ncessite pas l'introduction d'activits ctives ( nuds) autre que celles de dbut et

n.

2.3.1 Graphe de la mthode du potentiel

[Tou90] On associe donc au problme central d'ordonnancement de projet un graphe dont les

sommets reprsentent les diverses tches du problme, on ajoute un nud 0 qui correspond ladate du dbut de projet et nud f = n + 1 qui correspond la n du projet. Les arcs du rseaureprsentent les contraintes de prcdence entre les tches. On peut construire systmatiquement

le graphe associ pour l'exemple prcdent, nous obtenons le graphe suivant :

33


Fig. 2.6 Prsentation graphique de la mthode du potentiel

Les contraintes de type potentiel autre que les contraintes d'antriorit du problme centrale

sont diciles prendre en compte dans le graphe potentiel-tape (PERT). On est en eet amen

ajouter des sommets et des arcs ctifs en trs grand nombre dans le graphe. En revanche dans le

graphe potentiel-tche, chaque contrainte supplmentaire de type potentiel s'introduit simplement

par l'adjonction d'un arc dans le graphe.

Les graphes de type disjonctif ou cumulatif sont impossible prendre en compte dans le graphe

potentiel-tape (PERT). Certains amnagements permettent leur prise en compte dans le graphe

potentiel-tche. On prfrera donc la reprsentation potentiel-tche ds que le problme ne se rduit

pas au problme centrale. Parmi les mthodes utilises pour reprsenter un projet sous forme d'un

graphe il y a la mthode PDM (Precedence Diagramming Method).

2.4 Modlisation par la programmation linaire

[CCM03]

2.4.1 L'ordonnancement avec les contraintes temporelles

Fixons nous les notations suivantes. Nous avons n tches excuter, indicesi = 1, . . . ,n. On adoptera dans toute la suite la notation di qui dsigne la dure d'excution de latche i.De mme on attribuera aux variables du problme des symboles qu'on notera ainsi par:

ti: le temps de dbut d'excution de la tche i.

tf : le temps de n du projet.

On s'appuie sur un graphe des prcdences (ou grpahe de projet) G = (X,U) dni par l'ensembledes tches X et l'ensemble des arcs U (l'arc (i,j) signie que la tche i prcde la tche j). Il estfacile de constuire ce graphe partir des listes de prdcesseurs du tableau qui liste les activits

et leurs relations de prcdence.

L'objectif tant de minimiser le temps de ralisation du projet, on crira la fonction objectif comme

suit:

minZ = tf t0 (2.1)o t0 dnote la date de dbut du chantier que l'on peut xer t0 = 0.Les contraintes du problme sont de trois types:

34


1. Les contraintes de localisation temporelles, expriment que la tche i ne peut commenceravant le dbut du chantier.

ti t0,i = 1,2, . . . ,n. (2.2)2. Les contraintes de succession temporelles expriment que la tche j ne peut dbuter avantque toute tche i pralable j ne soit nie:

ti + di tj,i j (2.3)

3. Les contraintes de n de projet expriment que la tche i doit tre nie avant la n du projet:

ti + di tf ,i = 1,2, . . . ,n. (2.4)

Nous avons donc le modle mathmatique suivant:minZ = tf t0

s.c : ti t0.ti + di tj.ti + di tf .i = 1,2, . . . ,n.

2.5 La mthode PDM (Precedence Diagramming Method)

2.5.1 Dnition

La Mthode PDM aussi appel mthode des antcidents a t dveloppe en 1964 par H.

B. Zachry en coopration avec IBM. C'est une mthode de gestion de projet parmi plusieurs

autres mthodes utilises pour reprsenter un projet sous forme d'un graphe. PDM fait partie des

reprsentation AoN (elle est issue de la mthode des potentiels (MPM)), elle utilise des rectangles

pour reprsenter les activits ou (tches) du projet, qui contiennent des informations relatives aux

tche, ces rectangles sont relis par des arcs ou ches qui montrent la dpendance logique entre les

tches. Elle peut tre utilise manuellement ou l'aide de l'outil informatique. C'est la mthode

la plus utilise par les logiciels de gestion de projet. Elle a largement remplace la mthode PERT

du type AoA.

2.5.2 Mthodologie de construction d'un graphe PDM

Pour construire le graphe PDM il faut respecter quelques rgles :

Reprsenter les tches dans des rectangles en indiquant les informations de la tche.

ES: Early Start. (Date dbut au plus tt)

EF: Early Finish. (Date n au plus tt)

LS: Late Start. (Date dbut au plus tard)

LF: Late Finish. (Date n au plus tard)

TFE: Total Float Early. (Marge total au plus tt)

TFL: Total Float Late. (Marge total au plus tard)

35


Fig. 2.7 Reprsentation d'une tche

Dur: Duration. (Dure de la tche)

Tche: Nom de la tche.

Lier les rectangles par des arcs en indiquant les dpendances logiques entre les tches. Il y'a

quatre dpendances logiques ou (Relations de prcdence):

1. Finish-to-Start "FS": (Fin-Dbut)

La notation FSij +0 signie que la tche j peut dbuter immdiatement aprs la n dela tche i.Cette relation est la seule prise en compte dans la reprsentation du type AoA.

FSij + x signie que le dbut de l'activit j peut avoir lieu au plus tt x-jours (jour :unit de temps) aprs la n de la tche i.

Fig. 2.8 Le lien Finish-to-Start(Fin-Dbut)

Si on dsigne par si la date de dbut de la tche i et par fi sa date de n d'excution,cette relation de prcdence se traduit par l'ingalit : Si >= fj + x

2. Start-to-Finish "SF" : (Dbut-Fin)

SFij + x signie que la n de la tche j a lieu au plus tt x-jours aprs le dbut del'activit i.Cette relation se traduit par l'ingalit fj >= si + x

Fig. 2.9 Le lien Start-to-Finish(Dbut-Fin)

3. Finish-to-Finish "FF" : (Fin-Fin)

FFij +x signie que la n de la tche j a lieu au plus tt x-jours aprs la n de la tchei.Cette relation se traduit par l'ingalit fj >= fi + x

36


Fig. 2.10 Le lien Finish-to-Finish(Fin-Fin)

4. Start-to-Start "SS":(Dbut-Dbut)

SSij + 0 signie que la tche j peut dbuter ds que (ou en mme temps) la tche i adbut.

SSij + x signie que la tche j peut dmarrer au plus tt, x-jours aprs le dbut de latche i.Cette relation se traduit par l'ingalit sj >= si + x

Fig. 2.11 Le lien Start-to-Start (Dbut-Dbut)

Respecter l'avance (Lead) et le retard (Lag) appliqu aux liens logiques:

- Le retard (Lag) a l'eet de retarder la tche successive par le nombre d'units de temps

spcies.

Exemple:

Fig. 2.12 Lag appliqu un lien

- l'avance (Lead) a l'eet d'acclrer la tche succssive par le nombre de temps spci.

L'avance est autoris dans certains logiciels, mais elles doivent tre utilises avec prudence.

37


Fig. 2.13 Lead appliqu un lien

Faire relier toutes les tches qui n'ont pas de prdcesseur vers une tche ctive commune

appel "Dbut".

Fig. 2.14 tape dbut d'un graphe PDM

Faire relier toutes les tches qui n'ont pas de successeur vers une tche ctive commune

appel "Fin"

Fig. 2.15 tape n d'un graphe PDM

2.5.3 Etablir la liste des tches

C'est le processus qui consiste identier les actions spciques entreprendre pour produire

les livrables du projet. Le processus Crer le (WBS)identie les livrables au niveau le plus bas de

la structure de dcoupage du projet (WBS), c'est- -dire, le lot de travail. Les lots de travail du

projet sont habituellement dcomposs en composants plus petits, appels tches, qui reprsentent

le travail ncessaire l'achvement du lot de travail. Chaque tche sera codie an d'allger la

38


reprsentation graphique du rseau.

Exemple :

Code Tches

A terrassement

B fondation

C colonnes porteuses

D charpente toiture

E couverture

F maonnerie

G plomberie,lectricit

H coulage dalle bton

I chauage

J pltre

K nitions

Tab. 2.2 La liste des tches

2.5.4 Dterminer les conditions d'antriorit

C'est le processus qui consiste identier et documenter les relations entre les tches du

projet. Les activits sont organises en squence sur la base de liens logiques. Chaque tche et

chaque jalon, l'exception des premiers et des derniers, est li au moins un prdcesseur et un

successeur. Cette tape consiste dterminer exactement les relations d'antcdence entre tches.

Elle rpond aux questions suivantes : Quelle(s) tche(s) doit tre termine immdiatement avant

qu'une autre ne commence? Quelle(s) tche(s) doit suivre une tche termine?

Exemple :

Code Tches Prcdents

A terrassement -

B fondation A

C colonnes porteuses B

D charpente toiture C

E couverture D

F maonnerie C

G plomberie,lectricit B

H coulage dalle bton G

I chauage H;F

J pltre E;I

K nitions J

Tab. 2.3 Les relations d'anticidence

39


2.5.5 Estimer les ressources ncessaires aux activits.

C'est le processus qui consiste dnir le prol des personnes et estimer leur nombre, le

type et la quantit de matriels, d'quipements ou de fournitures, ncessaires l'accomplissement

de chaque activit.

exemple

Code Tches Prcdents Consommation de ressources

A terrassement - 1 ouvrier

B fondation A 3 ouvriers

C colonnes porteuses B 2 ouvriers

D charpente toiture C 2 ouvriers

E couverture D 4 ouvriers

F maonnerie C 3 ouvriers

G plomberie,lectricit B 2 ouvriers

H coulage dalle bton G 2 ouvriers

I chauage H;F 1 ouvrier

J pltre E;I 4 ouvriers

K nitions J 1 ouvrier

Tab. 2.4 Estimation des ressources

2.5.6 Estimer la dure de chaque tche.

C'est le processus qui consiste estimer le nombre de priodes de travail requises pour achever

chacune des tches avec les ressources estimes. La dure d'une tche est souvent fonction de l'im-

portance des ressources aectes pour la raliser. On utilise l'une des quatre techniques suivantes:

1. Jugement d'expert:

Bas sur l'information historique, le jugement d'expert peut fournir des informations sur

l'estimation de la dure ou la dure maximale recommande des activits provenant de projets

antrieurs similaires.

2. Estimation par analogie

L'estimation par analogie utilise les paramtres d'un projet antrieur similaire, tels que la

dure, le budget, la taille, la charge et la complexit, comme base pour l'estimation des

paramtres ou mesures semblables dans un projet futur.

L'estimation de la dure par analogie est frquemment utilise pour estimer la dure d'un

projet lorsque l'on dispose de peu d'informations dtailles sur ce dernier, comme c'est le

cas, par exemple, lors des phases initiales d'un projet.

L'estimation par analogie utilise l'information historique et le jugement d'expert.

Le plus souvent, l'estimation par analogie est moins onreuse et prend moins de temps que

les autres techniques, mais d'une faon gnrale, elle est galement moins prcise.

3. Estimation paramtrique

L'estimation paramtrique utilise une relation statistique entre les donnes historiques et les

autres variables (par exemple, la supercie m2) pour estimer les paramtres d'une activit,

40


tels que le cot, le budget et la dure.

La dure des activits peut tre quantitativement dtermine en multipliant la quantit de

travail eectuer par le nombre d'heures de main d'oeuvre par unit de travail.

Par exemple, dans un projet de conception, la dure d'une activit peut tre estime en

multipliant le nombre de dessins par le nombre d'heures de travail requises par dessin, ou,

pour un projet de cblage, en multipliant le mtrage de cble par le nombre d'heures de

travail par mtre de cble. Si, par exemple, les ressources alloues sont capables d'installer

25 mtres de cble par heure, la dure requise d'installation de 1 000 mtres de cble sera

de 40 heures.(1 000 mtres divis par 25 mtres par heure).

4. Estimation trois points (loi Bta)

La dure t de chaque tche du projet est considre comme alatoire, de distribution Bta.Les paramtres de la distribution Bta sont calculs moyennant une hypothse de calcul as-

sez forte partir des trois paramtres A, B et M0.Il sut donc de poser les trois questionssuivantes:

- Quelle est la dure minimum de ralisation de la tche?

- Quelle est la dure maximale de ralisation de la tche?

- Quelle est la dure la plus probable?

Pour obtenir respectivement les paramtres A, B etM0qui permettent de calculer la moyenne, partir des formules suivantes:

E(t) =A+B + 4M0

6

Fig. 2.16 Distribution Bta

41


Exemple :

Code T

Documents

Planification Et Gestion de Projet