République Algérienne Démocratique et Populaire

Ministre de l’Enseignement Supérieur et de la Recherche Scientifique

Université Abderrahmane Mira-Bejaia

Faculté des Sciences Exactes

Département Recherche Opérationnelle

Mémoire de fin de cycle

En vue de l’obtention du diplôme Master en Mathématiques appliquées Option :
Modélisation Mathématique et Techniques de Décision

THÈME
Ordonnancement des tâches pour la rénovation de la
base de vie Bordj Menaiel Sonatrach

Réaliser par :

- ABID Wissam - BAOUZ Sarah

Les jury :
- Président : Mr Khimoum. N M.C.B Université de béjaia.
- Encadrant : Mr AISSANI. Dj Professeur université de béjaia.
Mlle AOUDIA. Z M.A.A université de béjaia.
-Invité : Mr BENACER. M Ingénieur Sonatrach de Bejaia
- Examinatrices : Mme BOUCHEBAH. K M.A.A université de béjaia.
Mme HALIMI. N M.C.A université de béjaia.

Année universitaire : 2021/2022

 Dédicaces

Rien n’est aussi beau à offrir que le fruit d’un labeur qu’on dédie du fond du cœur à ceux
qu’on aime et qu’on remercie en exprimant la gratitude et la reconnaissance durant toute notre
existence.

Je dédie ce travail :

À mes chers paraents, pour tous leurs sacrifices, leurs amour, leur tendresse, leurs soutien, et
leurs prières tous au long de mes études.

À mes chers frères : Mehand Akli, Yacine, Djilali et Billel.

À mes chères cousines : Sonia, Yasmine et Amel.

À mes chères amies : Mélissa, Dyhia, Imene, et Massilia.

À ma chère binôme : Sarah.

Que ce travail soit l’accomplissement de vos vœux tant allégués, et le fruit de votre soutien
infaillible.
Merci d’être toujours là pour moi.

Wissam.
 Dédicaces

Je dédie ce travail :

À ma chère maman, pour tous son sacrifice, son amour, sa tendresse, son soutien, et ses
prières tous au long de mes études.

À mes chers frères : Mabrouk, Amar, Djamel et Abd elaziz.

À tout mes neveux et mes nièces surtout Chehra et Saloua et mon neveu Louanes.

À mes chers amis : Léna, Djaafer, Yachi, Mebrouk et Linda.

À ma chère binôme : Wissam.

Que ce travail soit l’accomplissement de vos vœux tant allégués, et le fruit de votre soutien
infaillible.
Merci d’être toujours là pour moi.

Sarah.
 Remerciements

Ce mémoire marque une étape très importante dans notre vie, couronnant nos
années d’études universitaires. Nous voudrions remercier ici les personnes qui
nous ont accompagnés au cours de notre parcours.

Tout d’abord, nous remercions ‘’Dieu” le Tout puissant de nous avoir donné le
courage, la force et la patience pour faire aboutir ce travail.
Nous tenons particulièrement à remercier très chaleureusement notre encadrant
Mr DJ. AISSANI, et notre Co-encadrant Mlle Z. AOUDIA, nous avons pu
profiter de leurs connaissances scientifiques, de leur orientation, du soutien mo-
ral et intellectuel qu’ils nous ont apporté. Ils nous ont permis de bénéficier de
leurs encadrements, les précieux conseils qu’ils nous ont été déterminantes dans
la réalisation de notre travail de recherche.
Nous remercions chaleureusement tout le personnel de la RTC , particuliè-
rement le département des traveaux de nous avoir accueilli durant notre stage .
Nous remercions particuliérement notre co-encadrant Mr BENNACER Mahdi,
de nous avoir encouragé et soutenu.
Nous tenons également à remercier vivement les membres de jury :
Nous adressons nos plus sincères remerciements à tous nos proches et amis qui
nous ont toujours soutenue et encouragés au cours de la réalisation de ce mémoire.

Ces remerciement ne seraient pas complets sans un pense pour nos parents, nos
frères et nos sœurs. Merci de nous avoir encouragé et soutenues tout au long de
ces années et de nous avoir permis à bien nos études.
 Table des matières

Table des figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VIII

Liste des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IX

Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

I Présentation de l’entreprise SONATRACH. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3

I.1 Présentation de l’entreprise SONATRACH . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
I.1.1 Création de la SONATRACH. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
I.1.2 Mission de la SONATRACH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I.1.3 Objectif et Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I.1.4 Situation géographique et organisation de la RTC Bejaia. . . . . . . . . . . . . . .6
I.2 Présentation de RTC-sonatrach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
I.3 SONATRACH-RTC (Béjaia) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
I.3.1 Organisation Structurelle et Fonctionnelle de la RTC Bejaia . . . . . . . . . . . 8
I.3.2 Les différentes Structures de la RTC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I.3.3 La structure de la RTC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
I.3.4 Présentation de la structure d’accueil (TNF) . . . . . . . . . . . . . . . . . . . . . . . . . 11
I.4 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

IV
II L’ordonnancement gestion de projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
II.1 Définition du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
II.1.1 Cycle de vie d’un projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
II.1.2 Les objectifs d’un projet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
II.1.3 Management de projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
II.1.4 Étapes de réalisation d’un projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
II.1.4.1 Première étape : Définir l’envergure du projet . . . . . . . . . . . . . . . . . . 18
II.1.4.2 Deuxième étape : Etablir les priorités du projet . . . . . . . . . . . . . . . . 18
II.1.4.3 Troisième étape : Créer une structure de découpage du projet . . 19
II.1.5 Structure de découpage du projet (Work Breakdown Structure (WBS))19
II.2 Problème d’ordonnancement de projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
II.2.1 Tâche / Activité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
II.2.2 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
II.2.3 Définition de l’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
II.2.4 Objectif de l’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
II.3 Quelques concepts de la théorie des graphes . . . . . . . . . . . . . . . . . . . . . . 22
II.3.1 Définition d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
II.3.2 Date au plus tôt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23
II.3.3 Date au plus tard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
II.3.4 Tâche critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
II.3.5 Chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
II.3.6 Marges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

III Techniques d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

III.1 Le diagramme de GANTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
III.2 La méthode du Potentiel-Metra MPM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
III.3 La méthode PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
III.3.1 Construction du graphe PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
III.3.2 Détermination des dates et des marges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

V
 III.4 Méthodes de résolution du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
III.4.1 Les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

IV Modelisation et résolution du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
IV.1 Présentation générale du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
IV.1.1 Les caractères du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
IV.1.2 Description des ouvrages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
IV.2 Décomposition du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
IV.3 Détermination de la durée des tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
IV.4 Résolution par la méthode PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
IV.4.1 Les données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
IV.4.2 Construction de réseau PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
IV.4.3 Détermination des dates et des marges par rapport à la table IV.3 . . . . 42
IV.4.4 Le chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
IV.4.5 Résultat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43
IV.5 Utilisation du diagramme de GANTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
IV.6 Utilisation du logiciel Ms Project 2016 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
IV.6.1 Définir la date de début du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
IV.6.2 Paramètre le calendrier du projet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
IV.6.3 Définir la semaine de travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
IV.6.4 Créer des tâches et leurs durées dans l’affichage GANTT . . . . . . . . . . . . . 46
IV.6.5 Créer des liens d’antériorité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
IV.6.6 Afficher le diagramme de GANTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
IV.6.7 Affichage du chemin critique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
IV.7 Résolution par la programmation linéaire. . . . . . . . . . . . . . . . . . . . . . . . . .50
IV.7.1 Les données du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
IV.7.2 Les variables de décision. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50
IV.7.3 La fonction objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

VI
 IV.7.4 Les contraintes de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
IV.7.4.1Les contraintes de successions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
IV.7.5 Le modèle mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
IV.7.6 Application avec la méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

VII
 Table des figures

I.1 Réseau de Transport par Canalisation. . . . . . . . . . . . . . . . . . . . . . . . 7

I.2 Organigramme de la RTC-Bejaia. . . . . . . . . . . . . . . . . . . . . . . . . . . 9
I.3 Organigramme de la RTC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
I.4 Organigramme de la structure d’accueil (TNF). . . . . . . . . . . . . . . . . . . 12

II.1 Cycle de vie d’un projet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

II.2 Le triangle d’or. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
II.3 Structure de découpage d’un projet (WBS). . . . . . . . . . . . . . . . . . . . . 19
II.4 Caractéristiques d’une tâche i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

III.1 Diagramme de GANTT de la table d’ordonnancement T. . . . . . . . . . . . . . 26

III.2 Le graphe PERT associé. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

IV.1 Situation géographique de la Base de vie BBM. . . . . . . . . . . . . . . . . . . 35

IV.2 Réseau PERT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
IV.3 La date de début du projet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
IV.4 La date de début du projet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
IV.5 Les options de calendrier. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
IV.6 La liste des tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
IV.7 Les liens d’antériorité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
IV.8 Le diagramme de GANTT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
IV.9 Le chemin critique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
IV.10Les données. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
IV.11Exécution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
IV.12Résultat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

VIII
 Liste des tableaux

III.1 Table initiale d’ordonnancement T. . . . . . . . . . . . . . . . . . . . . . . . . . 26

III.2 Tableau des tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
III.3 Les marges libres et les marges totales. . . . . . . . . . . . . . . . . . . . . . . . 30

IV.1 Liste des tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

IV.2 Liste des tâches et leurs durées. . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
IV.3 Tableau des activités de projet. . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
IV.4 Des dates et des marges par rapport à la table IV.3 . . . . . . . . . . . . . . . . 42

IX
 Introduction générale

