Optimisation des délais dans un système de planification et de gestion de la performance.

République Algérienne Démocratique et Populaire
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université des Sciences et de la Technologie Houari Boumediene

Faculté de Mathématiques

Département de Recherche Opérationnelle

Mémoire

En vue de l'obtention du Diplôme de MASTER
Recherche Opérationnelle, Management, Risque et Négociation
(ROMARIN)

Thème

Optimisation des délais dans un système

de planification et de gestion de la

performance

Présenté par: NEFRAOUI Aimen Encadré par: MOULAÏ Mustapha

CHEBBAB Abdesslem CHAIBLAINE Yacine

Soutenu le 18 juillet 2021, devant le jury composé de :

Présidente : AMROUCHE Salima, USTHB Rapporteur: MOULAÏ Mustapha, USTHB Examinatrice : MAACHOU Nacera, USTHB

Code Mémoire: 10/ROMARIN/2021

Remerciements

Nous remercions chaleureusement l'ensemble des enseignants du
département de mathématiques de l'USTHB, particulièrement, notre
encadreur monsieur le professeur MOULAÏ Mustapha de nous avoir
encadré, encouragé et surtout de ses conseils judicieux, sa
disponibilité et ses apports avantageux sur ce mémoire.

Nos remerciements vont aussi à monsieur CHAIBLAINE Yacine
pour ses efforts, son assistance, le partage de son savoir et le temps
qu'il nous a accordé.

Nous remercions également tout le personnel de la direction SPE -
SONATRACH et en particulier Mme LASKRI Karima qui n'a cessé
de nous orienter et nous encourager, pour son aide et son assistance
durant toute la période pour l'élaboration de notre mémoire de fin
d'études.

Et enfin, toute personne qui, d'une façon ou d'une autre, a contribué
à la réalisation de ce mémoire, trouve ici le témoignage de nos plus
vives gratitudes.

Dédicace

Je tiens à dédier ce mémoire:

À mon cher Père et ma chère Mère, en témoignage et en gratitude de
leurs dévouement, de leur soutien permanent durant toutes mes
années d'études, leurs sacrifices illimités, leurs réconfort moral, eux
qui ont consenti tant d'effort pour mon éducation, mon instruction
et pour me voir atteindre ce but, pour tout cela et pour ce qui ne
peut être dit, mes affections sans limite.

À ma chère soeur et cher frère pour leurs encouragements
permanents, et leur soutien moral.

À mon cher binôme NEFRAOUI Aimen et à toute sa famille.

À toute ma famille et mes amis pour leur soutien tout au long de
mon parcours universitaire et à tous ceux qui m'ont enseigné tout au
long de ma vie scolaire.

À vous tous un grand merci.

Abdesslem

Dédicace

C'est avec profonde gratitude et sincères mots, que je dédie ce
travail de fin d'études:

À ma chère mère, la lumière de mes jours, qui a oeuvré pour ma
réussite, par son amour, son soutien, tous les sacrifices consentis et
ses précieux conseils, reçois à travers ce travail aussi modeste soit-il,
l'expression de mes sentiments et de mon éternelle gratitude, que
Dieu te garde et te protège.

À mon cher père, l'épaule solide, qui m'a toujours soutenu et aidé à affronter les difficultés, qui a veillé tout au long de ma vie à ce que je n'eusse besoin de rien, celui qui s'est toujours sacrifié pour me voir réussir. Je prie dieu le tout puissant pour qu'il te protège et te donne

bonheur et prospérité.

À ma chère soeur et cher frère pour leurs encouragements
permanents, et leur soutien moral, je vous souhaite un avenir
radieux plein de réussite et que Dieu, le tout puissant, vous protège
et vous garde.

À mon cher binôme CHEBBAB Abdesslem et à toute sa famille.

À toute ma famille et mes amis pour leur soutien tout au long de
mon parcours scolaire.

Aimen

Table des matières

Introduction générale 1 Présentation de l'organisme d'accueil			1 3
	1.1	Introduction	3
	1.2	Historique de la SONATRACH	3
	1.3	Organisation de l'entreprise	4
		1.3.1 La Direction générale	4
		1.3.2 Structures fonctionnelles	5
		1.3.3 Activités de SONATRACH	5
	1.4	Missions de SONATRACH	8
	1.5	Présentation de la Direction d'accueil : La Direction SPE	8
		1.5.1 Organisation de la Direction SPE	8
		1.5.2 Missions de la Direction SPE	9
	1.6	Conclusion	9
2	Généralités sur la planification, l'ordonnancement et la performance		10
	2.1	Introduction	10
	2.2	La planification	10
		2.2.1 Définition	10
		2.2.2 Les différents types de planification	10
		2.2.3 Le processus de planification	11
		2.2.4 Les intérêts et les limites de la planification	12
	2.3	Notions générales sur les problèmes d'ordonnancement	12
		2.3.1 Définition d'ordonnancement	12

TABLE DES MATIÈRES

		2.3.2 Les tâches 2.3.3 Quelques définitions 2.3.4 Les ressources 2.3.5 Les contraintes	13 13 14 14
	2.4	La gestion de la performance	15
		2.4.1 Concepts sur la performance	15
		2.4.2 Les typologies de la performance	16
		2.4.3 La performance organisationnelle	16
		2.4.4 Les mesures de la performance	17
	2.5	L'impact de la planification sur la performance	18
	2.6	Conclusion	18
3	Les outils de modélisation et les méthodes de résolution		19
	3.1	Introduction	19
	3.2	Le diagramme de GANTT	19
	3.3	Modélisation par les graphes	21
		3.3.1 Notions de la théorie des graphes	21
		3.3.2 Les représentations graphiques	23
		3.3.3 La méthode PERT	24
		3.3.4 La Méthode des Potentiels Métra (MPM)	27
	3.4	Modélisation d'un problème d'ordonnancement par la PL	28
		3.4.1 Composants d'un problème d'optimisation linéaire	28
		3.4.2 Programmation linéaire en nombres entiers (PLNE)	29
	3.5	Conclusion	30
4	Modélisation du problème posé		31
	4.1	Introduction	31
	4.2	Problématique	31
	4.3	Formulation mathématique	33
		4.3.1 Les hypothèses	33
		4.3.2 Les indices	33
		4.3.3 Les notations	33
		4.3.4 Les paramètres	33

TABLE DES MATIÈRES

4.3.5 Les variables de décision 33

4.3.6 La fonction objectif 34

4.3.7 Les contraintes 34

4.3.8 Le modèle mathématique 35

4.3.9 Type du modèle 35

4.3.10 Taille du modèle 35

4.4 Méthodes de résolution des PL 36

4.4.1 Les Méthodes exactes 36

4.4.2 Les Méthodes approchées 37

4.5 La modélisation avec solveur CPLEX 39

4.5.1 Présentation du solveur CPLEX 39

4.5.2 Le modèle en CPLEX 39

4.6 Conclusion 40

5 Résolution du problème et implémentation 41

5.1 Introduction 41

5.2 Présentation de MATLAB 41

5.2.1 Pourquoi opter pour MATLAB? 42

5.3 Collecte des données 42

5.3.1 Décomposition du système 42

5.3.2 Détermination de la durée des tâches 44

5.4 Implémentation du problème 45

5.4.1 Présentation d'App Designer 45

5.4.2 Présentation de l'application 45

5.4.3 Fonctionnement de PlanningAPP 46

5.4.4 Présentation du résultat et commentaires 49

5.5 Conclusion 52

Bibliographie et Webographie 54

Conclusion générale 53

Table des figures

1.1	Direction générale		3
1.2	Organigramme de SONATRACH		7
1.3	Organigramme de la direction Corporate Stratégie, Planification et
	Économie		9
3.1	Un exemple du diagramme de GANTT		21
3.2	Concepts en résumé		24
3.3	Durée de la tâche A		26
3.4	Représentation d'une etape dans un réseau PERT		26
3.5	Tâche fictive		26
3.6	Principe MPM		28
4.1	Le Macro-processus du système de planification et de gestion de la
	performance		32
4.2	Organigramme récapitulatif des méthodes de résolutions		38
4.3	Modélisation du problème sous CPLEX		39
5.1	La bibliothèque de composants d'App Designer		45
5.2	Identification		46
5.3	Message d'erreur		46
5.4	Bouton À propos		47
5.5	Fenêtre d'accueil		47
5.6	Bouton «...»		48
5.7	Fichier Excel importé		48
5.8	Bouton Aide		49
TABLE DES FIGURES
5.9		Tableau résultats		49
5.10		Résultats sous Excel		50
5.11		Tableau résultats 1		50
5.12		Tableau résultats 2		51
5.13		La durée totale du système		51
5.14		Solution graphique avec diagramme de GANTT		52

Liste des tableaux

2.1	Intérêts et limites de la planification.	12
2.2	Exemple de contraintes cumulatives	15
4.1	Tableau représentatif du nombre de variables	35
4.2	Tableau représentatif du nombre de contraintes	36
5.1	Tableau récapitulatif des tâches du système de planification et de
	gestion de la performance. 43
5.2	Tableau récapitulatif des durées, contraintes et temps d'attente des
	tâches du système. 44

Liste des abréviations

SPE : Direction Corporate Stratégie Planification et Economie.

AOA : Activity-on-Arrow.

AON : Activity-on-Node.

EVA : Economic Value Added.

ROE : Return On Equity.

ROI : Return On Investment.

CPM : Critical Path Method.

MPM : Méthode des Potentiels Métra.

PDM : Precedence Diagram Method.

PERT : Program Evaluation and Review Technic.

PL : Programmation Linéaire.

PLNE : Programmation linéaire en nombres entiers.

D-F : Relation Début - Fin.

IBM : International Business Machines Corporation.

ILOG : Entreprise française, éditeur de logiciels de gestion.

1

Introduction générale

Le secteur économique de l'énergie en Algérie occupe une place prédominante dans l'économie du pays, les hydrocarbures à eux seuls représentent 60 % des recettes du budget de l'état et 98 % des recettes d'exportation.[17]

Depuis plus de 50 ans, SONATRACH joue pleinement son rôle de locomotive de l'économie nationale. Elle a pour mission de valoriser les importantes réserves en hydrocarbures de l'Algérie.

Dans un monde industriel marqué par une concurrence accrue, les entreprises sont confrontées à une demande de plus en plus variable et fortement influencée par de nombreux facteurs conjoncturels.

Compte tenu des défis qui attendent ces entreprises et pour y faire face et avoir un coup d'avance sur la concurrence, la SONATRACH doit s'inscrire dans une nouvelle dynamique plus agile et efficace particulièrement dans son organisation et son fonctionnement. A cet effet, une Direction Corporate Stratégie, Planification et Economie (SPE) a été créée pour répondre aux nouveaux enjeux stratégiques.

Cette dernière est chargée de l'élaboration et le développement des plans à moyen et long terme et d'évaluer leur mise en oeuvre.

La Direction Corporate Stratégie, Planification et Economie (SPE) a élaboré un système intégré de planification et de gestion de la performance qui est un outil qui contribue à son pilotage stratégique, c'est au sein de ce système, qui se compose de plusieurs processus, que se définit la méthodologie d'élaboration de la stratégie de la planification à long terme, le choix des indicateurs clés de performance à mettre en place et la définition des cibles puis la planification des prévisions à court terme. C'est aussi dans ce système que se fait le suivi des réalisations et la préparation

