Problèmes d‟optimisation et leurs méthodes de résolution

Rôle de l’ordonnancement dans la gestion de production

Le modèle général en gestion de production, décompose les décisions en trois niveaux : Stratégique, tactique et opérationnel (pilotage et suivi quotidien des flux de matières et du travail). Cette hiérarchisation se traduit par une échelle de responsabilité (direction, cadre, agent, etc.) (Esquirol et Lopez 1999) Dans la mesure où des événements aléatoires tels que des pannes ou des commandes imprévues, qui peuvent survenir à tout moment, il est nécessaire de recalculer fréquemment l‟ordonnancement, il est difficile de résoudre le problème d‟ordonnancement au niveau supérieur (stratégique). Donc, il est résolu au niveau inférieur (opérationnel) (Blondel 2004) La place de l‟ordonnancement varie entre le niveau tactique et le niveau opérationnel (Herrmann 2006). Il s‟occupe de la réalisation des décisions venant de niveau supérieur. Son rôle consiste à transformer les décisions de fabrication définies par le programme directeur en instructions d‟exécution destinées à contrôler et piloter à court terme l‟activité des postes de travail. En sortie de la fonction d‟ordonnancement, nous obtienons un planning ou ordonnancement, qui restitue l‟affectation des tâches fournies en entrée à des dates précises pour des durées déterminées sur les différentes ressources. Ce planning cherche à satisfaire des objectifs, en respectant le plus possible les contraintes imposées (Javel 2004). La fonction ordonnancement se décompose en trois sous fonctions Figure 0.2 (Javel 2004) :

•L‟élaboration des ordres de fabrication (OF) : consiste à transformer les informations du programme directeur de production (suggestion de fabrication) en OF.

•L‟élaboration du planning d‟atelier : consiste à déterminer, en fonction des ordres de fabrication (OF) et de la disponibilité des ressources, le calendrier prévisionnel de fabrication.

•Le lancement et le suivi des opérations de fabrication.

La complexité problématique La complexité problématique est relative au problème à résoudre ainsi que la méthode de résolution adoptée pour élaborer la solution optimale par rapport aux critères retenus.

Un problème de décision comprend deux parties : la partie relative aux données du problème et un processus binaire ayant « oui » ou « non » comme réponse possible.

Un problème de recherche est un problème constitué d‟un ensemble de données dont chacun représente un ensemble de solutions. Donc, la résolution d‟un problème de recherche consiste à trouver pour chaque ensemble de données D des solutions S associées.

Un problème d‟optimisation est un problème de recherche en associant à chaque solution une valeur qualitative. À chaque problème d‟optimisation, nous pouvons associer un problème de décision (par exemple l‟exclusion ou l‟inclusion d‟une solution dans les futures générations pour les AG), donc l‟étude de la complexité du problème de décision peut donner des indications au problème d‟optimisation associé. (Charon 1996). La théorie de complexité permet de classer les problèmes en deux classes P et NP. La classe P regroupe les problèmes qui peuvent être résolus par des algorithmes polynomiaux. Un algorithme est dit polynomial, lorsque son temps d‟exécution est borné par O (P(x)) où P est un polynôme et x est la longueur d‟entrée d‟une instance du problème.

Les algorithmes polynomiaux représentent une classe stable et la composition de deux algorithmes polynomiaux engendre un algorithme polynomial, et un algorithme construit polynomialement à partir d‟appels à des procédures de complexité polynomiale, reste polynomial. (Lacomme, Prins et Sevaux 2003). Les algorithmes dont la complexité ne peut pas être bornée polynomialement sont qualifiés d‟exponentiels et correspondent à la classe NP „Non determinist Polynomial time‟. Les problèmes dans NP peuvent être résolus en énumérant l‟ensemble des solutions possibles et en les testant à l‟aide d‟un algorithme polynomial. Tous les problèmes de décision dont nous pouvons associer à chacun d‟eux un ensemble de solutions potentielles (de cardinal au pire exponentiel) de telle sorte qu‟il existe un algorithme polynomial qui peut vérifier, si la solution trouvée est valable ou pas. Un problème de décision est dit NP-Complet s‟il appartient à la classe NP et il est résolu, au mieux, en un temps exponentiel. Un problème d‟optimisation est dit NP-Difficile, si le problème de décision associé est NPcomplet. La Figure 0.9 montre les différentes classes de complexité.