La recherche opérationnelle (RO) est la discipline des méthodes scientifiques utilisables pour
élaborer de meilleures décisions. Elle permet de rationaliser, de simuler et d’optimiser l’archi-
tecture et le fonctionnement des systèmes de production ou d’organisation. C’est une discipline
des mathématiques appliquées qui s’intéresse à l’application du savoir mathématique aux autres
domaines [1].

La Sonatrach est une compagnie étatique algérienne et un acteur international majeur dans
l’industrie des hydrocarbures. Le groupe pétrolier et gazier est classé 1er en Afrique et 12me dans
le monde en 2013, toutes activitès confondues, avec un chiffre d’affaires à l’exportation de plus
de 63 milliards de US $.
Née le 31 décembre 1963, la compagnie intervient dans l’exploration, la production, le trans-
port par canalisations, la transformation et la commercialisation des hydrocarbures et de leurs
dérivés.
La région de transport Centre de Béjaia est l’une des cinq régions composant l’activité de
transport des hydrocarbures par canalisation de l’entreprise Sonatrach. Elle est subdivisée en
03 structures de soutien rattachées directement à la direction : les stations de pompage, les
terminaux (nord et sud), et le port pétrolier. Dans le but d’améliorer les conditions d’exploitation
et de sécurité des installations du port pétrolier, des travaux de rénovation des installations ont
été entamés en 2006. Toutefois, les travaux n’ont pas été menés à terme par le précédent maître
de l’oeuvre. Par conséquent, la tâche principale du nouveau marché consiste en la réhabilitation
et la mise en service des installations de surface du port pétrolier de Béjaïa. Les travaux restants
à réaliser sont essentiellement : les travaux de dépose, démolition et évacuation. Et les travaux
des ouvrages neufs à réaliser.

1
 La réalisation d’un projet nécessite souvent une succession de tâches aux-quelles s’attachent
certaines contraintes :

- De temps : délais à respecter pour l’exécution des tâches ;

- D’antériorité : certaines tâches doivent s’exécuter avant d’autres ;
- De production : temps d’occupation du matériel ou des hommes qui l’utilisent.

L’objectif de ce mémoire est de trouver un ordonnancement de tâches de durée minimale,

afin de réduire le délai de réalisation du projet de rénovation de la base de vie BBM Bordj
Menaïel. Et ce en utilisant les différentes méthodes de modélisation et de résolution du pro-
blème d’ordonnancement de projet.

La gestion de projet est un champs multidisciplinaire, et une composante très importante

de la communauté de recherche opérationnelle fondée sur l’idée que gérer des projets est diffé-
rent de gérer d’autres types d’activités, une distinction souvent présentée comme la différence
entre des projets temporaires qui produisent des résultats uniques et les opérations répétitives
et continues. C’est un champ très appliqué qui a connu une forte croissance depuis le milieu des
années 1990. La gestion de projet est une branche très appliquée dans laquelle les associations
ont historiquement joué et continuent de jouer un rôle très important. À l’origine, le champ s’est
intéressé surtout aux techniques de planification de projets et le peu de recherche qu’il y avait
étaient dans le domaine de la recherche opérationnelle.

La théorie de l’ordonnancement de projet est une branche de la recherche opérationnelle

qui consiste en la programmation de ses tâches et des ressources nécessaires à leurs exécution,
qui respecte les différentes contraintes techniques du projet et les disponibilités des ressources
utilisées.

Ce mémoire se divise en quatre chapitres. Au chapitre 1, une présentation de la société Sona-

trach, avec la position du problème. Ensuite, au chapitre 2, nous donnons quelques généralités
sur la planification et la gestion de projet. Le chapitre 3 présente les méthodes de modélisation
et d’ordonnancement de projet. Finalement, le chapitre 4 est réservé à l’application des tech-
niques et méthodes citées au chapitre 3 à notre problème. Nous terminons notre travail par une
conclusion générale, dans laquelle nous donnons quelques perspectives prévues.

2
 I

Présentation de l’entreprise
SONATRACH

Dans un premier temps, nous commençons par présenter la société Sonatrach et la direction
régionale RTC Béjaia, afin de bien cerner notre sujet d’étude. Nous évoquons les principaux
éléments, notamment le domaine d’activité, la situation géographique et les différentes structures.
Á la fin de ce chapitre , nous exposons la position du problème.

I.1 Présentation de l’entreprise SONATRACH

L’entreprise SONATRACH est considérée comme la plaque tournante de l’entreprise algé-
rienne. Elle assure plus de 95% des recettes de l’Etat, mais seulement 15% des recettes reviennent
à l’entreprise pour ses propres besoins d’exploitation et de fonctionnement.

I.1.1 Création de la SONATRACH

La SONATRACH à été crée, le 31 décembre 1963 par la décret n 63/49. La dimension natio-
nale de cette entreprise s’est spontanément identifiée à celle donnée au pétrole, puis à tout terme
générique d’hydrocarbures dans lequel le gaz occupera, peu à peu, une place prépondérante.

3
I.1.2 Mission de la SONATRACH
Dés sa création, SONATRACH qui avait pour mission de prendre en charge le transport
et la commercialisation des hydrocarbures dans un contexte marqué alors par la mainmise des
compagnies étrangères sur le parcours en réalisant l’oléoduc Haoud-el-Hamra / Arzew d’une
longueur de 801Km.
Après avoir vu en 1996 ses missions étendues à l’ensemble des activités pétrolières, La SONA-
TRACH est confirmée dans son rôle d’outil privilégié de la politique nationale dans le domaine
des hydrocarbures, le 24/02/1971.

Elle s’attelle dés lors à consolider le processus de récupération totale des richesses pétrolières
et gazières ainsi que leurs maitrises technologiques tout en sauvegardant l’approvisionnement
énergique du pays, et en pourvoyant aux recettes en devises nécessaires à son développement,
parallèlement à ce rythme soutenu sur le terrain, les débouchés aux produits pétroliers et gaziers
sont assurés en aval par une remarquable percée commerciale sur le marché international.

Aujourd’hui, la SONATRACH assure des missions stratégiques centrées sur la recherche, la

production, le traitement, la liquéfaction du G.P.L, de l’approvisionnement du marché national
et la commercialisation des hydrocarbures liquides et gazeux sur le marché international, les
activités découlant de ces missions demeurent les soucis des 40000 employés dont environs 10000
cadres qui constituent l’effectif de la SONATRACH.

I.1.3 Objectif et Evolution

Les objectifs de la SONATRACH durant les 25 années à venir consistent à doubler le rythme
de la production pour atteindre la barre des 100 Tep annuellement, ce qui donnera une produc-
tion cumulée prévisionnelle de 2 milliards de Tep à la fin de l’année 2021.

Si parallèlement les efforts d’exploitation et de prospection des hydrocarbures ne suffisent

pas à renouveler la totalité des réserves en place par la découverte de nouveaux gisements, on
irait irrémédiablement vers un déséquilibre énergétique très grave. Le programme des réserves
à maintenir la même durée à venir a été élaboré en fonction d’une espérance de découvertes de
gisement équivalent à 144 millions de Tep annuellement.

Il est évident que si l’on tient compte du volume de réserves potentiellement récupérables,
cette découverte ne suffirait pas à couvrir notre rythme de production des hydrocarbures ou
encore moins, rattraper le retard en matière de ressources énergétiques.

4
 Il est donc très important pour le secteur de l’énergie de la SONATRACH de tracer une
nouvelle politique énergétique ayant pour but essentiel de préserver et consolider la dynamique
de production et l’exploitation des hydrocarbures.

Aujourd’hui, l’évolution de l’économie mondiale des hydrocarbures ne laisse pas d’autres al-
ternatives à la SONATRACH que l’adaptation, l’amélioration et la modernisation des conditions
de travail .Pour cela, la SONATRACH s’appuie sur les valeurs fondamentales de la culture de
l’entreprise, l’engagement dans l’intérêt et l’esprit de l’éthique.

Le professionnalisme, la quête de l’excellence constituent les valeurs de l’entreprise ; le déve-

loppement de la SONATRACH se fait par une volonté qui s’appuie sur :

• La compétence technologique.
• L’amélioration de la qualité de l’environnement social.
• La satisfaction de la clientèle.
• Le transfert du savoir-faire.

Les activités de la SONATRACH se résument comme suit :

• L’Exploration, la Recherche et l’Exploitation des gisements d’hydrocarbures (E/P ).
• La liquéfaction et la transformation du gaz (LQS).
• Le transport par canalisation (TRC).
• Raffinage et Pétrochimie (RPC).
• La commercialisation des hydrocarbures (COM).

Le but recherché par la restriction et la réorganisation est la décentralisation des pouvoirs.

La SONATRACH exerce ses activités dans quatre principaux domaines à savoir :

• Activité E/P : recouvre les métiers de la recherche, de l’exploration, du développement et

de la production des hydrocarbures.
• Activité TRC : assure l’acheminement des différents hydrocarbures par canalisation.
• Activité LQS : a pour charge le développement et l’exploitation des complexes hydrocarbures
(liquéfaction, raffinerie).
• Activité COM : a pour mission l’élaboration et l’application de la stratégie commerciales
de SONATRACH sur le marché national et international.

5
I.1.4 Situation géographique et organisation de la RTC Bejaia
La RTC Bejaia se situe à 2Km au nord-ouest, au niveau l’arrière port, à l’entrée de la ville
de Bejaia.

La Région Transport Centre est constituée d’un Port Pétrolier et d’un Terminal Arrivée
Comportant 02 parcs de stockage. La RTC est confiée à la branche de transport par canalisation
(pipeline) des hydrocarbures, le développement, la gestion de la maintenance d’un réseau de 2
pipe-lines en exploitation, ainsi que les installations suivantes :

• 04 stations de pompage et une station de compression en exploitation.

• 16 bacs de stockages en exploitation.

I.2 Présentation de RTC-sonatrach