des informations fournies au top management et nécessaires à la prise de décision pour l'amélioration des performances. Comme il s'agit d'un processus à visée décisionnelle, les délais revêtent une importance capitale. Un besoin existe donc pour optimiser au maximum le délai total de traitement.

Le but de notre travail est d'optimiser les délais de réalisation d'un cycle complet dans un système intégré de planification et de gestion de la performance.

Pour mener à bien notre mémoire, nous avons élaboré le plan suivant:

Chapitre 1 : Une présentation générale de l'organisme d'accueil en particulier la Direction Corporate Stratégie, Planification et Economie (SPE) là où notre projet s'est fait et suivi.

Chapitre 2 : Des généralités sur la planification, l'ordonnancement et la gestion de performance afin de bien comprendre les éléments de notre problème et nous aidera à considérer l'ordonnancement des tâches dans le système de planification et de la gestion de la performance lors de la résolution.

Chapitre 3 : Etude des méthodes d'ordonnancement et les techniques de modélisation des problèmes d'ordonnancement.

Chapitre 4 : Traitement de la problématique en définissant l'objectif, la modélisation mathématique, le type et l'évaluation de la taille du modèle avec une présentation d'une brève description des méthodes de résolution existantes, exactes ou approchées et la méthode choisie pour la résolution du modèle ainsi qu'une présentation du solveur CPLEX.

Chapitre 5 : Présentation de l'application développée pour la résolution du problème ainsi que l'implémentation des données collectées au sein de l'entreprise.

2

Notre travail se termine par une conclusion générale et quelques perspectives.

3

Chapitre1

Présentation de l'organisme d'accueil

1.1 Introduction

Ce chapitre présente la direction d'accueil, les différentes structures et départements afin de localiser l'emplacement de notre travail.

1.2 Historique de la SONATRACH

La SONATRACH (Société Nationale de Transport et Commercialisation des Hydrocarbures) est une entreprise pétrolière et gazière algérienne qui a vu le jour le 31 décembre 1963, elle avait pour mission de prendre en charge le transport et la commercialisation des hydrocarbures et de leurs dérivés.

FIGURE 1.1 - Direction générale

En 1965, la SONATRACH a pu réaliser son premier défi qui était de concevoir et de poser le premier pipeline Algérien.

Le 24 février 1971, SONATRACH a connu la plus grande et la plus importante transformation de son histoire après que le gouvernement ait décidé de nationaliser

4

Chapitre 1.Présentation de l'organisme d'accueil

les hydrocarbures, sa tâche était de gérer et de développer toutes les branches de l'industrie pétrolière et gazière algérienne.

Le décret présidentiel n° 98-48 du 11 Février 1998 a modifié les statuts, la forme juridique de SONATRACH et a défini son objet social et ses organes, ce qui a donné naissance à une société par action (SPA), employant environ 50 000 salariés (120 000 avec ses filiales), produit à elle seule 30% du PNB de l'Algérie. [17]

Aujourd'hui, SONATRACH est la Compagnie Algérienne de Recherche, d'Exploi-tation, de Transport par Canalisation, de Transformation et de Commercialisation des Hydrocarbures et de leurs dérivés. L'entreprise est également impliquée dans d'autres domaines tels que la production d'électricité, les énergies nouvelles et renouvelables et le dessalement de l'eau de mer. Elle est présente en Algérie et partout dans le monde où il y a des opportunités. Elle a déjà démarré ses activités dans plusieurs pays en amont et en aval et compte actuellement 16 filiales nationales et 24 filiales internationales dans l'exploitation, le raffinage la commercialisation, le stockage, les services aux puits, etc.. Ce qui la rend la première entreprise du continent Africain et 12^eme parmi les compagnies pétrolières mondiales. Sa production globale est de 230 millons de TEP en 2006. [17]

1.3 Organisation de l'entreprise

SONATRACH est organisée autour de ses métiers dans les activités où se crée la richesse et en assurant à ses activités appui et expérience à travers les fonctions centrales du groupe, elle se résume en 3 points :

1.3.1 La Direction générale

La direction générale se compose essentiellement d'un :

· Président Directeur Général (PDG).

· Comité Exécutif.

· Secrétariat Général.

· Comité d'Ethique.

5

Chapitre 1.Présentation de l'organisme d'accueil

1.3.2 Structures fonctionnelles

Les structures fonctionnelles ont pour role d'élaborer et veiller à l'application des politiques et stratégies de la société. Elles fournissent l'expertise et l'appui nécessaires aux activités opérationnelles du groupe.

Elles sont organisées comme suit:

· Direction Corporate Stratégie, Planification et Economie (SPE),

· Direction Corporate Finances (FIN),

· Direction Corporate Business Development et Marketing (BDM),

· Direction Corporate Ressources Humaines (RHU),

· Direction Centrale Procurement et Logistique (PL),

· Direction Centrale Ressources Nouvelles (REN),

· Direction Centrale Engineering et Project Management (EPM),

·

,

Direction Centrale Juridique (JUR)

· Direction Centrale Digitalisation et Système d'Information (DSI),

· Direction Centrale Santé, Sécurité et Environnement (HSE),

· Direction Centrale Recherche et Développement (RD).

1.3.3 Activités de SONATRACH

Exploration et Production (E-P)

L'activité Exploration-Production a pour mission la recherche, le développement, l'exploitation et la production des hydrocarbures . Elle est chargée aussi de l'élabo-ration et de l'application des politiques et stratégies d'exploration. Elle s'articule autour de trois axes:

-- Le développement et l'exploitation des gisements pour une valorisation optimale des ressources,

-- La gestion des activités en partenariat dans les phases d'exploration, de développement et d'exploitation des gisements,

-- La recherche, la négociation et le développement de nouveaux projets sur le territoire national et à l'international.

6

Chapitre 1.Présentation de l'organisme d'accueil

Transport par Canalisations (TRC)

Le transport des hydrocarbures liquides et gazeux par canalisations prend en charge le développement, la gestion et l'exploitation du réseau de transport, de stockage, de livraison et de chargement des hydrocarbures. [18]

L'activité TRC couvre les domaines operationnels suivants:

-- Exploitation des ouvrages de transport des hydrocarbures et des installations portuaires,

-- Maintenance des ouvrages de transport des hydrocarbures et des installations portuaires,

-- Etudes et développement, à l'éxclusion des activités relevant de la Direction Corporate Business Development et Marketing (BDM) pour la partie étude et de la Direction Centrale Engineering et Project Management pour la partie developpement et realisation de projets.

Liquéfaction et Séparation (LQS)

L'activité Liquéfaction-Séparation a pour mission la transformation des hydrocarbures par la liquéfaction du gaz naturel et la séparation des GPL. Désormais l'ac-tivité est concentrée principalement sur l'exploitation et l'optimisation de l'outil de production tandis que le développement des grands projets structurants en matière de GNL et GPL est assuré par les nouveaux démembrements de la Direction Générale. [18]

Raffinage et Pétrochimie (RP)

L'activité Raffinage et Pétrochimie a pour mission essentielle l'exploitation et la gestion de l'outil de production du Raffinage et de la Pétrochimie, pour répondre principalement à la demande du marché national en produits pétroliers. [18]

L'activité RP couvre les domaines operationnels suivants:

-- Raffinage du Pétrole Brut et du Condensat, -- Pétrochimie.

Chapitre 1.Présentation de l'organisme d'accueil

Commercialisation (COM)

L'activité Commercialisation a pour mission de veiller aux approvisionnements énergétiques du marché national, sa première mission statutaire en tant que garant du service public, et à la valorisation des hydrocarbures liquides et gazeux, primaires et transformés, exportés sur les marchés internationaux. [18]

L'activité COM couvre les domaines operationnels suivants:

-- Commercialisation du pétrole brut et produits pétroliers,

-- Commercialisation gaz,

-- Elaboration et suivi de la mise en reuvre de la politique de trading.

La figure suivante représente l'organisation de SONATRACH :

7

FIGURE 1.2 - Organigramme de SONATRACH

8

Chapitre 1.Présentation de l'organisme d'accueil

1.4 Missions de SONATRACH

SONATRACH a pour missions essentielles:

-- La prospection, la recherche et l'exploitation.

-- Le traitement de la liquéfaction du gaz naturel.

-- La transformation et le raffinage des hydrocarbures.

-- La séparation du GPL.

-- La commercialisation des hydrocarbures sur le marché international.

-- L'approvisionnement des hydrocarbures liquides et gazeux sur le marché na-

tional.

-- Le développement de toute forme d'activités conjointe en Algérie et à l'étran-

ger avec les sociétés algériennes ou étrangères.

1.5 Présentation de la Direction d'accueil : La Direction SPE

La Direction Corporate Stratégie, Planification et Economie (SPE) est chargée de l'élaboration et le développement à moyen et long terme et d'évaluer leur mise en oeuvre.

1.5.1 Organisation de la Direction SPE

Sous les commandes d'un vice président, la direction Corporate Stratégie, Planification et Économie (SPE) est organisée autour de :

· Une Direction Stratégie et intelligence Economique,

· Une Direction Planification,

· Une Direction Gestion de la Performance,

· Une Direction Etudes Economiques et Modèles,

· Une Direction Organisation,

· Une Direction Informations Documentaires,

· Une Direction Administration et Logistique,

· Des Conseillers.

La figure ci-dessous représente l'organigramme de la direction Corporate Stratégie, Planification et Economie :

9

Chapitre 1.Présentation de l'organisme d'accueil

FIGURE 1.3 - Organigramme de la direction Corporate Stratégie, Planification et Économie

1.5.2 Missions de la Direction SPE

La Direction Corporate Stratégie, Planification et Economie a pour missions essentielles :

· L'animation du processus de formulation, d'adoption et de suivi de la mise en oeuvre de la stratégie de la Société,

· L'organisation, l'animation et la coordination du processus de planification, en particulier les plans a moyen terme et les plans annuels,

· L'organisation, l'animation, la coordination et le contrôle du processus de gestion et de suivi des performances,

· L'organisation, l'animation et la coordination du cadrage stratégique de la Société,

· L'élaboration des études économiques des projets de la Société,

· L'élaboration, le suivi et la mise en oeuvre d'un système d'évaluation économique du portefeuille de la Société en Algérie et a l'étranger.

1.6 Conclusion

Dans ce chapitre nous avons présenté la SONATRACH d'une façon générale en se basant sur la Direction Corporate Stratégie, Planification et Economie (SPE) là où notre projet s'est fait et suivi.

10

Chapitre2

Généralités sur la planification, l'ordonnancement et la performance

2.1 Introduction

Dans ce chapitre nous aborderons differentes notions sur la planification, l'or-donnancement et la performance

2.2 La planification

La planification est un élément qui joue un rôle clé dans le succès d'une entreprise. En rédigeant un plan stratégique détaillé, l'entreprise peut se donner un mandat et adopter une marche à suivre qui lui permettra de connaître le succès.[19]

2.2.1 Définition

La planification est un processus qui permet d'organiser dans le temps une succession d'actions ou d'évènements afin de réaliser un objectif particulier ou un projet.

2.2.2 Les différents types de planification La planification stratégique:

· S'étale sur plus de 5 ans.

· Analyse certains aspects de l'environnement externe et de repérer les forces et les faiblesses.

· Déterminer la mission et les objectifs généraux de l'entreprise.

11

Chapitre 2.Généralités sur la planification, l'ordonnancement et la performance

La planification à moyen terme:

· Couvre une période de cinq ans au maximum.

· Elaboration des plans détaillés, coordonnés, qui concerne la production, la commercialisation et les ressources humaines...

La planification à court terme:

· S'étale sur une période pas plus qu'un an.

· Les cadres inférieurs définissent les tâches à accomplir les programmes, les projets, les opérations et les activités propres à leurs unités organisationnelles.

2.2.3 Le processus de planification

1 - L'analyse de la situation:

Il s'agit au niveau de cette étape de faire un diagnostic. Le diagnostic:

L'objectif d'un diagnostic est de déterminer si celle-ci se porte bien ou mal et de détecter ses dysfonctionnements.

Les phases du diagnostic:

· Analyse préalable de la stratégie à travers sa definition et l'appréciation de sa pertinence et son adéquation avec l'environnement.

· Analyse du potentiel interne:

- Evaluation des moyens humains (effectifs, salaires, qualifications...) et leurs

adéquation avec les besoins de l'entreprise.

- Evaluation des moyens financiers.

- Evaluation des moyens techniques.

· Analyse de l'environnement par la collecte et l'analyse des informations.

2 - La formulation de la mission et des objectifs:

C'est une étape cruciale, puisque la mission et les objectifs servent de point de départ et d'encadrement aux activités de tous les services, les divisions et les unités administratives.

La mission est la description générale et durable de l'entreprise, elle correspond à la raison pour laquelle elle est crée.

Un Objectif se définit par quatre composantes : une dimension, une échelle de mesure, une norme et un horizon temporel. Il peut être stratégique, tactique ou opérationnel.

12

Chapitre 2.Généralités sur la planification, l'ordonnancement et la performance

2.2.4 Les intérêts et les limites de la planification

Intérêts		Limites	- Incite à l'utilisation d'un processus uniforme. - Force les gestionnaires à examiner tous les programmes, les projets et les activités d'une façon systématique. - Permet de saisir des opportunités. - Fournit une base de contrôle. - Equilibre l'utilisation des moyens de l'entreprise.
- Coûteuse. - Risque d'erreur. - Peu flexible dans un environnement turbulent et incertain.

TABLE 2.1 - Intérêts et limites de la planification.

2.3 Notions générales sur les problèmes d'ordonnancement

L'ordonnancement se situe exactement dans la phase planification. Il réalise le suivi opérationnel du projet : gestion de ressources, suivi de l'avancement, lancement des activités. Techniquement, ordonnancer un projet consiste à programmer dans le temps l'exécution des tâches, tout en respectant les contraintes de manière à optimiser les critères de performance retenus.

2.3.1 Définition d'ordonnancement

Selon Carlier et al. [1], "ordonnancer, c'est programmer l'exécution d'une réalisation en atribuant des ressources aux tâches et en fixant leur date d'exécution". On peut définire une autre définition qui est plus explicite : "Un ordonnancement constitue une solutio au problème d'ordonnancement. Il décrit l'exécution des tâches et l'allocation des ressources au cours du temps, et vise à satisfaire un ou plusiseurs objectifs. Plus précisement, on parle de problème d'ordonnancement lorsqu'on doit déterminer les dates de début et de fin des tâches, alors qu'on réserve le terme de problème de séquencement au cas où l'on cherche seulement à fixer un ordre relatif entre les tâches qui peuvent être en conflit pour l'utilisation des ressources. Un ordonnancement induit nécessairement un ensemble unique de relations de séquencement"[2].

Chapitre 2.Généralités sur la planification, l'ordonnancement et la performance

2.3.2 Les tâches

Une tâche ou activité est une entité élémentaire localisée dans le temps.

Chaque tâche:

-- est identifiée par son rôle à jouer dans l'éxécution du travail.

-- se caractérise par un début et une fin.

-- consomme des ressources qui ont un coût d'utilisation et sont disponibles en

quantité limitée.

-- est souvent reliée aux autres tâches par des relations d'antériorité qui im-

pliquent qu'une tâche ne peut débuter avant qu'une autre ne soit préalable-

ment terminée.

2.3.3 Quelques définitions

- Date début au plus tôt: c'est la date la plus prématurée à laquelle une activité peut commencer.

- Date début au plus tard: c'est la date la plus tardive à laquelle une activité peut commencer sans tarder la tâche suivante.

- Date fin au plus tôt: c'est la date plus hâtive dont une tâche peut prendre fin.

- Date fin au plus tard : c'est la date la plus tardive dont une tâche peut prendre fin sans retarder la tâche suivante.

- La marge libre : c'est la réserve de temps dont on dispose sur une tâche (i, j) qui permet, si elle est consommée, de ne pas retarder les dates au plus tôt des tâches ultérieures. Elle est définie par:

m j = èj - (è + d j)

où

èj : date fin au plus tôt de la tâches (i, j).

è : date début au plus tôt de la tâches (i, j). d j : durée de la tâches (i, j).

- La marge totale : est la réserve du temps sur la tâches (i,j) qui si elle est consommée, fait que cette tâches se ramènera à sa date au plus tard. Elle est définie par:

M j = è* j - (è + d j)

13

où è* j : date fin au plus tard.

14

Chapitre 2.Généralités sur la planification, l'ordonnancement et la performance

2.3.4 Les ressources

Une ressources est un moyen technique ou humain utilisé pour réaliser une tâche. On distingue deux types de ressources :

- Les ressources renouvelables, qui après avoir été allouées à une tâche, redeviennent disponibles (machines, personnel,...).

- Les ressources consommables, qui après avoir été allouées à une tâche, ne sont plus diponibles ( matières premières, argent,...).

Qu'elle soit renouvelable ou consommable, la disponibilité d'une ressource peut varier au cours du temps. par ailleurs, dans le cas des ressources renouvelables, on distingue principalement les ressources disjonctives qui ne peuvent exécuter qu'une tâche à la fois et les ressources cumulatives qui peuvent être utilisées par plusieurs tâches simulatanément mais en nombre limités.

2.3.5 Les contraintes

Une contrainte est une restriction sur les valeurs que peuvent prendre une ou plusieurs variables de décision sur le temps (variable d'ordonnancement) ou bien sur les ressources (variables d'affectation).[5]

Nous pouvons distinguer plusieurs types d'entre elles :

- Les contraintes potentielles : qui peuvent être de deux sortes:

· Les contraintes d'antériorité selon lesquelles une tâche j ne peut commencer avant qu'une tâche i ne soit terminée.

· Les contraintes de localisation temporelle impliquant qu'une tâche donnée i ne peut débuter avant une date imposée, ou qu'elle ne peut s'achever après une date imposée.[6]

- Les contraintes disjonctives:

Une contrainte disjonctive impose la non-réalisation simultanée de deux tâches. Ou comme dans le cas d'utilisation d'une ressource présente en un seul exemplaire (une machine,un ouvrier, etc.) ou pour exprimer les interdictions de réalisation simultanée pour des raisons de sécurité ou des problèmes d'espace.[7]

- Les contraintes cumulatives:

On parle de contraintes cumulatives lorsque les tâches demandent une partie d'une ou plusieurs ressources présentes en quantité limitée. Le problème est beaucoup plus combinatoire que pour les contraintes disjonctive. Considérons l'exemple où nous avons cinq intervenants et cinq tâches à effectuer. Chaque tâche demande la présence d'un certain nombre de ces intervenants. [8]

15

Chapitre 2.Généralités sur la planification, l'ordonnancement et la performance

Tâche	A	B	C	D		E	Nombre d'intervenants
4	3	2	1	1

TABLE 2.2 - Exemple de contraintes cumulatives