ETAT DE L’ART

Les ateliers Job shop et Flow shop ont fait l‟objet de plusieurs études de modélisation pour la résolution des problèmes d‟ordonnancement avec temps de transport. King et al (King, Hodgson et Chafee 1993) développent un algorithme Branch and Bound pour la résolution du Flow shop avec un seul transporteur. La première modélisation du job shop avec transport a été introduite par Knust (Knust 1999). Ensuite, ce problème a été étudié avec un seul robot, par (Hurink et Knust 2002). Une modélisation sous forme de graphe disjonctif a été proposée par Hurink et al (Hurink et Knust 2005). Ce graphe est constitué de deux types de noeuds : des noeuds reflétant des opérations effectuées sur machines et des noeuds représentant des opérations de transport. Strusevich (Strusevich 1999) a introduit un décalage connu et déterministe, entre la fin d‟une opération et le début de l‟opération suivante dans le même job. Ce décalage entre deux opérations consécutives est nommé temps de transport. Récemment, L‟étude du Flow shop avec transport a fait l‟objet d‟une attention particulière (Larabi 2010) dont nous trouvons un état de l‟art proposé par Crama et al (Crama, et al. 2000).

Ces études considèrent plus particulièrement les problèmes d‟ordonnancement avec unique transporteur avec la prise en compte du transport à charge et à vide. D‟autres auteurs (Nowicki 1999) (Brucker, Heitmann et Brucker 2003) ont proposé un graph disjonctif avec une capacité du stock limitée, pour résoudre le problème d‟ordonnancement du Flow shop avec transport. Pour le job shop sous la contrainte de capacité de stockage, Caumond et al (Caumond, et al. s.d.) ont proposé un modèle linéaire mixte pour 5 jobs et 111 opérations. Plusieurs auteurs ont étudié le Job shop avec transport et plusieurs robots (Lacomme, Larabi et Tchernev 2007), (Lacomme et Larabi 2008), (Lacomme, Larabi et Tchernev 2013). Burgy et al (Bürgy et Gröflin 2016) ont proposé une formulation pour le problème du Job shop avec un système de transport nommé rail-bound. Ces auteurs ont développé une recherche locale pour résoudre le problème. Zeng et al (Zeng, Tang et Yanb 2014) ont étudié le même problème mais avec un nombre limité de transporteurs. Ces auteurs ont proposé une heuristique à deux niveaux.

Un algorithme nommé iterative greedy insertion technique a été propose par Bekar et al pour le job shop flexible avec transport (Bekkar, et al. 2016). Ces auteurs ont travaillé sur AIPPREMICA (Trentesaux, et al. 2013), reflétant une cellule réelle du job shop flexible. Cette technique est très populaire pour résoudre les problèmes d‟optimisation combinatoires (Talb 2009). Elle fonctionne d‟une manière récursive et destructive. Chaque itération écrase sa précédente, jusqu’à ce que l‟optimum local soit trouvé. Généralement, le problème d‟ordonnancement du Job shop sous des contraintes de transport repose sur un ensemble de robots identiques, transportant les jobs entre machines. En revanche, dans le job shop flexible, le transfère peut demander plus de distance (Afsar, et al. 2016). Ainsi, il est plus probable que le transfère est effectué par des véhicule ayant une plus grande capacité. Nous proposons un algorithme génétique hybride, basé sur la recherche tabou pour la cellule de montage des pièces AIP-PREMICA (Trentesaux, et al. 2013), qui reflète une cellule réelle du problème job shop flexible avec transport. Une fonction de voisinage est proposée pour la recherche tabou. Dans la section suivante, nous présentons une formalisation mathématique du problème job shop flexible avec transport.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