L’activité transport est confiée a la branche ≪ Transport par Canalisation ≫ (TRC) dont
la mission principale est d’assurer le transport des hydrocarbures par pipe-line.

Ainsi, huit régions de l’activité transport par canalisation, ont été crées, à savoir :

• RTC : Région Transport Centre (Béjaia).

• RTH : Région Transport de Haoud el-Hamra (Centre de distribution).

• RTI : Région Transport d’In Aminas.

• RTE : Région Transport Est (Skikda).

• RTO : Région Transport Ouest (Arzew).

• GHR : Gazoducs Hassi R’mel.

• GEM : Gazoducs Enrico-Mattei.

• GPDF : Gazoducs Pedro-Durel farrel.

6
 Figure I.1 – Réseau de Transport par Canalisation.

I.3 SONATRACH-RTC (Béjaia)

La société pétrolière de gérance (SOPEG) est devenue depuis, la Direction Régionale de Be-
jaia (DRGB), elle-même devenue Région Transport Centre (RTC) . Le siège de la RTC est située
au nord de Béjaia (arrière port) à l’entrée de la ville s’étend sur une superficie globale répartie
comme suit :

∗ Terminaux (nord et sud) :

• Surface clôturée : 516135m2 .
• Surface couverte : 7832m2 .
• Surface occupée par les bacs : 43688m2 .
• Surface non clôturée : 2250m2 .
• Surface de stockage : 3800m2 .

7
∗ Port Pétrolier :
• Surface clôturée : 19841m2 .
• Surface couverte : 300m2 .
• Surface occupée par les bassins de déballastage : 1600m2 .

La RTC compte quatre stations de pompage et deux terminaux qui sont :

∗ SP1 BIS : Station de pompage à Djemaa (EL-Oued ) : Elle assure un débit maximum de
2200m3 /h. Elle est essentiellement équipée de :
• 03 turbopompes (TPA, TPB et TPC), mais les deux premières ne sont plus en état de
marche.
• 02 bacs de stockage d’une capacité 450m3 chacun.
∗ SP2 : Station de Pompage a Biskra : Elle est équipée de :
• 05 groupes motopompes (GMP) placées en série.
• 03 électropompes boosters placées en parallèle.
• 02 groupes électrogènes assurant le relais en cas de disjonction.
• Un groupe électrogène de secours.
• 02 bacs tampons d’une capacité 2900m3 .

∗ SP3 : Station de Pompage à M’sila : dans cette station, on retrouve exactement les mêmes
installations que celles de la SP 2, à l’exception du montage des GEP qui sont branchés en
parallèle.
∗ SBM : Station de Pompage Beni-Mansour.
∗ TRA : Terminal Raffinerie d’Alger.
∗ TMB : Terminal Marin de Béjaia.
La RTC est chargée du transport, du stockage et de la livraison du pétrole transportés à
travers les deux canalisations gérées par celle-ci, qui sont de 24 pouces et de 20 pouces.
Sa capacité de transport est d’environ 14 millions de tonnes, la capacité réelle de transport est
d’environ 11 millions de tonnes, sont acheminées à la raffinerie d’Alger.

L’effectif total de la RTC est de 2819 personnes réparties comme suit :

• 864 : permanents.
• 1955 : temporaires.

I.3.1 Organisation Structurelle et Fonctionnelle de la RTC Bejaia

Les différentes départements et directions de la RTC sont représentés sur l’organigramme
I.2.

8
Figure I.2 – Organigramme de la RTC-Bejaia.

9
I.3.2 Les différentes Structures de la RTC
• La Direction Régionale : Son rôle est de coordonner les efforts des différents départements
et sous-directions de la région, elle est dirigée par un directeur régional.
• Secrétariat : Son rôle est d’aider le directeur régional.
• Assistant de Sécurité Interne (ASI) : Il veille à la sécurité et à l’intégrité des installations
et des personnes de la région.
• Département HSE : Il a pour mission la protection et la sauvegarde du patrimoine humain et
matériel de la région et veille au respect et à la stricte application des normes et standards
en matière d’hygiène, de sécurité et de protection de l’environnement.
• Centre Informatique.
• Sous-direction Exploitation : Chargée des exploitations des installations de la région. Elle
est composée de deux départements qui sont :
∗ Département Exploitation Liquide.
∗ Département Exploitation Gaz.
• Sous-direction Administration : Elle a pour mission la gestion des ressources humaines et
les moyens généraux ; elle est organisée en trois départements :
∗ Département Administration et Social.
∗ Département Ressources Humaines et Communication.
∗ Département Moyens Généraux.
• Sous-direction Finances : La sous-direction Finance est composée de deux départements :
∗ Département Finance (FIN).
∗ Département Budget (BDG).
• Direction Juridique (JUR).
• Sous-direction Technique : Elle a pour mission d’assurer la maintenance et la protection
des ouvrages, ainsi que l’approvisionnement, l’étude et le suivi de projet de réalisation de
travaux neufs . Elle se compose de huit départements :
∗ Département Entretien Lignes et Bacs (ELB).
∗ Département des Ouvrages (PTO).
∗ Département Protection Cathodique (PCA).
∗ Département Approvisionnement et Transport (ATR).
∗ Département Travaux neufs (TNF).
∗ Département Maintenance (MTN).
∗ Département Méthode (MET).
∗ Département Passation des Marchés (PSM).

10
I.3.3 La structure de la RTC
Les différentes structures de la RTC sont présentées dans le nouvel organigramme (fait en
2017) défini ci-dessous :

Figure I.3 – Organigramme de la RTC.

I.3.4 Présentation de la structure d’accueil (TNF)

Département Travaux Neufs (TNF) : Ce département est chargé des études de l’assistance
technique et de suivi des réalisations des projets d’investissement et des travaux neufs. Il prend
aussi en charge les travaux de rénovation des installations demandés par les différentes structures.
Le département travaux neufs gère environ quatre-vingt (80%) pour cent du budget global de
la région. Ce département est actuellement structuré comme suit :
• Service études industrielles.
• Service technique et suivi des réalisations.
• Section archivage et documentation.
Notre travail est en relation directe avec les activités de ce département. L’organigramme du
département TNF est représenté ci-dessous :

11
 Figure I.4 – Organigramme de la structure d’accueil (TNF).

• Secrétariat : S’occupe de la communication et diffusion de l’information, ainsi que l’élabo-

ration de la correspondance et le traitement du courrier et documents.
• Service études Industrielles : Il est composé actuellement d’ingénieurs études et d’une
section archive et documentation. Les ingénieurs d’études ont la charge de préparer les
dossiers d’appels d’offres "DAO" pour les projets inscrits au budget de la RTC. Une fois
l’appel d’offre aboutis dans le respect strict de la procédure de passation des marchés de
SONATRACH, le service technique et suivi de réalisation prend le relai pour la concréti-
sation du projet.
• Service technique et Suivi des réalisations : Ce service est composé d’ingénieurs de suivi
et d’un ingénieur planning et ordonnancement.

I.4 Problématique
Ce mémoire traite une problématique rencontrée en entreprise, il s’agit de trouver un ordon-
nancement des tâches pour le projet de renovtion de la base de vie Bordj Menaiel, en minimisant
son délai de réalisation.

La planification et l’ordonnancement d’un projet sont des moyens incontournables pour le

bon déroulement d’un projet. Ne pas plannifier le projet est une erreur préjudiciable, cela revient
à se priver :

- D’un outil de communication et de coordination au sein du projet ;

- D’un outil de contrôle de la bonne exécution de toutes les phases et de l’atteinte des
objectifs ;
- D’un outil de rationnalisation, de gestion des risques et de prise de décisions pour le chef
de projet.

12
Conclusion
Nous avons effectué notre stage au sein de la Sonatrach (RTC Béjaia). Au cours de ce stage
au niveau du département des travaux neufs, nous avons pu nous intéresser aux techniques
de suivi, de réalisation, et de planification des projets. Ce stage a été l’opportunité pour nous
d’appréhender de nouvelles connaissances sur le domaine de la planification et la gestion de
grands projets. Ainsi que sur le domaine de transport par canalisation des hydrocarbures.
Nous avons introduit à la fin de ce chapitre la problèmatique soulevée.

13
 II

L’ordonnancement gestion de projet

La planification a pour objectif d’organiser le déroulement des étapes du projet dans le temps.
Une tâche fondamentale pour la maîtrise des délais. Généralement pour planifier un projet, la
première phase consiste à le découper en plusieurs étapes, d’en estimer la durée, d’identifier
l’enchaînement des étapes (dont celles qui peuvent être conduites en parallèle), affecter des
ressources (financières et humaines), et enfin modéliser cette organisation sur un document
opérationnel partagé entre tous les acteurs concernés.
Pour bien nous situer, nous allons faire un tour d’horizon sur la gestion de projet.

II.1 Définition du projet

Un projet se définit comme une démarche spécifique qui permet de structurer méthodique-
ment et progressivement une réalité à venir. Un projet est donc un processus unique, qui consiste
en un ensemble d’activités coordonnées, faisant appel à diverses compétences et ressources de
l’entreprise, dans le but d’atteindre un objectif conforme à des exigences spécifiques, telles que
des contraintes de délais, de coûts et de ressources [2].

14
II.1.1 Cycle de vie d’un projet
En général, le cycle de vie d’un projet comporte 4 phases successives (voir la figure II.1) :

Définition : Définir les spécifications du projet, établir ses objectifs, former des équipements
et on assigne les principales responsabilités.
Planification : On élabore des plans pour déterminer tout ce que le projet implique, le
moment de l’ordonnancement, à qu’il profitera, le niveau de qualité qui devra être conservé et
le budget qui sera retenu.
Exécution et contrôle (suivi) : Une importante partie du travail physique et intellectuel
du projet s’effectuera à cette étape, où a lieu la fabrication du produit physique, l’évaluation de la
durée, les coûts et les spécifications, pour contrôler les résultats ; ainsi que la vérification régulière
et continue de la bonne marche du projet pour intégrer, au fur et à mesure du déroulement, les
actions correctives nécessaires.
Clôture : Elle comprend :