Pour que l'ordonnancement soit réalisable, il faut qu'on utilise, à tout moment, au plus cinq intervenants. Cette contraintes va interdire les ordonnancements réalisant en parallèle: (A//B), (A//C), (A//D//E), (B//C//D), (B//C//E). Ces configurations sont minimales au sens que, si (A//B) est interdit, toute configuration contenant (A//B) l'est aussi (par exemple: (A//B//D), (A//B//C//D), ect).

2.4 La gestion de la performance

Le terme de performance intéresse de plus en plus les entreprises et utilisé par celle-ci dans l'appréciation de leurs activités. En effet, la performance se réfère à la capacité de l'entreprise à concrétiser ses objectifs stratégiques en adoptant les meilleures façons de faire.

Cette section sera consacrée à la présentation de quelques généralités sur la performance.

2.4.1 Concepts sur la performance

La performance est un concept englobant et intégrateur, donc, difficile à définir de façon précise.

Pour mieux cerner le concept de la performance, il est utile de montrer quelques définitions proposées par quelques auteurs:

Selon L'ORINO Philipe : « la performance dans une entreprise est tout ce qui, et seulement ce qui contribue à atteindre ces objectifs stratégiques ».[14]

Pour DIMITRE WEISS : « la performance pour un salarié, pour un chef d'entreprise, peut- être pour une équipe dans la direction, le résultat global, le profit apprécié sur une ou plusieurs années, mesurant objectivement l'efficacité de la gestion ». [15]

D'après KHEMAKHEM. A : « la performance d'un centre de responsabilité (atelier, service, unité, entreprise, branche,...) Désigne l'efficacité et la productivité dans laquelle ce centre de responsabilité a atteint les objectifs qu'il avait acceptés ». [16]

De ces définitions nous pouvons dire que la notion de la performance découle du degré d'atteinte des objectifs. Autrement dit, la performance réside là où il y'a une conformité entre les résultats obtenus et les objectifs tracés.

16

Chapitre 2.Généralités sur la planification, l'ordonnancement et la performance

Aussi la performance peut être la réponse au besoin, ni plus coûteux ni moins insuffisant en termes de quantité, de qualité, de coût et de temps.

D'une manière générale, la performance est un résultat chiffré obtenu dans le cadre d'une compétition.

Au niveau d'une entreprise, la performance exprime le degré d'accomplissement des objectifs poursuivis.

Une entreprise performante doit être à la fois efficace et efficiente. Elle est efficace lorsqu'elle atteint les objectifs qu'elle s'est fixés. Elle est efficiente lorsqu'elle minimise les moyens mis en oeuvre pour atteindre les objectifs qu'elle s'est fixés.

2.4.2 Les typologies de la performance

Appréhendée d'une manière générale sur un plan strictement financier, la performance de l'entreprise a été progressivement élargie au cours du vingtième siècle (Germain et Trébucq; 2004) pour considérer d'autres aspects tels que les aspects économiques, commerciaux, sociaux et sociétaux. Parmi ces aspects, il est possible de distinguer:

· La performance financière.

· La performance économique.

· La performance sociale.

· La performance technique.

· La performance organisationnelle.

· La performance managériale.

· La performance sociétale.

· La performance commerciale.

· La performance concurrentielle.

Dans notre travail on s'intéresse à la performance organisationnelle :

2.4.3 La performance organisationnelle

Elle concerne la manière dont l'entreprise est organisée pour atteindre ses objectifs, et la façon dont elle parvient à les atteindre. Il existe quatre facteurs de l'effica-cité organisationnelle, à savoir:

· Le respect de la structure formelle;

· Les relations entre les composants de l'organisation;

· La qualité de la circulation de l'information;

· La flexibilité de la structure.

17

Chapitre 2.Généralités sur la planification, l'ordonnancement et la performance

Dans cette conception, la performance de l'entreprise résulte de la valeur de son organisation. Cette dernière est déterminante et c'est elle qui impose ses exigences au système social. [13]

2.4.4 Les mesures de la performance

La performance se mesure avec des critères (ou indicateurs) qualitatifs ou quantitatifs de résultat. Pour mesurer l'efficacité, on utilise un critère qui exprime un rapport entre le résultat obtenu et l'objectif visé. Pour mesurer l'efficience, on utilise un critère qui exprime un rapport entre le résultat obtenu et les moyens mis en oeuvre.

Pour évaluer la performance d'une entreprise, il est nécessaire d'effectuer des mesures à tous les niveaux : financier, économique, social, organisationnel et sociétal.

La performance financière:

Traditionnellement, d'après Alfred Sloan, on mesure la performance financière à l'aide des indicateurs ROI et ROE. Aujourd'hui, on utilise en plus l'indicateur EVA.

· Le ROI (Return On Investment) : ce ratio mesure la rentabilité économique du capital utilisé par l'entreprise. C'est le rapport entre le résultat d'exploitation et les capitaux investis.

· Le ROE (Return On Equity) : ce ratio mesure la rentabilité financière des capitaux apportés par les propriétaires de l'entreprise. C'est le rapport entre le résultat net et les capitaux propres.

· L'EVA (Economic Value Added) : ce ratio permet de mesurer la création de valeur pour l'actionnaire. C'est la différence entre le résultat opérationnel et les capitaux investis.

La performance économique:

Il s'agit de mesurer les composantes de la compétitivité de l'entreprise : la compétitivité-prix et la compétitivité-hors prix.

· La compétitivité-prix: désigne la capacité d'un produit à attirer des clients au détriment des produits concurrents du fait de son prix. Sa mesure permet de situer la place de l'entreprise sur le marché par rapport à ses concurrents.

· La compétitivité hors-prix: désigne la capacité d'un produit à attirer des clients au détriment des produits concurrents du fait des éléments indépendants du prix. Elle est obtenue grâce à des éléments comme la qualité des produits, l'innovation, le service, le design...

18

Chapitre 2.Généralités sur la planification, l'ordonnancement et la performance

La performance organisationnelle:

Il s'agit de mesurer la performance de l'entreprise au niveau de la qualité de la production, de la flexibilité, des délais...

La performance sociale:

Le bilan social récapitule les principales données chiffrées permettant d'apprécier la performance sociale et les rapports sociaux au sein d'une entreprise. En France, le bilan social est obligatoire pour les entreprises de plus de 300 salariés. Parmi les nombreux indicateurs sociaux, on peut citer : le montant des rémunérations, le nombre d'accidents de travail, les maladies professionnelles ...

La performance sociétale :

Indique l'engagement de l'entreprise dans les domaines environnementaux, humanitaires, culturels. Les outils de la responsabilité sociétale de l'entreprise (RSE) peuvent être utilisés pour apprécier le niveau de performance de l'entreprise. [24]

2.5 L'impact de la planification sur la performance

Les entreprises se mesurent toujours par leurs performances. Une performance plus forte et durable doit impérativement prendre ses bases sur une planification stratégique bien étudiée surtout dans un milieu où les données sont bien définies car les spécialistes disent qu'il y a une relation positive entre la planification qui est faite dans une entreprise et les résultats que cette entreprise est capable d'atteindre et l'absence d'une planification est une cause importante de faillite.

2.6 Conclusion

Dans ce deuxième chapitre nous avons donné des généralités sur la planification, l'ordonnancement et la gestion de la performance.

En comprenant les éléments de la planification et de la gestion des performances, cela nous aidera à considérer l'ordonnancement des tâches dans le système de planification et de la gestion de la performance de Sonatrach lors de la résolution, mais avant cela il faut d'abord étudier les méthodes d'ordonnancement et les techniques de modélisation de ces problèmes d'ordonnancement, ce qui fera l'objet de prochain chapitre.

19

Chapitre3

Les outils de modélisation et les méthodes de résolution

3.1 Introduction

La modélisation mathématique est une traduction des observation à l'aide d'ou-tils, techniques et théories mathématiques.

Il s'agit d'une étape cruciale dans l'étude de tout problème dans la recherche opérationnelle.

Dans ce qui suit, nous étudierons les méthodes d'ordonnancement et les techniques de la modélisation des problèmes d'ordonnancement qui nécessitent la connaissance de certains concepts de base de la théorie des graphes et de la programmation linéaire.

3.2 Le diagramme de GANTT

Le diagramme de GANTT n'est pas une méthode pour résoudre les problème d'ordonnancement mais seulement une méthode pour représenter une solution.

Définition

Le diagramme de GANTT est un outil utilisé en ordonnancement et en gestion de projet, permettant de modéliser la planification de tâches nécessaires à la réalisation d'un projet. Il a été mis au point par Henry GANTT en 1917. Un diagramme de Gantt répertorie toutes les tâches à accomplir pour mener le projet à bien, et indique la date à laquelle ces tâches doivent être effectuées (le planning).

20

Chapitre 3.Les outils de modélisation et les méthodes de résolution

Etant donné la relative facilitée de lecture des diagrammes GANTT, cet outil est utilisé par la quasi-totalité des chefs de projet dans tous les secteurs, permettant de représenter graphiquement l'avancement du projet, mais c'est également un bon moyen de communication entre les différents acteurs d'un projet.

Pour ce type de modélisation il existe plusieurs outils spécialisés dont les plus connus est Microsoft Project et Primavera.[25]

Principe

Le principe de ce type de diagramme est de représenter au sein d'un tableau telle que chaque tâche est représentée par une ligne, tandis que les colonnes représentent les unités de temps (exprimées en jours, semaines , mois...).

Le temps estimé pour une tâche se modélise par une barre horizontale dont l'extré-mité gauche est positionnée sur la date prévue de démarrage et l'extrémité droite sur la date prévue de fin de réalisation. Les tâches peuvent s'enchaîner séquentielle-ment ou bien être exécutées en parallèle. Ce diagramme permet donc de visualiser d'un seul coup d'oeil:

- Les différentes tâches à envisager.

- La date de début et la date de fin de chaque tâche.

- La durée comptée de chaque tâche.

- Le chevauchement éventuel des tâches, et la durée de ce chevauchement.

- La date de début et la date de fin du projet dans son ensemble.[11]

Réalisation

Les différentes étapes de réalisation d'un diagramme de Gantt sont les suivantes:

- Etape 1 : On définit les différentes tâches à réaliser et leurs durées.

- Etape 2 : On détermine les relations d'antériorité entre tâches.

- Etape 3 : On représente les tâches par des traits dans le diagramme : d'abord les tâches n'ayant aucune antériorité, puis les taches dont les tâches antérieures ont déjà été présentées, et ainsi de suite. . .

- Etape 4 : On représente la progression réelle du travail par un trait pointillé parallèle à la tâche planifiée.

Exemple

La figure ci-dessous représente un diagramme de Gantt, où chaque colonne représente une unité de temps, les traits épais représentent les durées d'exécution prévues des tâches et les traits pointillés représentent le déroulement d'exécution.

21

Chapitre 3.Les outils de modélisation et les méthodes de résolution

Par exemple, la tâche B, qui dure 5 unités de temps, ne peut commencer son exécution qu'après la fin de la tâche A et elle peut s'exécuter en même temps que la tâche C.

FIGURE 3.1 - Un exemple du diagramme de GANTT

Le chemin critique est formé d'une succession de tâches sur le chemin le plus long en terme de durées (A,B,D,E dans l'exemple). Il est appelé chemin critique parce que tout retard pris sur l'une des tâches de ce chemin entraîne du retard dans l'achèvement du projet.

Avantages et limites

Le diagramme de GANTT est l'un des outils les plus efficaces pour une visualisation rapide et facile de l'avancement du projet, il permet aussi de déterminer la date de réalisation d'un projet et d'identifier les marges existantes sur certaines tâches (avec une date de début au plus tôt et une date de fin au plus tard).

Son point faible est que son application est limitée à des problèmes particuliers.

3.3 Modélisation par les graphes

3.3.1 Notions de la théorie des graphes

Graphe

Un graphe est un dessin géométrique défini par la donnée d'un ensemble de points (appelées sommets ou noeuds), reliés entre eux par un ensemble de flèches (Appelées arcs). Chaque arc a pour extrémités deux points, éventuellement confondus.[3]

22

Chapitre 3.Les outils de modélisation et les méthodes de résolution

Graphe orienté

En théorie des graphes, un graphe orienté C = (X, A) est défini par la donnée d'un ensemble de sommets X et d'un ensemble d'arcs A, chaque arc étant un couple de sommets. Par exemple, si x et y sont des sommets, les couples (x, y) et (y, x) peuvent être des arcs du graphe C :

dans ce cas, ils sont notés respectivement xy et yx.

Chemin

Soit C = (X, U) un graphe,

Un chemin du sommet X0 à Xk dans un graphe C, est une suite de sommets reliés successi- vement par des arcs orientés dans le même sens;

On le note : (X0, X1, X2, ..., Xk)

- Le chemin critique : d'un projet est la plus longue séquence de tâches qui doit être accomplie pour que le projet soit terminé à la date due.[3]

Circuit

Le circuit est un chemin simple dont les extrémités coïncident. (dans les graphes orienté seulement).

Réseau

Un réseau est un graphe C = (X, U) muni d'une application d : U R qui à chaque arc fait correspondre un poids d(u), on note un tel réseau par R = (X, U, d). On pratique d(u) peut matérialiser un coût, une distance, une durée ...etc.

Arbre

Un arbre est un graphe simple connexe ne possédant pas de cycle. Soit n le nombre de sommets d'un graphe G et m le nombre de ses arcs:

- Si C est connexe m = n - 1.

- Si C est sans cycles m = n - 1.

Arborescence

Un graphe C = (X, U), avec |X| = n = 2 sommets est une arborescence de racine s si :

- C est un arbre.

- S est une racine de C.

23

Chapitre 3.Les outils de modélisation et les méthodes de résolution

Un sommet s d'un graphe G est une racine de G s'il existe un chemin joignant s à chaque sommet du graphe G.

Un sommet z d'un graphe G est une anti-racine de G s'il existe un chemin joignant chaque sommet du graphe G à z.

Makespan

C'est la date de fin d'exécution de l'ordonnancement (Cmax).

La mise en ordre d'un graphe (l'ordonnancement d'un graphe)

Ordonner un graphe revient à disposer dans un certain ordre ses sommets tels que les arcs soient dans le même sens. On définit ainsi les différents niveaux des sommets. L'ordonnancement d'un graphe se traduit par un algorithme.

Recherche du plus court (long) chemin dans un graphe:

Les problèmes de cheminement dans les graphes (en particulier la recherche d'un plus court chemin) comptent parmi les problèmes les plus anciens de la théorie des graphes et les plus importants par leurs applications.

pour la résolution de ces problèmes,il existe plusieurs algorithmes qui calcule le plus court (long) chemin,le plus courant est l'algorithme de Bellman.

L'idée de l'algorithme de Bellman, est de calculer de proche en proche l'arbores-cence de plus courtes distances, issue du sommet s à un sommet donné p.

On ne calcule la plus courte distance du sommet s à y, que si on a déjà calculé les plus courtes distance du sommet s à tous les prédécesseurs du sommet y.

3.3.2 Les représentations graphiques

Il y'a principalement deux représentations graphique d'un projet:

- La représentation AON (Activity-on-Node) ou « Potentiel-tâches ».

- La représentation AOA (Activity-on-Arrow) ou «Potentiel-étapes ».

Les abréviations AON et AOA signifient successivement : Activity On Network et Activity On Arc. Ces deux notions sont utilisées dans la représentation par le biais d'un réseau de gestion de projet, à son tour faisant partie d'une branche plus générale et plus large : La Théorie des Graphes. Cette dernière est utilisée notamment dans plusieurs domaines comme le transport, les réseaux neurones ou l'optimisa-tion etc. Ces deux concepts ont été développés dans les années 50, AON pour établir ce qu'on appelle le chemin critique d'un planning de projet et AOA dans la méthode

Chapitre 3.Les outils de modélisation et les méthodes de résolution

(graphe) de PERT, AON est utilisé notamment dans la méthode appelée PDM (Precedence Diagram Method), Cette dernière est utilisée entre autres, dans le CPM (Critical Path Method) pour déterminer le chemin critique.[4]

Les méthodes utilisant la représentation AON sont MPM et PDM.

Les méthodes utilisant la représentation AOA sont : PERT et CPM.

24

FIGURE 3.2 - Concepts en résumé

A ce jour seules sont appliquées industriellement les méthodes simples : la méthode PERT et la méthode des potentiels MPM.

3.3.3 La méthode PERT

Le terme PERT est l'acronyme de «Program Evaluation and Review Technic» ou «program evaluation research task ». Sa traduction française serait : «technique d'évaluation et d'examen de programmes» ou « de projets », ou encore « technique d'élaboration et de mise à jour de programme ».

"Program Evaluation and Review Technic" est une méthode conventionnelle utilisable en gestion de projet "gestion de temps et des délais", ordonnancement et planification créé en 1958 à la demande de la marine américaine, qui voulait planifier la durée de son programme de missiles balistiques nucléaires miniaturisés Polaris. Alors que le délai initial de ce programme qui a fait intervenir 9000 sous-traitants et 250 fournisseurs était de 7 ans, l'application de la technique du PERT a permis de réduire ce délai à 4 ans. [26]

25

Chapitre 3.Les outils de modélisation et les méthodes de résolution

Objectif de la méthode PERT

La méthode PERT est une technique permettant de gérer l'ordonnancement dans un projet. Elle consiste à représenter sous forme de graphe , un réseau de tâches dont l'enchaînement permet d'aboutir à l'atteinte des objectifs d'un projet.

La méthode permet:

-- La prise en compte des différentes tâches à réaliser et des antériorités à respecter entre ces tâches.

-- La détermination de la durée globale du projet et des tâches qui la conditionnent.

-- La détermination des tâches pour lesquelles du temps est disponible (notion de marge).

-- La détermination des dates « au plus tôt » et « au plus tard » pour lancer chaque tâche.

-- L'établissement d'un planning d'exécution et d'enchaînement des tâches. -- La nomination d'un chef de projet chargé d'assurer le suivi du projet, de rendre

compte si nécessaire et de prendre des décisions en cas d'écart par rapport aux

prévisions.

-- La gestion des moyens logistiques (matériels) et humains (effectif) intervenant sur le projet. [26]

Principe du réseau PERT

Le diagramme PERT propose de calculer, à l'aide d'un graphe, l'enchaînement optimal des tâches. Chaque tâche est identifiée par sa durée moyenne et sa précé-dence. Le graphe propose ainsi pour chaque tâche une date "au plus tôt" et une date "au plus tard". Tant que la tâche démarre à une date comprise entre ces deux limites, elle ne pénalisera pas les tâches avales.

Le graphe PERT est caractérisé par des sommets (étapes) reliés ente eux par des arcs (tâches) chaque arc étant défini par son début, sa fin, sa durée et les sommets entre les arcs définissant les relations d'antériorité. Ce graphe ne comportera ni routeur ni circuit et on ne rencontrera qu'un seul arc ente deux sommets.

Ainsi, pour élaborer et exploiter un réseau on peut distinguer six grandes étapes:

-- Etablir la liste des tâches;

-- Déterminer les conditions d'antériorité;

-- Tracer le réseau PERT;

-- Calculer les dates des tâches et déterminer le chemine critique;

-- Calculer les marges totales et les marges libres de chaque tâche;

-- Construire le planning de projet;

26

Chapitre 3.Les outils de modélisation et les méthodes de résolution

Symboles de la représentation du graphe PERT

Le réseau PERT (appelé parfois graphe PERT) est composé des éléments suivants:

· Tâche (parfois activité), représentée par une flèche (arc). A chaque tâche correspond un code et une durée. Néanmoins, la longueur de la flèche est indépendante de la durée.

FIGURE 3.3 - Durée de la tâche A

· Étape, c'est-à-dire le début et la fin d'une tâche. Chaque tâche possède une étape de début et une étape de fin. A l'exception des étapes initiales et finales, chaque étape de fin est étape de début de la tâche suivante. Les étapes sont en règle générale numérotées et représentées par un cercle, mais elles peuvent parfois avoir d'autres formes (carré, rectangle, ovale, etc.).

FIGURE 3.4 - Représentation d'une etape dans un réseau PERT

· Tâche fictive, représentée par une flèche en pointillés, permet d'indiquer les contraintes d'enchaînement entre certaines étapes.

FIGURE 3.5 - Tâche fictive

Avantages de PERT

PERT permet:

-- La visualisation de la dépendance des tâches et de procéder à leur ordonnancement.

-- La prise en compte des différentes tâches à réaliser et des antériorités à respecter entre ces tâches.

27

Chapitre 3.Les outils de modélisation et les méthodes de résolution

-- La détermination de la durée globale du projet et des tâches qui la conditionnent.

-- La détermination des tâches pour lesquelles du temps est disponible (notion de marge).

3.3.4 La Méthode des Potentiels Métra (MPM) Définition

La Méthode des Potentiels et antécédents Métra (MPM) fait partie des méthodes dites "potentiel-tâches". La Méthode MPM est une méthode d'ordonnancement basée sur la théorie des graphes, et visant à optimiser la planification des tâches d'un projet. Semblable à PERT, les principales différences entre les deux méthodes reposent essentiellement dans la construction du graphe. Elle a été développée par le chercheur français Bernard Roy, en 1958.

L'utilisation de la MPM permet de :

· Déterminer la durée minimum nécessaire pour mener à bien un projet et les dates auxquelles peuvent ou doivent débuter les différents tâches nécessaires à sa réalisation pour que cette durée minimum soit respectée.

· Calculer les marges des différentes tâches et identifier les intervalles de flottements.

· Etudier les couts de réalisation de chaque tâche et le coût global du projet.[27]

Principe

-- Chaque tâche est représentée par un sommet, et les arcs entre les sommets traduisent uniquement les relations d'anteriorité des tâches.

-- Chaque tâche (ou sommet) est renseignée par la date à laquelle elle peut commencer au plus tôt (date de début au plus tôt) et terminer au plus tard (date de fin au plus tard) pour respecter le délais optimal de réalisation du projet.

-- A chaque arc est associée une valeur numérique qui représente soit une durée d'opération, soit un délai.

-- Le graphe commence et se termine par 2 sommets, respectivement appelés Début et Fin symbolisant le début et la fin des opérations. (ces deux sommets

28

Chapitre 3.Les outils de modélisation et les méthodes de résolution

ne correspondent pas à une tâche).

-- Le graphe se lit de gauche à droite (du sommet "DEBUT" à celui de "FIN").

FIGURE 3.6 - Principe MPM

3.4 Modélisation d'un problème d'ordonnancement par la PL

L'importance de l'optimisation et la nécessite d'un outil simple pour modéliser des problèmes de décision que soit économique, militaire ou autres on fait de la programmation linéaire un des champs de recherche les plus actifs au milieu du siècle précédent. Les premiers travaux (1947) sont celle de George B. Dantzig et ses associés du département des forces de l'air des Etats Unis d'Amérique. Les problèmes de programmations linéaires sont généralement liés à des problèmes d'allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit ou de minimiser un coût. Le terme meilleur fait réfrence à la possibilité d'avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces décisions sont en général le résultat d'un problème mathématique. [28]

3.4.1 Composants d'un problème d'optimisation linéaire

Tous les programmes linéaires comportent trois éléments capitaux:

-Variables de décision : ce sur quoi porte la décision, ce qui permet d'exprimer les contraintes et la fonction objectif.

-Fonction objectif: elle sert de critère pour déterminer la meilleure solution à un problème d'optimisation. À chaque variable de décision, correspond un coeffecient

29

Chapitre 3.Les outils de modélisation et les méthodes de résolution

économique indiquant la contribution unitaire de la variable correspondante à l'ob-jectif poursuivi.

-Les contraintes : dans la problèmatique de la décision, il faut être en mesure d'iden-tifier tout genre de restriction (main d'oeuvre, espace, budget,...) qui peut limiter les valeurs que peuvent prendre les variables de décision. Existe-t-il également des restrictions ou exigences minimales sur les variables de décision (contraintes du marché, politique de l'entreprise,...). À chaque restriction, limitation ou exigences, correspond habituellement une contrainte qui prendra la forme d'une équation. L'en-semble des contraintes ainsi formulées constitue le domaine des solutions possibles au modèle.

Définition

Un problème de programmation linéaire (P) est un problème d'optimisation où la fonction objectif à plusieurs variables et les contraintes sont toutes linéaires. Sa forme générale est la suivante :

?

?

?

(P)

Z(max) = C.x . . . (1) A.x = b ...(2)

x = 0 ...(3)

avec:

A : m × n - matrices des contraintes. b : vecteur colonne (second membre). e : vecteur ligne (vecteur des coûts). x : vecteur colonne.

(P) est appelé un programme linéaire. On note D(P) le domaine formé par (2) et (3).

Donc, un programme linéaire a pour but de résoudre un problème d'optimisation dans lequel:

· Les contraintes (2) e (3) délimitent dans un espace de n dimensions (le nombre de variables), s'ils sont compatibles, un hyper volume convexe dont à l'intérieur on peut trouver le (ou les) point(s) qui satisfai(en)t la fonction objectif (1).

3.4.2 Programmation linéaire en nombres entiers (PLNE)

Le terme programmation linéaire suppose que les solutions à trouver doivent être représentées en variables réelles. S'il est nécessaire d'utiliser des variables discrètes dans la modélisation du problème, on parle alors de programmation linéaire en nombres entiers (PLNE). Il est important de savoir que ces derniers sont nettement plus difficiles à résoudre que les PL à variables continues.

Chapitre 3.Les outils de modélisation et les méthodes de résolution

Définition

Etant donné une matrice A d'ordre (m x n), un vecteur colonne b et un vecteur ligne c, on appelle un programme linéaire en nombres entiers le problème suivant:

(PLNE)

? ? ?

Z(max) = C.x A.x < b x E N j = 1,2,..,n

30

Dans le cas où les variables x E {0, 1} , on dit un programme linéaire en variable bivalentes.

3.5 Conclusion

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

31

Chapitre4

Modélisation du problème posé

4.1 Introduction

Parmi les outils de modélisation étudiés dans le chapitre précèdent et compte tenu des informations recueillies au sein de l'entreprise, la meilleure méthode de modélisation de la problématique est la programmation linéaire.

Nous présentons dans ce chapitre, en premier lieu, la problématique, ensuite le modèle associé au problème déduit à partir de l'application d' outils et techniques mathématiques.

4.2 Problématique

Toute entreprise en général a besoin d'un plan pour organiser et structurer son travail ainsi qu'a veiller à sa bonne réalisation. Ceux qui est le cas de Sonatarch.

En effet, la Sonatrach possède un systéme intégré de planification et de gestion de la performance qui est un outil qui contribue à son pilotage stratégique. C'est au sein de ce système que se définit la méthodologie d'élaboration de la stratégie et de la planification à long terme, le choix des indicateurs clé de performance à mettre en place et la définition des cibles, puis la planification des prévisions à court terme. C'est aussi dans ce système que se fait le suivi des réalisations et la préparation des informations fournies au top management et nécessaires à la prise de décision pour l'amélioration des performances.

Ce système se compose de 7 processus suivants :

- Planification long terme,

- Stratégie Court et long terme,

- Fixation des objectifs annuels,

- Planification à court et Moyen terme,

32

Chapitre 4.Modélisation du problème posé

- Suivi des réalisations annuelles,

- Suivi des performances annuelles

- Analyse des écarts et plan d'actions d'amélioration.

Le système s'illustre comme ceci:

FIGURE 4.1 - Le Macro-processus du système de planification et de gestion de la performance

La durée de ce système, élaboré par la Direction SPE, vise à ne pas dépasser 2 années (730 jours), 1 année pour la planification et 1 année pour la réalisation. Or lors de son exécution, le processus prend plus que prévu par la norme (3 mois de retard).

Comme il s'agit d'un processus à visée décisionnelle, les délais revêtent une importance capitale. Un besoin existe pour optimiser au maximum le délai total de traitement. L'interpretation du problème consiste donc à minimiser la durée de ce système.

L'objectif de ce chapitre consiste alors à élaborer un modèle mathématique adéquat pour établir un ordonnancement optimal des tâches à exécuter dans le plan afin d'optimiser sur le temps.

33

Chapitre 4.Modélisation du problème posé

4.3 Formulation mathématique

Avant d'entamer la modélisation, nous allons d'abord présenter l'ensemble des outils pris en considération durant notre présente étude.

4.3.1 Les hypothèses

· Le système se compose de sept (7) processus qui sont liés entre eux.

· Chaque processus contient un ensemble de tâches.

· Une tâche peut contenir des sous - tâches élémentaires.

· Une tâche peut commencer avant que la tâche précédente ne soit terminée.

· Chaque tâche a une durée connue avec certitude.

· Les tâches sont liées entre elles par des relations d'antériorité.

· Il existe des temps d'attente entre certaines tâches.

· Certaines tâches possèdent des dates de début et de fin imposées par l'orga-nisme.

4.3.2 Les indices

· i : indice tâche i = 1, ..., N

· j : indice tâche j = 1, ..., N

4.3.3 Les notations

· N : le nombre de tâches,

· d : la durée de réalisation de la tâche i,

· fi : la date à ne pas depasser de la tâche i,

· l : la date de début obligatoire de la tâche i.

· e : intervalle d'attente entre les tâches i et j.

4.3.4 Les paramètres

{ 1 si la tâche i se fait après la tâche j

R j = 0 sinon

4.3.5 Les variables de décision

Ci = Le jour du commencement de la tâche i. tmax = La durée totale du système.

34

Chapitre 4.Modélisation du problème posé

4.3.6 La fonction objectif

La fonction objectif consiste à minimiser tmax qui représente la durée totale du système.

minZ = tmax

4.3.7 Les contraintes

· La durée totale du système doit être supérieure ou égale à la date fin de la tâche i.

tmax > Ci + di `d i = 1...N (1)

· Si la tâche j précède la tâche i, la tâche i ne peut commencer que lorsque la tâche j et son intervalle d'attente soit terminée.

(2)

(3)

(4)

Rij.Ci > Rij.(Cj + dj + ej) ` di,j = 1...N

· La tâche i ne doit pas dépasser une date précise.

Ci + di < fi `d i = 1...N

· La tâche i doit commencer à une date précise.

Ci > li ` di = 1...N

Ci E N `di = 1...N (5)

ei E Z `di = 1...N (6)

tmax E N (7)

Chapitre 4.Modélisation du problème posé

(P)	? ????????????????????? ? ??????????????????????

4.3.8 Le modèle mathématique

minZ = tmax

tmax ~ Ci + di Vi = 1...N

Rij.Ci = Rij.(Cj + dj + ej) Vi,j = 1...N

Ci + di = fi Vi = 1...N

Ci ~ li Vi = 1...N

Ci E N Vi = 1...N

ei E Z Vi = 1...N
tmax E N

4.3.9 Type du modèle

La modélisation du problème nous a fourni un programme mathémathéque linéaire en nombres entiers mono-objectif.

4.3.10 Taille du modèle

Cette étape est très importante car elle permet de connaitre la taille et de s'orien-ter vers une méthode de résolution adéquate.

Nombre de variables

Le tableau suivant montre le nombre de variables associées à notre modèle:

Variables	Nombre de variables
C	Nbrtaches
tmax	1

TABLE 4.1 - Tableau représentatif du nombre de variables Nous obtenons au total: Nbrvariables = Nbrtaches + 1 variables

35

36

Chapitre 4.Modélisation du problème posé

Nombre de contraintes

Le tableau suivant montre le nombre de contraintes associés à notre modèle:

Type de contrainte	Nombre de contraintes
(1)	Nbrtaches		(2)
Nbrtaches * Nbrtaches	(3)
Nbrtaches	(4)
Nbrtaches	(5)
Nbrtaches	(6)
Nbrtaches	(7)
1

TABLE 4.2 - Tableau représentatif du nombre de contraintes

Nous obtenons au total : Nbrcontraintes = 5 * Nbrtaches + Nbrtaches * Nbrtaches + 1 contraintes.

4.4 Méthodes de résolution des PL

4.4.1 Les Méthodes exactes

Les méthodes de résolution exactes sont nombreuses et se caractérisent par le fait qu'elle permettent d'obtenir une ou plusieurs solutions. Elles se basent généralement sur une recherche complète de l'espace des combinaisons afin de trouver une solution optimale. Ces dernières sont souvent lentes et ne résolvent que des problèmes dont l'espace de recherche est petit. Tels que la programmation dynamique, séparation et évaluation, ect.

La programmation dynamique

La programation dynamique est une méthode d'optimisation qui a pour objet d'aider à prendre des décision séquentielles indépendantes les unes des autres. Le concept a été introduit au début des années 1950 par Richard Belleman. À l'époque, le terme "programmation" signifie planification et ordonnacement, elle consiste à résoudre un problème en le décomposant en sous-problème, puis à résoudre les sous-problème des plus petits aux plus grands en stockant toujours les résultats intermiédiaires.[9]

37

Chapitre 4.Modélisation du problème posé

La Méthode par séparation et évaluation (Branch and Bound)

L'algorithme de séparation et évaluations, plus connu sous son appellation anglaise Branch and Bound (B&B) est une méthode exacte, appartient à la famille de recherche arborescente qui est utilisée pour la résolution des programmes mathématiques (P). Le principe de cette méthode consiste à faire une énumération des solutions admissibles en gardant pour objectif de ne pas développer tout l'arbre de recherche en "coupant" des branches à l'aide de bornes. Le Branch-and-Bound est composé de deux étapes : évaluation et séparation. [10]

· La séparation: cette phase consiste à diviser le problème initial en plusieurs sous-problèmes qui ont chacun un ensemble de solutions réalisables, en résolvant tous les sous-problèmes et en gardant la meilleure solution on assure la résolution de notre problème initial. L'ensemble de solutions construit une hiérarchie en arbre souvent appelée arbre de décision.

· L'évaluation : l'évaluation d'un noeud de l'arbre de décision a pour but de déterminer l'optimum de l'ensemble des solutions réalisables associés au noeud en question ou bien le contraire, c'est à dire de prouver mathématiquement que cet ensemble ne contient pas de solution optimale pour la résolution du problème.

4.4.2 Les Méthodes approchées

Les méthodes de résolution approchées sont connues sous le nom d'heuristiques ou de méta-heuristiques. Elles ont pour but de trouver une solution admissible en un temps raisonnable, mais sans garantir l'optimalité de cette solution. Ces méthodes sont utilisées pour résoudre des problèmes de grandes tailles en temps de calcul acceptable.

Les heuristiques

Une heuristique est un algorithme de résolution qui fournit une solution réalisable mais pas nécessairement optimale, pour un problème d'optimisation combinatoire. La différence entre les méthodes heuristiques et les méthodes algorithmiques est que ces derniers ne nous assurent pas qu'on va arriver à un résultat en un nombre fini d'étapes.

38

Chapitre 4.Modélisation du problème posé

Les méthodes heuristiques se divisent en deux:

· Les heuristiques de constructions : le principe est la construction progressif d'une solution initiale par une suite d'instruction gloutonne en démarrant de rien. Exemple : plus proche voisin, heuristique d'insertion.

· Les heuristiques de d'amélioration : contrairement aux heuristiques de constructions, les heuristiques d'améliorations démarrent d'une solution réalisable puis l'améliorer de proche en proche. Exemple : transformation admissible, méthode de descente.

Les Méta-heuristiques

Une Méta-heuristique peut être définie comme une méthode algorithmique qui a pour stratégie de dévier et orienter le processus de recherche dans un espace de solution (souvent très grand) vers des régions riches en solutions optimales dans le but de s'approcher de cette dernière afin de déterminer des solution (presque) optimales en un temps raisonnable.

Parmi les méta-heuristiques les plus utilisées, nous trouvons :

· Recuit simulé,

· Recherche tabou,

· Algorithme génétiques,

· Algorithme de colonies de fourmis.

L'organigramme suivant résume quelques méthodes de résolutions:

Méthodes de résolution

Méthodes exactes		Méthodes approchées
Séparation et évaluation	Programmation dynamique		Heuristiques	Méta-heuristiques

FIGURE 4.2 - Organigramme récapitulatif des méthodes de résolutions

Chapitre 4.Modélisation du problème posé

4.5 La modélisation avec solveur CPLEX

4.5.1 Présentation du solveur CPLEX

CPLEX est un outil informatique d'optimisation commercialisé par IBM depuis son acquisition de l'entreprise française ILOG en 2009. Son nom fait référence au langage C et à l'algorithme du simplexe. Il est composé d'un exécutable (CPLEX interactif) et d'une bibliothèque de fonctions pouvant s'interfacer avec différents langages de programmation: C, C++, Java et Python.[20]

CPLEX Optimizer fournit des solveurs de programmation mathématique flexibles et hautes performances pour les problèmes de programmation linéaire, de programmation mixte en nombres entiers, de programmation par contraintes et de programmation à contraintes quadratiques. Ces solveurs incluent un algorithme parallèle distribué pour la programmation mixte en nombres entiers afin de tirer parti de plusieurs ordinateurs pour résoudre des problèmes difficiles.[21]

4.5.2 Le modèle en CPLEX

La résolution d'un modèle mathématique de programmation linéaire (petite taille) se fait en utilisant plusieurs méthodes, la plus connue est l'algorithme du Simplex qui a été utilisé dans plusieurs domaines. La figure suivante représente le modèle sous CPLEX :

39

FIGURE 4.3 - Modélisation du problème sous CPLEX

40

Chapitre 4.Modélisation du problème posé

4.6 Conclusion

La formulation d'un problème est une tâche délicate mais essentielle car elle conditionne la découverte de la bonne solution. Pour la première approche, il s'agit d'un problème linéaire à variables mixtes. Les problèmes d'ordonnancement sont des problèmes NP-difficiles [1], c'est-à-dire que dans le cas pratique, la complexité croît exponentiellement avec le nombre de tâches et de ressources. Toutefois, dans certains cas pratiques selon la taille du modèle, la résolution peut se faire à l'aide d'un solveur, nous allons voir si ce dernier nous fournit une solution en une durée de temps acceptable.

41

Chapitre5

Résolution du problème et implémentation

5.1 Introduction

Afin de résoudre notre problème, nous devons connaître les processus des composants du système qui sont liés entre eux, la durée de réalisation de chacune d'elle, les relations d'antériorité entre les tâches et les temps d'attente ainsi que les dates de début et fin imposées par l'organisme pour certaines tâches.

Ensuite, nous allons présenter PlanningAPP, l'application qu'on a conçue pour la réalisation de notre problème, nous implémenterons les données fournies par SPE dans celle ci.

5.2 Présentation de MATLAB

Le nom MATLAB vient de l'anglais MATrix LABoratory. Le logiciel Matlab est un logiciel de manipulation de données numériques et de programmation dont le champ d'application est essentiellement les sciences appliquées. Son objectif, par rapport aux autres langages, est de simplifier au maximum la transcription en langage informatique d'un problème mathématique en utilisant une écriture la plus proche possible du langage naturel scientifique.

Il permet de réaliser des simulations numériques basées sur des algorithmes d'ana-lyse numérique. Il peut donc être utilisé pour la résolution approchée d'équations différentielles, d'équations aux dérivées partielles ou de systèmes non linéaires, etc...

MATLAB a été développé par la société The MathWorks, MATLAB permet de manipuler des matrices, d'afficher des courbes et des données, de mettre en oeuvre des algorithmes, de créer des interfaces utilisateurs, et peut s'interfacer avec d'autres langages comme le C, C++, Java, et Fortran. Les utilisateurs de MATLAB sont de milieux très différents comme l'ingénierie, les sciences et l'économie dans un contexte

42

Chapitre 5.Résolution du problème et implémentation

aussi bien industriel que pour la recherche. L'approche matricielle de MATLAB permet de traiter les données sans aucune limitation de taille et de réaliser des calculs numériques et symboliques de façon fiable et rapide.[22]

5.2.1 Pourquoi opter pour MATLAB?

Le choix s'est porté sur l'emploi du langage du logiciel Matlab 9.0.0.341360 (R2016a), car il répond aux critères suivants:

- La maniabilité du langage : constitué d'un ensemble de possibilités faisant en sorte que le programmeur travaille avec aisance, assuré d'une part par la syntaxe du langage et d'autre part par un aspect visuel clair représentatif à la fois du détail et du global.

- Le bagage du langage : il contient une interface graphique puissante ainsi

qu'une grande variété de méthodes scientifiques implémentées (prédéfinies). - MATLAB possède une programmation facile, une continuité parmi les valeurs

entières, réelles et complexes.

- Une bibliothèque mathématique très compréhensive avec l'outil graphique qui inclut les fonctions d'interface graphique et les utilitaires.

- la possibilité de liaison avec les autres langages classiques de programmations.[12]

5.3 Collecte des données

5.3.1 Décomposition du système

Après l'étude du système de planification et de gestion de la performance, nous pouvons le décomposer en 57 tâches.

Pour des raisons de confidentialité, nous ne pouvons désigner les actions des tâches, nous les représenterons qu'avec leur codes d'action.

Chapitre 5.Résolution du problème et implémentation

Processus		Tâches		Sous-tâches
		P1.1
		P1.2
		P1.3
		P1.4
P1
		P1.5
		P1.6
		P1.7
		P1.8
		P2.1
		P2.2
		P2.3
		P2.4
P2
		P2.5
				P3.1.1
				P3.1.2
				P3.1.3
				P3.1.4
		P3.1
				P3.1.5
				P3.1.6
P3
				P3.1.7
				P3.1.8
				P3.2.1
		P3.2		P3.2.2
				P3.2.3
		P3.3
	P4.
			P4.1.1
	P4.1		P4.1.2
			P4.1.3
			P4.2.1
			P4.2.2
			P4.2.3
	P4.2		P4.2.4
			P4.2.5
			P4.2.6
			P4.2.7
P4
	P4.3
	p4.4
	p4.5
			P4.6.1
			P4.6.2
			P4.6.3
	P4.6		P4.6.4
			P4.6.5
			P4.6.6
			P4.6.7
			P4.6.8
	P5.1
	P5.2
P5
	P5.3
	P5.4
	P6.1
P6	P6.2
	P6.3
	P7.1
P7	P7.2
	P7.3

43

TABLE 5.1 - Tableau récapitulatif des tâches du système de planification et de gestion de la

performance.

Chapitre 5.Résolution du problème et implémentation

5.3.2 Détermination de la durée des tâches

Le tableau suivant exhibe les tâches du système avec leurs durées, contraintes et temps d'attente.

Tâches	Durées		Contraintes			Attente
P1.1	1		Débute le 01/06
P1.2	3		D-F
P1.3	60		D-F
P1.4	30		Paralléle			-30
P1.5	30
P1.6	7		D-F/auplustard31/01			5
P1.7	1		D-F
P1.8	2		Eventuellement
P2.1	20		D-F			3
P2.2	10		D-F
P2.3	10		D-F
P2.4	5		D-F			3
P2.5	10		D-F
P3.1.1	15		Après P2 / au plus tard 15/03			5
P3.1.2	5		D-F			5
P3.1.3	5		D-F
P3.1.4	3		D-F
P3.1.5	10		D-F
P3.1.6	10		D-F			7
P3.1.7	7		D-F
P3.1.8	5		Eventuellement
P3.2.1	30		Débute après P3.1			8
P3.2.2	20		D-F			8
P3.2.3	1		D-F
P3.3	129		Débute avec P4
P4.	90	Après P3.1		-54
P4.1.1	15	D-F		7
P4.1.2	20	D-F		7
P4.1.3	5	D-F		3
P4.2.1	30	D-F		7
P4.2.2	15	D-F		7
P4.2.3	8	D-F
P4.2.4	45	D-F		7
P4.2.5	12	D-F		7
P4.2.6	22	D-F
P4.2.7	15	D-F
P4.3	15	au plus tard 31/12
p4.4	20	D-F
p4.5	15	D-F
P4.6.1	5	D-F		7
P4.6.2	2	D-F
P4.6.3	5	D-F
P4.6.4	5	D-F
P4.6.5	1	D-F
P4.6.6	5	D-F
P4.6.7	5	D-F
P4.6.8	1	D-F
P5.1	10	D-F
P5.2	10	D-F		5
P5.3	1	D-F
P5.4	38	D-F
P6.1	15	Débute avec P5		5
P6.2	15	D-F		5
P6.3	10	D-F		7
P7.1	15	D-F		7
P7.2	15	D-F		7
P7.3	1	D-F

44

TABLE 5.2 - Tableau récapitulatif des durées, contraintes et temps d'attente des tâches du système.

D-F : Relation Début - Fin avec la tâche précédente.

Le système se fait actuellement en 821 jours (3 mois de retards).

45

Chapitre 5.Résolution du problème et implémentation

5.4 Implémentation du problème

5.4.1 Présentation d'App Designer

App Designer permet de créer des applications professionnelles, il fournit un environnement de développement interactif permettant de concevoir la mise en page d'une application et de programmer son comportement. Il fournit une version entièrement intégrée de l'éditeur MATLAB et un vaste ensemble de composants d'in-terface utilisateur interactifs. Il offre également un gestionnaire de grille pour organiser une interface utilisateur et des options de reflux automatique pour que l'ap-plication détecte et réponde aux changements de taille de l'écran. Il vous permet de distribuer des applications en les empaquetant dans des fichiers d'installation directement à partir de la barre d'outils de l'App Designer, ou en créant une application de bureau ou web autonome (nécessite MATLAB CompilerTM). [23]

FIGURE 5.1 - La bibliothèque de composants d'App Designer

5.4.2 Présentation de l'application

L'application "PlanningAPP" est destinée à établir un ordonnancement des tâches du système de planification et de gestion de la performance. En effet, après avoir saisi les données requises, elle permettra à l'utilisateur d'avoir les dates de début et fin de chaque tâche du système, ainsi que la durée totale optimisée de ce dernier.

46

Chapitre 5.Résolution du problème et implémentation

5.4.3 Fonctionnement de PlanningAPP

Lors du lancement de l'application, la fenêtre ci-dessous apparaitra, elle contient deux champs à remplir ainsi que deux boutons:

FIGURE 5.2 - Identification

-- Les champs d'authentification : la connexion à l'application se fait par la saisie d'un nom d'utilisateur et un mot de passe définit par défaut (nom d'uti-lisateur: admin, mot de passe : ROMARIN)

-- Bouton Connexion : permet d'accéder aux fonctionnalités de l'application une fois le nom d'utilisateur et le mot de passe correct sont insérés, si ces derniers sont incorrects, un message d'erreur s'affichera.

FIGURE 5.3 - Message d'erreur

-- Bouton À propos : le bouton À propos sert à afficher les informations essentielles sur les concepteurs de l'application.

47

Chapitre 5.Résolution du problème et implémentation

FIGURE 5.4 - Bouton À propos

Une fois connecté dans l'application, voici la fenêtre qui apparaitra :

FIGURE 5.5 - Fenêtre d'accueil

-- Fenêtre Importer un document Excel : cette fenêtre contient un bouton «...» qui permet d'importer un document Excel contenant la matrice de prédécesseurs, la durée, la date limite à ne pas dépasser,la date de début obligatoire pour chaque tâche ainsi que l'intervalle d'attente entre les tâches.

48

Chapitre 5.Résolution du problème et implémentation

FIGURE 5.6 - Bouton «...»

FIGURE 5.7 - Fichier Excel importé

Le bouton Aide explique à l'utilisateur comment préparer son fichier Excel pour ne pas y avoir d'erreurs lors du traitement de données.

49

Chapitre 5.Résolution du problème et implémentation

FIGURE 5.8 - Bouton Aide

Une fois le document Excel, contenant les données, a été choisi, l'utilisateur cliquera sur le bouton Résultats.

5.4.4 Présentation du résultat et commentaires

Après implémentation des données de SPE, le résultat final sera présenté analytiquement sur un tableau comme nous le montre la figure suivante:

FIGURE 5.9 - Tableau résultats

En cliquant sur : Importer dans Excel, l'application affichera les résultats dans Excel sous forme de tableau avec les dates de début, durées, dates de fin et une solution graphique avec le diagramme de GANTT, comme nous le montre les figures suivantes:

Chapitre 5.Résolution du problème et implémentation

La durée Totale du Syatè me eut 700 loura

04/05/2021 12/08/2021 20/11/2021 20/02/2022 08/06/2022 16/09/2022 25/12/2022 04/04/2023 13/07/2023

P13 P15 P1.7 P2.1 P22 P25 P3.1.2

P3.1.8

P33 P4.1.1 P0.1.3 P42.2 P4.2.4 P0.2.6 P43 P4.5 P4 fi.2 P46.4 P46.6 P4 fi.8 P5.2 P5A 2.6.2 P7.1 P73

Dare de début
·Durée

Itl

riches Date de début Durée Date de fin

P1.1	01/06/2021	1	02/05/2021
P1.2	12/0612021	3	05/06/2021
P1.3	05/0612021	60	04/08/2021
P1.4	D4/08/2021	3D	03/09/2021
P1.5	D4/08/2021	3D	03/09/2021
P1.6	03/09/2021	7	10/09/2021
P1.7	15/09/2021	1	15/09/2021
P1.8	16/09/2021	2	10/09/2021
P2.1	18/09/2021	20	08/10/2021
P2.2	11/10/2021	10	21/10/2021
P2.3	21/10/2021	10	31/10/2021
P2.4	31/10/2021	5	05/11/2021
P2.5	D8/11/2021	10	18/11/2021
P3.1.1	18/11/2021	15	03/12/2021
P3.1.2	58/12/20215		13/12/2021
P3.1.3	18/12/20215		23/12/2021
P3.1.4	23/12/20213		25/12/2021
P3.1.5	26/12/2021	10	05/01/2022
P3.1.6	D5/01/2022	10	15/01/2022
P3.1.7	22/01/20227		29/01/2022
P3.1.8	29/01/20225		03/02/2022
P3.2.1	03/02/2022	30	05/03/2022
P3.2.2	13/03/2022	20	02/04/2022
P3.2.3	53/05/20221		04/05/2022
P3.3	D4/05/2022	129	10/09/2022
P4.	03/02/2022	90	04/05/2022
P4.1.1	11/03/2022	15	26/03/2022
P4.1.2	02/04/2022	20	22/04/2022
P4.1.3	29/04/20225		04/05/2022
P4.2.1	04/05/2022	30	03/06/2022

10106_{2072 15 25/06/2027

Solution Feuill 0

50

FIGURE 5.10 - Résultats sous Excel

Tâches	Date de début	Durée	Date de fin
P1.1	01/05/2021	1	02/06/2021
P1.2	02/05/2021	3	05/06/2021
P1.3	05/06/2021	60	04/08/2021
P1.4	04/08/2021	30	03/09/2021
P1.5	04/08/2021	30	03/09/2021
P1.6	03/09/2021	7	10/09/2021
P1.7	15/09/2021	1	16/09/2021
P1.8	16/09/2021	2	18/09/2021
P2.1	18/09/2021	20	08/10/2021
P2.2	11/10/2021	10	21/10/2021
P2.3	21/10/2021	10	31/10/2021
P2.4	31/10/2021	5	05/11/2021
P2.5	08/11/2021	10	18/11/2021
P3.1.1	18/11/2021	15	03/12/2021
P3.1.2	08/12/2021	5	13/12/2021
P3.1.3	18/12/2021	5	23/12/2021
P3.1.4	23/12/2021	3	26/12/2021
P3.1.5	26/12/2021	10	05/01/2022
P3.1.6	05/01/2022	10	15/01/2022
P3.1.7	22/01/2022	7	29/01/2022
P3.1.8	29/01/2022	5	03/02/2022
P3.2.1	03/02/2022	30	05/03/2022
P3.2.2	13/03/2022	20	02/04/2022
P3.2.3	03/05/2022	1	04/05/2022
P3.3	04/05/2022	129	10/09/2022
P4.	03/02/2022	90	04/05/2022
P4.1.1	11/03/2022	15	26/03/2022
P4.1.2	02/04/2022	20	22/04/2022
P4.1.3	29/04/2022	5	04/05/2022
P4.2.1	04/05/2022	30	03/06/2022
P4.2.2	10/06/2022	15	25/06/2022

FIGURE 5.11 - Tableau résultats 1

Chapitre 5.Résolution du problème et implémentation

FIGURE 5.12 - Tableau résultats 2

51

FIGURE 5.13 - La durée totale du système

52

Chapitre 5.Résolution du problème et implémentation

FIGURE 5.14 - Solution graphique avec diagramme de GANTT

Discussion des résultats

D'après les données de SPE, le système se faisait en 821 jours . Il enregistrait un retard de 91 jours (soit environs 3 mois) par rappport à la date limite qui est de 730 jours . Le résultat obtenu en faisant appel aux fonctions du solveur CPLEX, qui est une méthode exacte, nous donne une solution optimale de : 700 jours.

Ce résultat diminue la durée totale du système de planification et de gestion de la performance d'environs 15% soit 121 jours. Il élimine, d'un coté, le retard enregistré et de l'autre coté, il dégage un gain appréciable en matière de temps par rapport à la date limite et par voie de consequence un gain en matière de coût et performance.

5.5 Conclusion

Dans ce dernier chapitre, nous avons abordé l'implémentation des données de SPE dans notre PlanningAPP.

Nous avons commencé en premier lieu par la présentation du langage MATLAB et les raisons de son choix. Ensuite, nous avons présenté les données recueillies au sein de l'entreprise ainsi que l'application PlanningAPP et enfin, nous avons fait l'implémentation des données dans notre application et comparé les résultats trouvés avec ceux de la SONATRACH.

53

Conclusion générale

Ce mémoire qui s'inscrit dans le domaine de l'amélioration des performances des entreprises a pour objectif principal la résolution des problèmes d'ordonnancement avec l'utilisation des méthodes et techniques de la recherche opérationnelle.

Le travail qui nous a été confié par l'entreprise SONATRACH avait pour but essentiel d'apporter les meilleurs résultats en matière de temps lors de la réalisation d'un cycle complet dans un système intégré de planification et de gestion de la performance.

Pour ce faire, notre travail a débuté en premier lieu par la compréhension du contexte de notre projet et l'influence de la planification sur la performance de l'en-treprise suivi d'une étude sur les méthodes d'ordonnancement et les techniques de modélisation des problèmes d'ordonnancement.

Après avoir pris connaissance des différentes contraintes intervenant lors de la réalisation du système, nous avons modélisé notre problème mathématiquement en gardant pour seul objectif la minimisation du temps.

A ce fait, une application appelée PlanningAPP a été créée pour la résolution du problème qui consiste à faire appel à des fonctions du solveur CPLEX. Cette application permet à l'utilisateur d'implémenter les données en important un document Excel.

En conclusion, nous pouvons dire que notre objectif assigné au début de notre travail a été atteint car nous avons pu minimiser les délais de la réalisation d'un cycle complet dans un système intégré de planification et de gestion de la performance.

54

Cependant, d'autres perspectives et développements pourraient être inscrits pour une meilleure appréciation de l'application à citer, à titre d'exemple:

-- Ajouter la contrainte des ressources humaines, -- Ajouter la contrainte de ressources financières.

Pour finir, ce projet nous a permis d'acquérir une très bonne expérience professionnelle dans notre domaine et nous espérons que ce résultat sera bénéfique pour l'entreprise.

55

Bibliographie

[1] J.CARLIER et P.CHRETIENNE : Problèmes d'ordonnacement, modélisa-tion,complexité,algorithmes, MASSON, ISBN 2-225-81275-6.

[2] P.LOPEZ Approche par contraintes de problèmes d'ordonnancement et d'af-fectation: structures temporelles et mécanismes de propagation, Thèse d'ha-bilitation à diriger des recherches, Institut polytechnique de Toulouse, 2003.

[3] BELHARRAT.N et Collectif ,«La recherche Opérationnelle,(théorie des graphes) », ALGERIE,Livre la pages blue, 2005.

[4] A. YEZZA. Que signifient AON et AOA?, thèse Doctorat, avril 2011 / mise à jour oct 2012.

[5] E. SAULE, P-F. DUTOT et G. MOUNIE : Scheduling With Storage Constraints. In Electronic proceedings of IPDPS 2008, Miami, Florida USA, APR 2008.

[6] E. DEMEULEMEESTER, J.BEEIEN, Operating room planning and scheduling: literature review, European Journal of Operational Research, 2010.

[7] G. FINK, Recherche opérationnelle et réseaux, Lavoisier, Paris, 2002.

[8] A. HAIT, C. ARTIGUES, P. BAPPTISTE et M. TREPANIER : Ordonnancement sous contraintes d'énergie et de ressources humaines. In : 11ème congrès de la société française de Génie des Procédés Octobre 2007, Saint-Etienne, France.

[9] BELLMAN, RICHARD, Eye of the Hurricane : An Autobiography. World Scientific Pub Co Inc, 1984, 344p.

[10] LAND A.H., DOIG A.G., «Econometrica», An Automatic Method ofSolving Dis-crete Programming Problems, Juillet 1960, Vol 28, n°3, pp.497-520.

[11] YENDE, RAPHAEL, Cours de methodes de conduite des projets informatique, 2019. Thèse de doctorat. institut supérieur de commerce. Page 59.

[12] RADI, BOUCHAÏB et EL HAMI, ABDELKHALEK. Méthodes numériques avancées sous Matlab® 1 : Approximation des fonctions et résolutions des systèmes linéaires. ISTE Group, 2018.

[13] ISSOR, ZINEB. La performance de l'entreprise : un concept complexe aux multiples dimensions. Projectics/Proyéctica/Projectique, 2017, no 2, p. 93-103.

56

BIBLIOGRAPHIE

[14] LEBAS. M, « oui, il faut définir la performance », in revue française de comptabilité, n°269, juillet, aout, 1995, p. 66.

[15] WEISS.D.K.O, « la fonction RH », Edition d'organisation, paris, 1988, P. 675.

[16] KHEMAKHEM. A, « la dynamique de contrôle de gestion », Edition Dunod, Paris, 1992, p. 311.

Webographie

[17] www.sonatrach.com

[18] www.sonatrach.com/nos-activites

[19] www.agrireseau.net

[20] www.wikipedia.org/wiki/CPLEX

[21] www.ibm.com/fr-fr/analytics/cplex-optimizer

[22] www.wikipedia.org/wiki/MATLAB

[23] [ www.mathworks.com/help/matlab/app-designer.html

[24] www.sabbar.fr/management/la-performance-de-lentreprise/

[25] www.gantt.com/fr/

[26] www.wikipedia.org/wiki/PERT

[27] www.logistiqueconseil.org/Articles/Logistique/Methode-potentiel-metra

[28] www.hatem.masri.tripod.com/RO/CHAP1html.htm

57

Résumé

Le secteur économique de l'énergie en Algérie occupe une place Importante dans l'économie du pays. La compagnie SONATRACH est un groupe entièrement intégré sur toute la chaîne de valeur des hydrocarbures, possédant plusieurs directions où la Direction Corporate Stratégie, Planification et Economie (SPE) ( chargée de l'élaboration et le développement des plans à moyen et long terme et d'évaluer leur mise en oeuvre) occupe une place prédominante.

La planification qui est une ligne de base pour toute amélioration de la performance de l'entreprise, la Direction Corporate Stratégie, Planification et Economie (SPE) a mis en place un système intégré de planification et de gestion de la performance qui contribue fortement à son pilotage stratégique important en matière de temps.

La problématique posée dans notre projet est la minimisation des délais de réalisation d'un cycle complet dans un système intégré de planification et de gestion de la performance, une étude était nécessaire sur le contexte de notre projet et l'in-fluence de la planification sur la performance de l'entreprise afin de connaitre les composantes réelles et comprendre son mode de fonctionnement.

Dans notre cas, la méthode exacte qui consiste à faire appel à des fonctions du solveur CPLEX a été utilisée dans notre mémoire pour la résolution du problème.

Afin de mettre en évidence notre modèle, en utilisant le langage MATLAB, nous avons programmé une application appelée « PlanningAPP » qui permet à l'utilisa-teur d'implémenter les données en important un document Excel.