INTRODUCTION GÉNÉRALE
NOTATION
Chapitre 1 : L‟ordonnancement et ses caractéristiques dans les systèmes de production
1.INTRODUCTION
2.LES SYSTEMES DE PRODUCTION
3.LA GESTION DE PRODUCTION
3.1 Définition et rôle de la gestion de production
3.2 Décomposition hiérarchique de la gestion de production
3.3 Rôle de l‟ordonnancement dans la gestion de production
4.LES PROBLEMES D‟ORDONNANCEMENT
4.1 Définition de l‟ordonnancement
4.2 Ordonnancement des ateliers
5.CLASSIFICATION DES ATELIERS
6.COMPLEXITE
6.1 La complexité algorithmique
6.2 La complexité problématique
7.CLASSIFICATION D‟ORDONNANCEMENT
7.1 Classification des problèmes d‟ordonnancement
7.1.1 Ordonnancement admissible
7.1.2 Ordonnancement semi-actif
7.1.3 Ordonnancement actif
7.1.4 Ordonnancement sans délais
7.2 L‟ordonnancement sous l‟incertitude
8.Modélisation et représentation des problèmes d‟ordonnancement
8.1 Notations
8.2 Modélisation
8.2.1 La modélisation graphique
8.2.2 La modélisation mathématique
8.3 Représentation des solutions
9.Particularités d‟ordonnancement dans les ateliers Job Shop Flexibles
CONCLUSION
Chapitre 2 : Problèmes d‟optimisation et leurs méthodes de résolution
1.INTRODUCTION
2.NOTIONS RELATIVES AUX PROBLEMES D‟OPTIMISATION
2.1 La fonction objectif
2.2 Les variables de décision
2.3 Les types de minima
2.4 Les problèmes mono-objectifs et multi-objectifs
2.5 Notion de dominance
3.METHODES DE RESOLUTION DES PROBLEMES D‟OPTIMISATION
3.1 Les méthodes exactes
3.1.1 La méthode branch & bound.
3.1.2 La programmation linéaire
3.1.3 La programmation dynamique
3.2 Les méthodes approximatives
3.2.1 Les heuristiques
3.2.2 Les Méta-heuristiques
4.L‟OPTIMISATION MULTI-OBJECTIF ET LES ALGORITHMES GENETIQUES
4.1. La méthode M.O.GA (Multiple Objective Genetic Algorithm)
4.2. La méthode NSGA (Non Dominated Sorting Genetic Algorithm)
4.3. La méthode SPEA (Strenght Pareto Evolutionary Algorithm)
4.4. La méthode PAES (The Pareto Archived Evolution Strategy)
5.classification des APPROCHES DE RESOLUTION DES PROBLEMES JOB SHOP Flexible
CONCLUSION
Chapitre 3 : Le problème job shop flexible avec transport
1.INTRODUCTION
2.Etat de l‟art
3.FORMULATION DU PROBLEME
4.L‟APPROCHE D‟OPTIMISATION PROPOSEE
5.LA RECHERCHE TABOU
5.1. Les fonctions de voisinage
5.2. Contribution : la fonction de voisinage proposée
5.2.1. L‟algorithme a pour l‟optimisation basée sur les fenêtres libres
5.2.2. L‟algorithme b pour l‟optimisation basee sur les fenetres occupees
5.2.3. L‟algorithme de la recherche tabou (TS)
6.L‟ALGORITHME GENETIQUE
6.1. La population initiale
6.2. Codage de chromosome
6.3. Evaluation des chromosomes
6.4. Sélection
6.5. Croisement
6.6. Mutation
6.6.1. Mutation d‟assignement
6.6.2. Mutation de séquencement
6.7. Remplacement et élitisme
6.8. Les paramètres de l‟algorithme génétique
7.CAS D‟ETUDE : AIP-PRMECA
7.1. Les données sur les produits
7.2. Les données sur les ressources
7.3. Les données sur le système de transport
7.EXPERIMENTATIONS ET RESULTATS
CONCLUSION
Chapitre 4 : Une approche prédictive réactive pour le contrôle d‟énergie pour le job shop flexible
1.INTRODUCTION
2.Etat de l‟art sur l‟ordonnancement et le contrôle de l‟énergie
3.UNE METHODE PREDICTIVE–REACTIVE POUR LE contrôle DE L‟ENERGIE
3.1. Une méthode prédictive pour le contrôle de l‟énergie basée sur NSGA-2
3.1.1. Le modèle de Contrôle d‟énergie
3.1.2. L‟algorithme de l‟ordonnancement : NSGA-2
3.2. Méthode réactive pour le contrôle de l‟énergie
3.2. Contrôle de perte d‟énergie
4.LE CAS D‟ETUDE
5.EXPERIMENTATIONS ET RESULTATS
Conclusion
Conclusion générale
PERSPECTIVES
Bibliographie