- La livraison du projet au client

- Le redéploiement des ressources.

Figure II.1 – Cycle de vie d’un projet.

15
II.1.2 Les objectifs d’un projet
Dans tout projet, on peut identifier trois catégories d’objectifs, qui sont souvent antagonistes :

Les objectifs de performance techniques : Relatifs au respect des spécifications fonc-

tionnelles et des caractéristiques techniques du produit. Ainsi, on se définit un niveau de qua-
lité en ce qui concerne, par exemple le respect de tolérance, la fiabilité du produit, la facilité
d’usage,. . .
Les objectifs de délai : Sont une composante trés importante pour le client. Ainsi, il ne
sert à rien de livrer un stade olympique trois mois après la fin des jeux olympiques. D’autre part,
dans un marché concurrentiel, tel que, par exemple, celui des produits pharmaceutiques, être le
premier à mettre sur le marché un nouveau vaccin ou un nouveau médicament peut représenter
un effet de monopole et des gains substantiels pour le premier arrivé sur le marché.
Les objectifs de coût : Sont primordiaux, notamment dans le cadre d’un contrat à prix
non révisable ou dans le cas d’un projet interne.

Ces objectifs sont fortement liées. Par exemple, il est plus facile de respecter des objectifs
techniques si le délai imparti est plus grand, ou si les ressources mises en oeuvre sont plus nom-
breuses et donc plus onéreuses.

Ces trois points forme donc un triangle d’or, qui est l’image couramment retenue pour ca-
ractériser les trois paramètres fondamentaux d’un projet. La réussite d’un projet passe par la
satisfaction des ces derniers [3].

Figure II.2 – Le triangle d’or.

16
II.1.3 Management de projet
Le management de projet recouvre l’ensemble des tâches qui permettent de conduire une
opération quelconque à bonne fin ; il comprendra les tâches de direction, gestion, maîtrise et
pilotage. Piloter un projet, c’est mener à bien et à temps les actions qui vont produire le résultat
du projet. C’est une des fonctions du management de projet [4].

Selon la norme AFNOR (Association Française de Normalisation) Le management de projets

regroupe deux fonctions bien différentes :

La direction de projet : Qui s’intéresse aux décisions stratégiques (décisions à long terme
mettant en jeu l’avenir de l’entreprise) cette fonction est assurée par un chef de projet assisté
parfois d’une équipe.
Il consiste à :

- Fixer le cadre stratégique (objectifs, moyens, programmes) ;

- Prioriser les actions ;
- Coordonner les activités et les différents projets ;
- Gérer les changements stratégiques ;
- Optimiser les ressources.

La gestion de projet : Qui s’intéresse aux décisions opérationnelles (décisions à court

terme de gestion des équipements et du personnel), elle est assurée par un contrôleur de projet.
Elle a pour objectif d’apporter à la direction de projet les informations relatives à l’avancement
de l’exécution du projet, au respect de ses objectifs et de ses coûts.
Il consiste à :

- Apporter les éléments nécessaires au pilotage ;

- Gérer les délais ;
- Gérer les coûts ;
- Planifier les tâches ;
- Elaborer des tableaux de bord ;
- Evaluer le projet.

17
II.1.4 Étapes de réalisation d’un projet
II.1.4.1 Première étape : Définir l’envergure du projet

La définition du contenu du projet consiste à créer un plan de projet. D’une autre manière,
il s’agit d’établir le résultat final ou la mission du projet et de définir une liste de vérification du
projet qui comprend les éléments suivants [5] :

Les objectifs du projet : La description du contenu du projet a pour première étape

d’établir les objectifs en fonction des besoins du client.

Les livrables : Décrire les principaux livrables, soit les résultats prévus au cours de la durée
du projet. Sachant qu’un livrable est tout résultat, document, mesurable, tangible ou véritable
qui résulte de l’achèvement d’une partie du projet.
Exemple : Un cahier des charges et une étude de faisabilité sont des livrables.

Les jalons : Ils servent à mieux diviser les principales parties d’un travail. Aussi, ils four-
nissent la première estimation grossière en termes de temps, de coût et de ressources.

Les exigences techniques : Se sont imposées pour garantir une performance conforme aux
exigences du client.

Les limites et les exclusions : Les limites du contenu doivent être clairement établie afin
d’éviter la perte de ressources et de temps attribuable à une mauvaise analyse du problème.

La révision du contenu en compagnie du client : Elle correspond à la dernière étape

de la liste de vérification du contenu du projet.

II.1.4.2 Deuxième étape : Etablir les priorités du projet

La quantité et le succès d’un projet dépend de la capacité à répondre aux attentes des
clients, voire de les dépasser en ce qui concerne les coûts (budget), le temps et la performance
(contenu). Les rapports mutuels entre ces critères varient. Il s’avère parfois nécessaire de proposer
des compromis quant à la performance et au contenu du projet pour le terminer plus rapidement
ou pour en diminuer les coûts, car plus la durée du projet se prolonge, plus le coût sera plus
élevé.
Souvent le gestionnaire du projet devra faire un compromis en matière de temps, de coûts
et de performance, et pour ce faire, il doit déterminer et comprendre les priorités du projet.

18
II.1.4.3 Troisième étape : Créer une structure de découpage du projet

Une fois le contenu et les livrables sont déterminés, l’ensemble du projet peut être successive-
ment réparti en éléments de travail de plus en plus petits. Le résultat de ce processus hiérarchique
nous donne la structure de découpage du projet.

II.1.5 Structure de découpage du projet (Work Breakdown Structure

(WBS))
Le découpage de projet consiste à fractionner les livrables principaux en éléments plus petits,
mieux gérables jusqu’à un point tel que ces éléments livrables soient suffisamment maîtrisables,
ainsi établir une forme de contrôle du projet.

Figure II.3 – Structure de découpage d’un projet (WBS).

II.2 Problème d’ordonnancement de projet

Lors de tout projet de grande envergure (construction d’un bateau, d’un avion, d’un bâti-
ment,. . .), un problème crucial qui se pose est celui du calendrier d’exécution des tâches.
Le problème d’ordonnancement consiste à organiser dans le temps la réalisation des activités
d’un projet, compte tenu des contraintes temporelles (délais, contraintes d’enchainement, . . .)
et de contraintes portant sur l’utilisation et la disponibilité des ressources requises pour la réa-
lisation de ce projet.

Mathématiquement, c’est un problème d’optimisation sous contraintes. Il s’agit de déter-

miner à l’intérieur de l’ensemble des solutions réalisables (c’est-à-dire vérifiant les contraintes
du problème), un ordre de passage des tâches qui minimise une (ou parfois plusieurs) fonction
objectif donnée [4].

19
II.2.1 Tâche / Activité
Une tâche i est une entité élémentaire de travail localisé dans le temps par une date de début
ti et de fin t¯i , dont la réalisation est caractérisée par [7] :

- Une durée di (on a t¯i = ti + di ) ;

- rik : L’intensité avec laquelle la tâche i consomme un certain moyen ou ressource k.

Exemples :

- En construction : Pose des dalles, peinture, plomberie, . . ..

- En informatique : Exécution d’un programme, impression d’un document, . . ..
- En transport ferroviaire : Occupation d’une portion de voie par un train, . . ..

Donc, il n’y a pas de définition formelle d’une tâche, mais toute considération dépend de la
nature du domaine et du problème en question.
En ordonnancement de projet, nous conservons le terme tâche pour désigner les activités
constitutives d’un projet, l’ensemble des tâches est généralement noté I, le nombre de tâche par
N et chaque tâche est noté par i et elle est décrite par les caractéristique suivantes :

- La date de disponibilité de la tâche i (date de début au plus tôt) ;

- La date de début au plus tard de la tâche i ;
- La date de fin au plus tôt ;
- La date échue de la tâche i (date de fin au plus tard : deadline) ;
- ti : ”Date de début d’exécution de la tâche i” ;
- t¯i : ”Date de fin d’exécution de la tâche i” ;
- di : ”Durée d’exécution de la tâche i”.

Figure II.4 – Caractéristiques d’une tâche i.

20
II.2.2 Contraintes
Les problèmes d’ordonnancement sont rendus difficiles à cause des contraintes à respecter.
Nous pouvons distinguer plusieurs types d’entre elles :

Contraintes potentielles : Elles lient les tâches entre elles c’est-à-dire que telle opération
ne peut être exécutée avant telle autre.

Localisation temporelle : Une tâche donnée doit être terminée avant telle date, ou au
contraire son exécution ne doit pas commencer avant une date précise.

Contraintes de succession : Dans ces contraintes, l’exécution de la tâche j ne peut com-

mencer qu’une fois un ensemble de tâches prédéfinies est achevé.

Contraintes disjonctives (ou non partageables) : Ce type de contraintes est lié aux
ressources utilisées par les tâches, il apparaitra lorsque deux tâches, utilisant la même machine,
ne pourront pas s’exécuter simultanément.

Contraintes cumulatives (ou partageables) : Elles sont aussi liées aux ressources, elles
apparaissent par exemple lorsque trois processus sont disponibles pour l’exécution de quatre
tâches : On ne pourra exécuter plus de trois de ces tâches en même temps sans que l’on puisse
savoir à l’avance laquelle sera retardée [8].

II.2.3 Définition de l’ordonnancement

Ordonnancer un ensemble de tâches, c’est programmer leur exécution en leur allouant les
ressources requises et en fixant leurs dates de début.

Un ordonnancement constitue une solution au problème d’ordonnancement. Il d´ecrit l’exé-

cution des activités et l’allocation des ressources au cours du temps, satisfaisant les contraintes
et s’approchant au mieux des objectifs à atteindre.

21
II.2.4 Objectif de l’ordonnancement
Les objectifs des entreprises se sont diversifiés et le processus d’ordonnancement est devenu
de plus en plus multicritères. D’une manière générale, on distingue plusieurs classes d’objectifs
concernant un ordonnancement :

Les objectifs liés au temps : On trouve par exemple la minimisation du temps total
d’exécution, du temps moyen d’achèvement, des durées totales de réglage ou des retards par
rapport aux dates de livraison.

Les objectifs liés aux ressources : Maximiser la charge d’une ressource ou minimiser le
nombre de ressources nécessaires pour réaliser un ensemble de tâches sont des objectifs de ce type.

Les objectifs liés au coût : Ces objectifs sont généralement de minimiser les coûts de
lancement, de production, de stockage, de transport, etc.

II.3 Quelques concepts de la théorie des graphes

Les graphes sont actuellement l’outil privilégié pour modéliser des ensembles structurés com-
plexes. C’est une tentative de visualisation concrète des faits. Dans cette partie, nous allons
définir quelques concepts de la théorie des graphes qui nous seront utiles dans ce qui suit.

22
II.3.1 Définition d’un graphe
Un graphe orienté pondéré G est constitué de deux ensembles :

1. Un ensemble X d’éléments appelé sommets matérialisés par des points.

X = {x1 , x2 , . . . , xn }.
2. Un ensemble U de lignes (arcs) reliant chacune deux sommets.
U = {u1 , u2 , . . . , un }.

Un graphe est noté donc par : G = (X, U ). Si les lignes U sont orientées, on les appelle des
arcs et G prend le nom de ”graphe orienté pondéré”. Par contre, si elles ne sont pas orientées,
on obtient des arrêtes et G devient ”un graphe non orienté”.

II.3.2 Date au plus tôt

On appelle date au plus tôt d’une tâche j, notée par tj la date la plus hâtive à laquelle une
activité peut commencer. Il s’agit de l’achèvement au plus tôt le plus tardif de toutes les activités
qui la précèdent immédiatement. Les dates au plus tôt des différentes tâches s’obtiennent comme
suit :

t = 0
i
t = max(t + d )
j i ij telque j ̸= i

avec dij la durée de l’activité(i,j).

II.3.3 Date au plus tard

On appelle date au plus tard d’une tâche i, notée par ti l’ultime date à laquelle toutes les
activités antérieures à i doivent être réalisées de manière ne pas retarder le projet.

T = t
N N
t̄ = min(t̄ + d );
j i ij

II.3.4 Tâche critique

Une tâche critique est une tâche dont les dates de début au plus tôt et au plus tard coïncident.
Tout retard sur les tâches critiques retarde la fin des travaux.

23
II.3.5 Chemin critique
C’est le plus long chemin du sommet ”début” au sommet ”fin”. Il est constitué des arêtes
associées à des tâches critiques. Il n’est pas nécessairement unique.

II.3.6 Marges
Elle est définie pour chaque tâche, comme la différence entre sa date de début au plus tard
et sa date de début au plus tôt. On distingue les marges suivantes :

Marge totale : La marge totale sur une tâche est le retard que l’on peut prendre dans la
réalisation de cette tâche sans retarder l’ensemble du projet. Elle est obtenue, en faisant pour
chaque tâche, la différence entre la date au plus tard de début d’une tâche et la date au plus
tôt. Les tâches critiques sont donc les tâches de marge totale nulle.

Marge libre : La marge libre sur une tâche est le retard que l’on peut prendre dans la
réalisation d’une tâche sans retarder la date de début au plus tôt de tout autre tâche qui suit.

Conclusion
Nous venons de voir dans ce chapitre la gestion de projet avec ses différentes étapes. Ensuite
nous avons situé la phase ordonnancement dans le cycle de vie d’un projet.

24
 III

Techniques d’ordonnancement

La modélisation méthématique est une traduction d’une observation dans le but de lui ap-
pliquer les outils, les techniques et les théories mathématiques. C’est une étape cruciale pour
l’étude de n’importe quel problème en recherche opérationnelle. Dans ce chapitre, nous étudions
les techniques de modélisation et les méthodes d’ordonnancement de projet.
La modélisation des problèmes d’ordonnancement de projet nécessite la connaissance de
quelques concepts de base de la théorie des graphes et de la programmation linéaire que nous
tâchons de présenter au cours de ce chapitre.

III.1 Le diagramme de GANTT

Le graphique de GANTT n’est pas une méthode pour résoudre les problèmes d’ordonnance-
ment mais seulement une méthode pour représenter une solution. Il s’agit d’un outil élaboré en
1917 par Henry L. GANTT permettant de modéliser la planification des tâches et représenter
graphiquement l’avancement du projet. Son principe est de représenter au sein d’un tableau, en
ligne les différentes tâches et en colonne les unités de temps (exprimées en mois, semaines, jours,
heures . . .). Cette méthode est actuellement intégrée dans tous les logiciels de planification de
projets (MS Project, Gantt Project . . .).

Ses différentes étapes de réalisation sont les suivantes :

- Définir les relations d’antériorité entre tâches ;

- Représenter les tâches par des traits dans le diagramme : d’abord les tâches n’ayant aucune
antériorité, puis celles dont les tâches antérieures ont déjà été représentées, et ainsi de suite ;

25
 - Evaluer la solution : représentation de la progression réelle du travail par un trait en
pointillé parallèle à la tâche planifiée.

Le diagramme de Gantt permet de visualiser dans le temps les diverses activités liées com-
posant un projet. Il permet de représenter graphiquement l’avancement du projet. Le concept a
été développé par Henry L. GANTT , ingénieur américain, vers 1910.

Exemple : Réalisation d’une construction.

Code Désignation Durée Antériorités immédiates

A Etablissement des plans 4 -
B Terrassement 5 -
C Creuser les fonds de piliers 6 -
D Faire les fonds de peliers 3 A,B,C
E Plassement arrivée et évacuation assainissenment 7 A,B,C
F Dalle 5 A,B,C
G Cloisonnage 8 D,E
H Carrelage 6 D,E
I Plomberie 5 F
J Installation chauffage 3 F
K Electricité 5 G,H,I,J
L Pose faïence 2 G,H,I,J
M Boiserie 1 K,L
N Peinture 4 K,L

Table III.1 – Table initiale d’ordonnancement T.

Figure III.1 – Diagramme de GANTT de la table d’ordonnancement T.

26
III.2 La méthode du Potentiel-Metra MPM
La méthode des potentiels a été développée vers la fin des années 50 parallèlement à la
méthode PERT (voir III.3). Dans cette méthode, le problème est représenté sous forme d’un
graphe tel que les tâches sont représentées par des noeuds et les contraintes de succession par
des arcs, son principe est le suivant :
- À chaque noeud sont associées une date de début au plus tôt et une date de fin au plus
tard ;
- À chaque arc est associé un délai d’attente entre les tâches. La date de début au plus tôt
d’une tâche dépend de la date de fin des tâches qui la précèdent ;
- La tâche DEBUT est initialisée avec une date de début au plus tôt égale à zéro.
Cette méthode permet de déterminer la date de réalisation d’un projet ainsi que la date de
début et de afin de chaque tâche, mais elle est incapable de résoudre des problèmes qui prennent
en compte plus de contraintes telles que l’incertitude et les coûts d’exécution des tâches.

III.3 La méthode PERT

La méthode PERT (Program Evaluation and Review Technique) s’est développée, parallèle-
ment à la méthode du potentiel, aux Etats-Unis en 1958 pour la planification de la construction
de la fusée Polaris. Elle se distingue de la méthode du potentiel par le fait que les tâches ne
sont plus associées aux noeuds mais plutôt aux arcs du réseau. Le modèle PERT fait intervenir
les étapes du projet et son but principal est l’étude finale de la réalisation. La méthode PERT
cherche donc à déterminer la chronologie des tâches dans le temps en déterminant la date de
début, la date de fin et les marges de chaque tâche par rapport au projet. Et ceci, en prenant
en compte les contraintes de précédences, de délai, et une date au plus tôt et au plus tard de
chaque tâche. Ainsi, cette méthode permet d’identifier les tâches critiques ce qui permet donc
d’estimer une durée minimale d’un projet.

La méthode PERT est une technique qui s’appuie essentiellement sur la construction d’un
graphe R = (X; U ; D) orienté, sans boucle défini comme suit :

- X : l’ensemble des sommets qui représentent les étapes de la réalisation du projet tels que :
X = {1, . . . , N } ;
- U : l’ensemble des arcs qui représentent toutes les tâches du projet ; avec
U = {(i, j) ∈ X 2 /i ̸= j, i < j}, |U | ≤ N − 1 ;
- D : l’ensemble des poids des arcs, i.e. D = {dij ∈ R+ , (i, j) ∈ X 2 }

27
 Exemple :

Tâche Tâche 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

Table III.2 – Tableau des tâches.

III.3.1 Construction du graphe PERT

La méthode commence par la construction d’un graphe, appelé graphe PERT, à partir de
l’échéancier. Ce graphe sera un graphe valué 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.

Figure III.2 – Le graphe PERT associé.

28
III.3.2 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.

- a) 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, grace à l’algorithme de Ford de recherche du chemin le plus long. Ainsi : t1 = 0
et tj = max(ti + dij ) sur tous les i précédant j avec dj = durée de la tâche ij.
Dans l’exemple t1 = 0 ; t2 = 0 + 6 = 6 ; t3 = 0 + 5 = 5 ; t4 = 6 + 4 = 10 ; t5 =
max(6 + 0; 5 + 6) = 11 ; t6 = max(11 + 6; 10 + 5) = 17 ; t7 = 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, t7 = 21, le projet durera donc au mieux 21 jours).

- b) Dates au plus tard : Pour un sommet, la date au plus tard (notée : T ) représente
coneré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 :
Tn = tn =durée du projet et Ti = min(Tj ..dij ) sur tous les j suivant i : Dans l’exemple
T7 = 21 ; T6 = 21..4 = 17 ; T5 = 17..6 = 11 ; T4 = 17..5 = 12 ; T3 = 11..6 = 5 ;
T2 = min(11..0; 12..4) = 8 ; T1 = min(8..6; 5..5) = 0.
On aura toujours t1 = T1 = 0 et t inférieur ou égal à T pour tout sommet. On appelle
T − t la marge de flottement du sommet.

- c) 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 :

M Lij = tj − ti − dij et M Tij = Tj − ti − dij

29
 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âche A B C D E F G
ML 0 0 0 0 2 0 0
MT 2 0 2 0 2 0 0

Table III.3 – Les marges libres et les marges totales.

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).

III.4 Méthodes de résolution du problème

Les méthodes de résolution des problèmes d’optimisation combinatoire (d’ordonnancement)
prennent en considération deux facteurs : la qualité des solutions et le temps de résolution. Ainsi
elles peuvent être classées en deux catégories : les méthodes exactes qui garantissent l’optimalité
mais avec un temps de calcul très grand, et les méthodes approchées qui peuvent perdre en
optimalité pour gagner en temps d’exécution.

III.4.1 Les méthodes exactes

On peut définir une méthode exacte comme une méthode qui garantit l’obtention de la
solution optimale pour un problème d’optimisation . L’utilisation de ces méthodes s’avère par-
ticulièrement intéressante, mais elles sont souvent limitées au cas des problèmes de petite taille.

Les algorithmes exactes les plus réussis dans la littérature appartiennent aux paradigmes de
quatre grandes classes :

- La programmation dynamique ;
- La programmation linéaire ;
- Méthode du simplexe.

30
1. La programmation dynamique

Elle se base sur le principe de Bellman (1954) : ” Si C est un point qui appartient au
chemin optimal entre A et B, alors la portion de ce même chemin allant de A à C est le
chemin optimal entre A et C ”. C’est une méthode qui consiste donc à construire d’abord
les sous-chemins optimaux et ensuite par récurrence le chemin optimal pour le problème
entier. Cette méthode est destinée à résoudre des problèmes d’optimisation à vocation plus
générale que la méthode de séparation et d’évaluation (branch and bound) sans permettre
pour autant d’aborder des problèmes de tailles importantes.
2. Modélisation d’un problème d’ordonnancement par la programmation linéaire

On s’appuie sur un graphe des précédences (ou grpahe de projet) G = (X; U ) détini par
l’ensemble des tâches X et l’ensemble des arcs U (l’arc (i; j)) signifie que la tâche i précède
la tâche j). Il est facile de constuire ce graphe à partir des listes de prédécesseurs du tableau
qui liste les activités et leurs relations de précédence.
Le projet est composé d’un ensemble de tâches pour lesquelles on dispose des informations
suivantes :

- Chaque tâche a une durée di supposée connue avec certitude ;

- Ces tâches sont liées entre elles par des contraintes de succession ;
- Les tâches peuvent être affectées de contraintes de localisation temporelle : par
exemple, date du début imposée pour une tâche.

a. Les variables de décision

On veut déterminer pour chaque tâche la date à laquelle elle doit débuter. Nous avons
n tâches à exécuter, indicées i = 1, . . . , n. On adoptera dans toute la suite la notation
di , qui désigne la durée d’exécution de la tâche i, On associe à chaque tâche i ∈ X
une variable de décision ti , représentant sa date de début.
On introduit deux tâches fictives : α représentant le début des travaux et ω repré-
sente la fin des travaux. Ces deux tâches ont une durée nulle. La date de début des
travaux correspond à t. On prend, tα = 0, c’est-d-dire que l’origine du temps est fixée
à la date de début des travaux. La date de fin des travaux sera mesurée par tω , date
d’exécution de la tâche fictive ω : Tous les ti ≥ 0.

b. Les contraintes
Il s’agit de respecter un certain nombre de contraintes portant sur les dates de début
des tâches. On peut prendre les contraintes suivantes :

31
 • Contraintes de successions : La tâche j ne peut commencer avant la fin de
i.

tj ≥ ti + di

• Contraintes de successions partielles : La tâche j peut commencer dès

qu’un pourcentage pi de la tâche i est exécuté.

tj ≥ ti + pi di

• Contraintes de successions immédiates : La tâche j doit commencer dés

que i est terminée.

tj = ti + di

• Date de disponibilité : La tâche i ne peut commencer avant la date ri .

tj ≥ ri soit tj ≥ tα + ri (tα = 0)

• Date de livraison : La tâche i doit être terminée avant la date li .

tj + di ≥ li soit tα ≥ ti + di − li

Tels que i, j ∈ T
c. La fonction objectif
ω représente la tâche "fin" du projet, le critère peut être traduit par :

min tω

d. Le modèle mathématique




min f (t) = tω





S.c :




tj ≥ ti + di





 tj ≥ ti + pi di



 tj = ti + di
tj ≥ tα + ri





tj + di ≥ li




tα ; tω ≥ 0





i∈X




32
 3. Méthode du simplexe

La méthode du simplexe est la plus simple pour la recherche du minimum d’une fonction
linéaire sous contraintes. On sait que les contraintes linéaires impliquent que les solutions
admissibles du problème d’optimisation sont à l’intérieur d’un simplexe. Une solution opti-
male est nécessairement située sur un sommet du simplexe. On recherche alors une solution
optimale en minimisant notre fonction en se "promenant" sur les bords du simplexe. Cette
méthode donne de bons resultats mais peut nécessiter un temps de recherche très long. Des
méthodes dites de points intérieurs plus rapides sont préférées. Elles sont plus complexes.
Il ne s’agit plus de rechercher notre solution optimale en parcourant les bords du simplexe
mais en le traversant [9].

Conclusion
À Chaque problématique est associée une modélisation, et pour chaque modélisation il existe
une ou plusieurs approches de résolution appropriées. Nous venons de voir dans ce chapitre les
techniques de modélisation et de résolution par le diagramme de Gantt, l’approche de la théorie
des graphes, et l’approche de la programmation linéaire.

33
 IV

Modelisation et résolution du
problème

Introduction
L’objectif de ce chapitre est de présenter les différentes manièrer de modéliser notre problème,
et les approches de résolution appliquées. Dans la première partie, nous présentons le projet de
réhabilitation et de mise en service de rénovation de la base de vie BBM-Bordj Menaïel. Dans
la seconde partie, nous appliquons les approches de modélisation et de résolution.

IV.1 Présentation générale du projet

Notre travail de recherche porte sur le projet intitulé « Rénovation de la Base de vie BBM
Bordj-Menaïel (Wilaya de Boumerdes) » qui a pour but principal l’aménagement de la base
existante et d’en réparer toutes les dégradations, les modifications et les rectifications observées
sur les bâtisses existantes, et d’y construire des nouveaux ouvrages. Cet aménagement apportera
une modernisation au point de vue aspect architectural et une amélioration dans les conditions
de travail et de vie du personnel du Terminal BORDJ MENAÏEL de Sonatrach.

34
 Figure IV.1 – Situation géographique de la Base de vie BBM.

IV.1.1 Les caractères du projet

• Titre du projet : Rénovation de la Base de vie BBM Bordj- Menaïel ([Link]).
• Maitre d’ouvrage : la société nationale pour la recherche, la production, le transport
et la commercialisation des hydrocarbures, dénommée SONATRACH – Transport par
Canalisation – Région Transport Centre Bejaïa.
• Maitre d’œuvre : Entreprise de Travaux de Bâtiment et Hydraulique Tout Corps d’Etat
ETB/TCE Smail ARHAB.
• Durée contractuelle : 28 mois comportant (12 mois de garantie inclus).
• Durée d’exécution : 18 mois.
• Montant du contrat : Vingt-quatre Millions Quatorze Mille Six Cent Cinq Dinars Al-
gériens en hors TVA (24014605,00 DA H/TVA).
• Lieu : Bordj-Menaïel, Wilaya de Boumerdes, Algérie.
• Date de signature du contrat : 09 juillet 2019.
• Date d’ordre de service (ODS) : 28 juillet 2019.
• Les plans et les dossiers techniques du projet ont été élaborés par le bureau d’étude
AXXAM qui a été suivi et dirigé par le département TNF.

35
IV.1.2 Description des ouvrages
a) Etat existant :

La base de Bordj-Ménaiel qu’il y a lieu de restaurer est composée de :

• Un pavillon situé à l’entrée de la station (bâtisse chef de station) composé de deux bureaux,
hall de réception et un sanitaire servant de bureau pour le chef du centre.
• Un hangar abritant un bloc administratif (bureaux, infirmerie et sanitaires), cuisine et
réfectoire. Magasin (atelier instrumentation), atelier entretien, sanitaires, aire lavage avec
fosse, atelier sécurité et magasin pièces de rechanges.
• Un bâtiment en R+1 composé d’un poste de garde au RDC et d’une salle de contrôle
(ancienne) au premier étage.
• Un bâtiment technique (Salle TELECOM au RDC et la nouvelle salle de contrôle en
premier étage).
• Trois (03) villas servant pour hébergement.
• Un château d’eau.

a) Etat projeté :

Les travaux de rénovation de la base de Bordj-Ménaiel doivent porter essentiellement sur :

Les travaux de démolitions et déposes :

• La dépose des installations et des appareils sanitaires de plomberie bâtisse chef de station,
salle de contrôle (ancienne), bloc technique, l’administration et des villas,
• La dépose de la toiture du hangar,
• La dépose des menuiseries bâtisse chef de station (fenêtres et porte d’entrée), salle de
contrôle (ancienne), de l’administration, du bloc technique et des villas,
• La dépose des revêtements des sanitaires bâtisse chef de station, salle de contrôle (an-
cienne), de l’administration, bloc technique et des villas,
• La dépose de revêtement horizontal et vertical de cuisine et réfectoire,
• La dépose de trois citernes d’eau y compris supports en élévation,
• La dépose d’un escalier métallique menant vers la soupente,
• La démolition des quais de chargement,
• La démolition de la décharge pour déchets base,
• La démolition de baraques de chantiers,
• La dépose des bordures.

36
Les travaux d’aménagement :

• L’aménagement des bureaux administratifs (RDC et soupente),

• L’aménagement bâtisse chef de station,
• L’aménagement du bloc technique,
• L’aménagement des villas.

Les travaux de ravalement et de restauration :

• La restauration de la cuisine et du réfectoire,

• La restauration des sanitaires,
• La restauration du hangar,
• La restauration de la fosse de vidange,
• La restauration en peinture pour l’ensemble de la base,
• La restauration des évacuations des eaux pluviales,
• La restauration des évacuations des eaux usées,
• La restauration de l’électricité générale.

Les travaux des ouvrages neufs :

• Réalisation des structures en béton pour escalier de la soupente,

• Réalisation de la maçonnerie et des enduits pour hangar et décharges des ordures base,
• Réalisation des revêtements pour décharges des ordures,
• Fourniture et pose de climatiseurs pour bureaux bâtisse chef de station, administration et
bureaux salle de contrôle (ancienne),
• Réalisation des abris véhicules en charpente métallique de 10 et 04 places,
• Réalisation d’une plate-forme en béton armé pour engins,
• Réalisation de l’abri pour citerne gaz propaneet l’abri groupe électrogène,
• Fourniture et pose ferronnerie et rideaux pour garages,
• Fourniture et pose ferronnerie des portails avec portillon pour réfectoire et atelier,
• Fourniture et pose ferronnerie (porte) pour magasin pièces de rechange, portillon pour
base hébergement,

37
IV.2 Décomposition du projet
Après l’étude du projet de la Rénovation de la Base de vie BBM Bordj- Menaïel ([Link]),
nous pouvons le décomposer en 27 tâches principales :

Code Tâches
1 Dépose et démolition / transport
2 Terrassement
3 Béton pour infrastructure
4 Dallage
5 Béton pour superstructure
6 Maçonnerie en brique rouge/parpaings
7 Enduits
8 Revêtement horizontaux
9 Revêtement verticaux
10 Revêtement escaliers
11 Scellement
12 Béton pour menus ouvrage
13 Menuiserie aluminium
14 Menuiserie bois
15 Appareillage électrique
16 Câblerie, gaines, filerie
17 Appareillage sanitaire
18 Robinetterie accessoires
19 F/P de ferronnerie
20 Peinture
21 Vitrerie
22 F/P de climatisation
23 F/P abris véhicule et abris gaz
24 Réseau DEP et assainissement extérieur
25 Assainissement
26 Allés et espaces vert
27 Remise en état des lieux

Table IV.1 – Liste des tâches.

38
IV.3 Détermination de la durée des tâches

Numéro de la tâche Durée (jours)

1 10
2 20
3 50
4 10
5 60
6 08
7 07
8 60
9 60
10 60
11 20
12 10
13 20
14 10
15 45
16 75
17 60
18 30
19 75
20 50
21 27
22 60
23 165
24 60
25 46
26 45
27 60

Table IV.2 – Liste des tâches et leurs durées.

La durée totale du projet est de 540 jours.

39
IV.4 Résolution par la méthode PERT
Le tableau ci-après résume les données de note projet.

IV.4.1 Les données

Tâches Désignation Durée (jours) Antériorités

1 Dépose et démolition / transport 10 -
2 Terrassement 20 -
3 Béton pour infrastructure 50 2
4 Dallage 10 3
5 Béton pour superstructure 60 4
6 Maçonnerie en brique rouge/parpaings 08 5
7 Enduits 07 6
8 Revêtement horizontaux 60 2
9 Revêtement verticaux 60 8
10 Revêtement escaliers 60 9
11 Scellement 20 2
12 Béton pour menus ouvrage 10 11
13 Menuiserie aluminium 20 5,10
14 Menuiserie bois 10 13
15 Appareillage électrique 45 6
16 Câblerie, gaines, filerie 75 15
17 Appareillage sanitaire 60 5
18 Robinetterie accessoires 30 17
19 F/P de ferronnerie 75 16
20 Peinture 50 10
21 Vitrerie 27 20
22 F/P de climatisation 60 14
23 F/P abris véhicule et abris gaz 165 3
24 Réseau DEP et assainissement extérieur 60 21
25 Assainissement 6 24
26 Allés et espaces vert 45 25
27 Remise en état des lieux 60 1, 7, 12, 18, 19, 22, 23, 26

Table IV.3 – Tableau des activités de projet.

40
IV.4.2 Construction de réseau PERT
Dans un graphe potentiel-étape, on associe un graphe G=(X, U) au problème d’ordonnan-
cement :
Les tâches sont représentées par des arcs dans un réseau.
Les extrémités de ces arcs sont des événements qui matérialisent soit le début soit la fin d’une
opération donnée.
Les arcs, soient des tâches réelles, soient des tâches fictives permettant de représenter certaines
contraintes potentielles.

Figure IV.2 – Réseau PERT

41
IV.4.3 Détermination des dates et des marges par rapport à la table
IV.3

Tâches Durée Antériorités Date au Date au ML MT

(jours) plus tôt plus tard
1 10 - 10 488 0 478
2 20 - 20 20 0 0
3 50 2 70 215 0 145
4 10 3 80 225 0 145
5 60 4 140 285 0 145
6 08 5 148 293 0 145
7 07 6 155 488 0 333
8 60 2 80 80 0 0
9 60 8 140 140 0 0
10 60 9 200 200 0 0
11 20 2 20 478 0 438
12 10 11 50 488 0 438
13 20 5,10 160 4185 0 258
14 10 13 170 428 0 258
15 45 6 193 338 0 145
16 75 15 268 413 0 145
17 60 5 200 458 0 258
18 30 17 230 488 0 258
19 75 16 343 488 0 145
20 50 10 250 250 0 0
21 27 20 277 277 0 0
22 60 14 230 488 0 258
23 165 3 235 488 0 253
24 60 21 337 337 0 0
25 46 24 383 383 0 0
26 45 25 428 428 0 0
27 60 1, 7, 12, 18, 488 488 0 0
19, 22, 23, 26

Table IV.4 – Des dates et des marges par rapport à la table IV.3

42
IV.4.4 Le chemin critique
Le chemin critique dans les deux réseaux est le plus long chemin du début jusqu’à la fin, sa
valeur est la durée minimale du projet.
Dans notre cas, on a obtenu le chemin critique suivant :

2 → 8 → 9 → 10 → 20 → 21 → 24 → 25 → 26 → 27

IV.4.5 Résultat
Après application de la méthode PERT et MPM nous avons pu optimiser la durée totale de
réalisation de notre projet de 52 jours en jours ouvrés.

La durée minimale du projet est 488 jours en jours ouvrés.

IV.5 Utilisation du diagramme de GANTT

Le diagramme de GANTT, couramment utilisé en gestion de projet, est l’un des outils les
plus efficaces pour représenter visuellement l’état d’avancement des différentes activités (taches)
qui constituent un projet.

La colonne de gauche du diagramme énumère toutes les taches à effectuer, tandis que les
lignes d’entête représente les unités de temps les plus adaptées au projet (jours, semaines, moi
etc.)Chaque tache est matérialisée par une barre horizontale, dont la position et la longueur
représentent la date de début, la durée et la date de fin.

Afin de représenter le diagramme de GANTT représentant notre projet nous avons utilisé le
logiciel Ms Project 2003.

IV.6 Utilisation du logiciel Ms Project 2016

IV.6.1 Définir la date de début du projet

On accède au paramétrage de la date de début du projet par le menu déroulant projet =⇒
Information sur le projet.

43
IV.6.2 Paramètre le calendrier du projet
Lorsque on crée un nouveau projet, Ms Project lui affecte un calendrier appelé "calendrier
standard".

Les paramétrages de ce calendrier (horaires de travail, jours fériés. . .) sont ceux par défaut,
il nous appartient de personnaliser ce calendrier en fonction des spécifiés de notre projet.

Figure IV.3 – La date de début du projet.

Figure IV.4 – La date de début du projet.

44
IV.6.3 Définir la semaine de travail
On accède aux paramétrages de calendrier par outils modifier le temps de travail dans la
boite de dialogue qui s’ouvre alors, un onglet est dédie au réglage de la semaine de travail.

Figure IV.5 – Les options de calendrier.

45
IV.6.4 Créer des tâches et leurs durées dans l’affichage GANTT
Il faut saisir une valeur sur une ligne du tableau et une tâche est crée.

Figure IV.6 – La liste des tâches.

46
IV.6.5 Créer des liens d’antériorité
Un des principes de base de l’ordonnancement de projet consiste a organiser la succession
des taches en fonction de règle d’antériorité.

Figure IV.7 – Les liens d’antériorité.

47
IV.6.6 Afficher le diagramme de GANTT

Figure IV.8 – Le diagramme de GANTT.

48
IV.6.7 Affichage du chemin critique

Figure IV.9 – Le chemin critique.

Remarque : dans ce diagramme de GANTT obtenu, les tâches critiques sont représentées
par la couleur rouge, tandis que les tâches non critiques sont représentées par la couleur bleu.

49
IV.7 Résolution par la programmation linéaire

IV.7.1 Les données du problème

- Soit T un ensemble de tâche (phases de la réalisation du projet).
- Soit di une durée pour chacune d’elles.
- On a pour chaque tâche un prédécesseur.

IV.7.2 Les variables de décision

Soit ti une variables de décision i ∈ t, tel que t = {0..27}. On introduit deux tâches fictives :
α représente le début des travaux et ω représente la fin des travaux. Ces deux tâches ont une
durée nulle.

On prend t = 0, c’est-à-dire que l’origine du temps est fixée à la date de début des travaux.

La date de fin des travaux sera mesurée par tω , date d’éxécution de la tache fictive ω.

Si tα = t0 = 0, tω = t28 représente aussi la durée des travaux avec :

IV.7.3 La fonction objective

Z représente la tâche "fin" du projet le critère peut être traduit par :

min Z = t28 − t0

50
IV.7.4 Les contraintes de décision
IV.7.4.1 Les contraintes de successions

t1 − t0 ≥ 0
t2 − t0 ≥ 0
t3 − t2 ≥ 20
t4 − t3 ≥ 50
t5 − t4 ≥ 10
t6 − t5 ≥ 60
t7 − t6 ≥ 8
t8 − t2 ≥ 20
t9 − t8 ≥ 60
t10 − t9 ≥ 60
t11 − t2 ≥ 20
t12 − t11 ≥ 20
t13 − t2 ≥ 60
t13 − t10 ≥ 60
t14 − t13 ≥ 20
t15 − t6 ≥ 8
t16 − t15 ≥ 45
t17 − t5 ≥ 60
t18 − t17 ≥ 60
t19 − t16 ≥ 75
t20 − t10 ≥ 60
t21 − t20 ≥ 50
t22 − t14 ≥ 10
t23 − t3 ≥ 50
t24 − t21 ≥ 27
t25 − t24 ≥ 60
t26 − t25 ≥ 46
t27 − t26 ≥ 45
t27 − t23 ≥ 165
t27 − t22 ≥ 60
t27 − t19 ≥ 75
t27 − t18 ≥ 30
t27 − t12 ≥ 10
t27 − t7 ≥ 7
t27 − t1 ≥ 10
t28 − t27 ≥ 60

51
IV.7.5 Le modèle mathématique

min Z = t28 − t0
Sous contraintes :
t0 ≥ 0t1 − t0 ≥ 0
t2 − t0 ≥ 0
t3 − t2 ≥ 20
t4 − t3 ≥ 50
t5 − t4 ≥ 10
t6 − t5 ≥ 60
t7 − t6 ≥ 8
t8 − t2 ≥ 20
t9 − t8 ≥ 60
t10 − t9 ≥ 60
t11 − t2 ≥ 20
t12 − t11 ≥ 20
t13 − t2 ≥ 60
t13 − t10 ≥ 60
t14 − t13 ≥ 20
t15 − t6 ≥ 8
t16 − t15 ≥ 45
t17 − t5 ≥ 60
t18 − t17 ≥ 60
t19 − t16 ≥ 75
t20 − t10 ≥ 60
t21 − t20 ≥ 50
t22 − t14 ≥ 10
t23 − t3 ≥ 50
t24 − t21 ≥ 27
t25 − t24 ≥ 60
t26 − t25 ≥ 46
t27 − t26 ≥ 45
t27 − t23 ≥ 165
t27 − t22 ≥ 60
t27 − t19 ≥ 75
t27 − t18 ≥ 30
t27 − t12 ≥ 10
t27 − t7 ≥ 7
t27 − t1 ≥ 10
t28 − t27 ≥ 60
i ∈ t; t = 0, 1, 2, . . . , 28.

52
IV.7.6 Application avec la méthode du simplexe
Notre problème comporte 36 contraintes et 29 variables et pour résoudre ce problème de
simplexe on a utilisé le logiciel Microsoft Excel.

Figure IV.10 – Les données.

53
Figure IV.11 – Exécution.

54
 Après l’exécution on a obtenu le résulta suivant :

Figure IV.12 – Résultat.

Nous avons obtenu le meme résultat obtenu dans les partie précédente , nous avons trouvé
que la durée minimale du projet est 488 jours en jours ouvrés. Ce résultat est obtenu après 3
itérations de la méthode simplexe.

55
 Conclusion générale

Les problèmes d’ordonnancement de projet figurent au rang des problèmes d’ordonnance-

ment les plus étudiés depuis les origines de la théorie de l’ordonnancement. Malgré les nombreux
progrès réalisés par la suite, ces problèmes, en dépit de leur simplicité apparente, constituent un
challenge pour la recherche opérationnelle actuelle.

Depuis leur début d’utilisation vers la fin des années 50, PERT et MPM ont été employées
intensivement pour aider les chefs de projet dans la planification, la programmation, et le com-
mandement de leurs projets. Avec le temps, ces deux techniques graduellement ont bénéficié des
avantages des unes et des autres.

Dans ce mémoire nous avons présenté différentes phases d’élaboration d’un projet. Nous
avons étudié en détails le problème central de l’ordonnancement sous ses différents aspects :
modèles, méthodes et outils de calculs.

Nous avons modélisé et résolu le problème de minimisation du délai de réalisation du projet

de la réhabilitation de la base de vie BM en utilisant la technique du diagramme de Gantt. Nous
avons également modélisé notre problème d’ordonnancement sous forme de programme linéaire
que nous avons résolu à l’aide du logiciel Excel .

56
 En présence de contraintes de ressources, l’ordonnancement devient essentiellement difficile
et les méthodes de résolution par le chemin critique s’avérent donc inadaptées. Dans cette situa-
tion, nous avons eu recours aux fonctionnalités du logiciel Ms project pour le nivellement de
ressources.

l’étude menée sur le problème soulevé, nous a permis d’avoir une solution optimisée et moins
couteuse.

comme perspective, nous allons réaliser l’étude comparative entre les méthode utilisées. .

57
 Bibliographie

[1] M. Aidene, et [Link]. Recherche opérationnelle ( Programmation linéaire), Edition

Bleues, 2005.
[2] T.H. Nguyen. Contribution à la planification de projet : Proposition d’un modèle d’évaluation
des scénarios de risque-projet (2011). Thèse de doctorat, Université de Toulouse, septembre
2011.
[3] R. Aïm. Les fondamentaux de la gestion de projet. Afnor éditions, 2011
[4] N. Mahfouf, [Link]. Planification et ordonnancement d’un projet à moyens limitées au
sein de l’engtp. Master’s thesis, 2016/2017.
[5] [Link], and [Link]. Management de projet, dunod, paris ed. 2007.
[6] É.Taillard, and [Link]. Métaheuristiques pour l’optimisation difficile. Paris, septembre 2003.
[7] N. Nassereddine Algorithmes de construction de graphes dans les problèmes d’ordonnance-
ment de projet. Thèse de doctorat, Université Farhat Abbas-Setif, 2011.
[8] K. Mesghouni, Application des algorithmes évolutionnistes dans les problèmes d’optimisation
en ordonnancement de la production. PhD [Link]
[9] G.B. Dantzig, Origins of the simplex method. In G. Nash, éditeur, A History of Scientific
Computing, ACM Press Hist. Ser., pages 141.151. ACM Press, Reading, MA, 1990.
[10] M. Palpant. Recherche exacte et approchée en optimisation combinatoire : schémas
[Link]égration et applications. Thése de doctorat, Universite [Link], 2005.
[11] C. Reeves. Modern Heuristic Techniques for Combinatorial Problems. Advances topics in
computer science. Mc Graw-Hill, 1995.

58
 Résumé

Ce mémoire traite une problématique rencontrée en entreprise, il s’agit de trouver un ordon-

nancement des tâches pour le projet de renovtion de la base de vie Bordj Menaiel, en minimisant
son délai de réalisation. Nous avons utilisé la technique du diagramme de Gantt et la méthode
PERT. Ces méthodes se basent sur les graphes pour la modélisation et la résolution. Pour cette
dernière, nous avons calculé le plus long chemin qui représente la plus longue série de tâches,
dont la durée totale représente la durée minimale du projet. Nous avons également modélisé
le problème sous forme de programme linéaire à variables bornées, que nous avons résolu par
la méthode du simplexe en utilisant le logiciel Excel, vu la grande taille de nos données. Nous
avons pu minimiser la durée totale du projet en résolvant le problème d’ordonnancement sous
contraintes d’antériorités et de localisation temporelles. Cependant, les problèmes d’ordonnance-
ment dans la pratique impliquent la prise en compte du nombre limité de ressources. Pour cela,
nous avons utilisé le logiciel Ms project pour l’affectation de ressources necéssaires aux tâches,
et pour la résolution de la surutilisation de ces dernières.
Mots clés : Ordonnancement des tâches, gestion de projet, planification de projet, théorie
des graphes, programmation linéaire.

Abstract

This dissertation deals with a problem encountered in business, it is a question of finding a

scheduling of tasks for the renovation project of the Bordj Menaiel living base, by minimizing
its achievement. We used the Gantt chart technique and the PERT method. These methods are
based on graphs for modeling and resolution. For the latter, we have calculated the longest path
which represents the longest series of tasks, including the total duration represents the minimum
duration of the project. We also modeled the problem as a linear program with bounded variables,
which we solved by the simplex method using Excel software, given the large size of our data. We
were able to minimize the total duration of the project by solving the scheduling problem under
constraints of anteriorities and temporal location. However, scheduling problems in practice
involve considering the number limited resources. For this, we used the Ms project software for
the allocation of resources necessary for the tasks, and for the resolution of the overuse of the
latter..
Key words : Scheduling tasks, project planning, project management, graph theory, linear
programming.

59