Le Flow-Shop sous contraintes de resources non-renouvelables

La gestion de production

  Face aux défis de la mondialisation et de la concurrence, les entreprises industrielles sont obligées de réadapter leur système de production en vue d’augmenter la qualité de leur produit, de mieux gérer leurs ressources, de diminuer leur coût de revient et d’augmenter leur flexibilité afin de rester compétitif.La gestion de production apparaît donc comme le guide indispensable de l’entreprise industrielle pour la réalisation de cet objectif. En effet, une telle gestion doit organiser le fonctionnement du système de production et de mieux gérer ses différents composants. Les systèmes de production peuvent être vus comme un ensemble de ressources divers (matériels, humains, etc.) qui interagissent et interfèrent dans le but de produire des biens ou services.Ces derniers peuvent être des systèmes très complexes et difficiles à gérer au vu de toutes leurs composantes fonctionnelles (fabrication, achat, distribution, maintenance…) [81]. À cet égard, plusieurs approches ont été envisagées dans le but de mieux comprendre leur fonctionnement et de mieux les appréhender. L’application de la théorie des systèmes aux systèmes de production suggère une décomposition de ces derniers en trois sous-systèmes : le sous-système physique de production, le sous-système de décision et le sous-système d’information qui s’intègrent afin d’assurer la pérennité et la compétitivité de l’entreprise industrielle comme illustrée dans la figure 1.1.
— Le sous-système physique de production englobe tout les ressources humaines et physiques nécessaires pour la transformation des matières premières en produits finis.
— Le sous-système de décision contrôle le système physique de production à travers l’organisation des différentes activités en prenant des décisions basées sur les données transmises par le sous-système d’information.
— Le sous-système d’information intervient à plusieurs endroits, entre les sous-systèmes de décision et de production et à l’intérieur même du sous-système de décision, pour la gestion des informations utilisées lors de prises de décision, et du sous-système physique de production, pour la création et le stockage d’informations de suivi par exemple [81]. Donc, son rôle peut se résumer a la collecte, le stockage, le traitement et la transmission d’informations.Les deux sous-systèmes décisionnels et informationnels traitent les fonctions rattachées directement à la production à savoir, la gestion de stock, la gestion des ressources, la maintenance, la planification, etc. L’association de ces deux derniers sous-systèmes constitue le système de gestion de production, évoqué dans cette section. En fait, la gestion de production assure l’organisation du système de production afin de fabriquer les produits en quantités et qualités définies, ainsi dans un temps voulus compte tenu des moyens humains ou technologiques disponibles.L’objectif de la gestion de production est de gérer les systèmes de production au mieux. Cette gestion s’effectue par un ensemble de décisions qui peuvent être hiérarchisées suivant des granularités et des horizons temporels différents. Ces décisions sont habituellement classées selon trois catégories introduites par Anthony [4] et reprises dans [135] en gestion de production, à savoir : les décisions stratégiques, tactiques et opérationnelles.

L’ordonnancement de la production

  La théorie d’ordonnancement est une branche de la recherche opérationnelle, qui consiste à ordonner un ensemble d’opérations tout en satisfaisant un ensemble de contraintes et en optimisant un ou plusieurs objectives. L’ordonnancement joue un rôle essentiel dans de nombreux secteurs d’activités à savoir, en : informatique (ordonnancement de processus), administration (établissement d’un emploi du temps, gestion des ressources humaines), industrie (gestion des ateliers de production), construction (gestion des chantiers routiers), logistique (gestion des livraisons et des stocks). Parmi ces nombreux types de problèmes d’ordonnancement, nous nous sommes intéressés dans le cadre de cette thèse aux problèmes d’ordonnancement d’ateliers dans les systèmes de production. Un atelier de production est un espace physique où la fabrication se déroule. Il est composé de ressources humaines et matérielles, et caractérisé par les types de tâches à exécuté, les type de ressources et la gamme de fabrication, que nous présentons en détail dans les sous-sections suivantes. Nombreuses sont les définitions proposées au problème d’ordonnancement d’atelier, nous tirons de la littérature les trois définitions ci-dessous :
Definition Scheduling is the process of organizing, choosing, and timing resource usage to carry out all the activities necessary to produce the desired outputs at the desired times, while satisfying a large number of time and relationship constraints among the activities and the resources.
Definition Scheduling is concerned with the allocation of scarce resources to activities with the objective of optimizing one or more performance measure.
Definition Scheduling is a decision-making process that is used on a regular basis in many manufacturing and services industries. It deals with the allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives. D’après les définitions ci-dessus, on retrouve l’aspect commun de l’affectation de ressources aux tâches. Donc nous pouvons dire que l’ordonnancement d’ateliers consiste à programmer dans le temps l’exécution des tâches selon la disponibilité des ressources pour répondre à un ou plusieurs d’objectifs, tout en respectant les contraintes techniques de fabrication.

Les ressources

   Une ressource est un moyen technique ou humain utilisé pour la réalisation d’une tâche et disponible en quantité limitée. Dans un atelier, plusieurs types de ressources sont distingués.
1. Selon leurs disponibilités au cours du temps, on trouve :
— Les ressources renouvelables, comme c’est le cas pour les machines, personnels, équipements, etc. La ressource est dite renouvelable si après avoir été utilisé par une ou plusieurs opérations, elle est à nouveau disponible en même quantité.
— Les ressources non-renouvelables, souvent appelées ressources consommables ou bien ressources financières. On dit que la ressource est non-renouvelables si ça disponibilité décroît après avoir été allouée à une opération. C’est le cas pour la matière première, budget.
— Les ressources doublement contraintes, ces ressources combinent les contraintes liées aux deux catégories précédentes. Leur utilisation instantanées et leur consommation globale sont toutes les deux limitées. C’est le cas des ressources d’énergie (pétrole, électricité, etc.).
2. Selon leurs capacités, on trouve :
— Les ressources disjonctives (ou non-partageables), il s’agit des ressources qui ne peuvent exécuter qu’une seule opération à la fois c’est le cas par exemple de machine-outil ou robot manipulateur.
— Les ressources cumulatives (ou partageables), il s’agit des ressources qui peuvent être utilisé par plusieurs opérations simultanément (équipes d’ouvriers, poste de travail, etc.).

Complexité algorithmique

   La complexité algorithmique est un concept fondamental qui permet de mesurer les performances d’un algorithme. Ces performances sont évaluées sur la base du temps alloué pour l’exécution de l’algorithme ou encore par rapport à l’espace mémoire requis pour résoudre le problème.Généralement, le temps d’exécution est le facteur dominant pour déterminer l’efficacité d’un algorithme, pour cela, on se concentre principalement sur ce facteur. La complexité temporelle d’un algorithme représente le nombre maximum d’opérations élémentaires effectuées pour résoudre un problème donné. Cette complexité se base essentiellement sur la mesure d’un ordre de grandeur qui est évalué en fonction de la taille du problème n. La notation O est utilisé pour représenter cet ordre de grandeur. Par exemple, pour un algorithme donné,si la solution est donnée en environ n opérations, on dit que l’algorithme a une complexité enO(n).
Definition Un algorithme est dit polynomiale si pour tout n, l’algorithme s’exécute en moins de n k opérations élémentaires (k étant une constante). En d’autres termes, un algorithme polynomial est un algorithme dont la complexité temporelle est bornée par un polynôme p de n, O(p(n)) : par exemple O(n k ) avec k une constante.
Definition Un algorithme est dit non-polynomial si le nombre d’opérations n’est pas borné par un polynôme de n. En d’autres termes, si le nombre d’opérations est borné par une forme exponentielle de la taille de problème alors l’algorithme est dit non-polynomial ou exponentiel : par exemple O(a n ) avec a > 1 une constante.

Méthode de séparation et évaluation

   La méthode de séparation et évaluation, plus connue sous son appellation anglaise Branch and Bound (B & B) est considérée parmi les méthodes exactes les plus reconnues dans la résolution optimale des problèmes d’optimisation combinatoires. Cette méthode est basée sur  une énumération implicite et intelligente de l’ensemble des solutions, mais l’analyse des propriétés du problème évite l’énumération de larges classes ne contenant pas de solution optimale. En d’autres termes, seulement les solutions potentiellement bonnes seront énumérées. Le principe de cette méthode repose comme son nom l’indique sur deux notions clé : la séparation et l’évaluation. La séparation consiste à décomposer l’ensemble des solutions en plusieurs sous-ensembles qui sont décomposés à leur tour selon une démarche itérative. Ce processus peut se visualiser sous la forme d’un arbre d’énumération ou les nœuds de l’arbre correspondent aux sous-ensembles et les feuilles correspondent à des solutions réalisables. Pour accélérer la recherche de la solution optimale en évitant l’exploration inutile de certains nœuds, on utilise une procédure d’évaluation. Cette dernière réduit le nombre de solutions explorées en permettant de prouver mathématiquement que l’ensemble des solutions réalisables associées à un des nœuds de l’arbre ne contient pas une solution intéressante pour le problème initial. Pour cela, la méthode la plus générale consiste à déterminer une borne inférieure (dans le cas des problèmes de minimisation) ou une propriété de dominance pour confirmer qu’une branche ne contient pas de solution optimale. Cette méthode a été introduite pour la première fois par Dantzig et al. [28] pour la résolution du problème du voyageur de commerce. Depuis, des centaines, voire des milliers de procédures par séparation et évaluation ont été proposées pour des problèmes d’ordonnancement dont on peut citer [20, 89].

Table des matières

I Ordonnancement de la production, optimisation et état de l’art 
1 Ordonnancement de production 
1.1 La gestion de production
1.1.1 Décisions stratégiques
1.1.2 Décisions tactiques
1.1.3 Décisions opérationnelles
1.2 L’ordonnancement de la production
1.2.1 Formulation d’un problème d’ordonnancement
1.2.1.1 Les tâches
1.2.1.2 Les ressources
1.2.1.3 Les contraintes
1.2.1.4 Les objectifs
1.2.2 Typologie des problèmes d’ordonnancements
1.2.2.1 Problèmes à une opération
1.2.2.2 Problèmes à plus d’une opération
1.2.3 Formalisation des problèmes d’ordonnancements
1.2.3.1 Classification et notation
1.2.3.2 Modélisation
1.2.3.3 Représentation des solutions
1.3 La théorie de la complexité
1.3.1 Complexité algorithmique
1.3.2 Complexité problématique
1.3.3 Hiérarchie de complexité pour les problèmes d’ordonnancement
1.4 Conclusion
2 Techniques d’optimisation
2.1 Méthodes exactes
2.1.1 Méthode de séparation et évaluation
2.1.2 Programmation dynamique
2.1.3 Programmation linéaire
2.2 Méthodes approchées
2.2.1 Heuristiques
2.2.2 Metaheuristiques
2.2.2.1 Métaheuristiques à solution unique
2.2.2.2 Métaheuristiques à base de population
2.3 Méthodes hybrides
2.4 Conclusion
3 Revue de la littérature 
3.1 État de l’art sur les problèmes d’ordonnancement sous contraintes de ressources non-renouvelables
3.2 Identification de problème et objectif de la thèse
3.3 Conclusion
II Le Flow-Shop sous contraintes de resources non-renouvelables : Modélisation mathématique et méthodes de résolution 
4 Méthode de résolution exacte 
4.1 Le Flow-Shop sous contraintes de ressources non-renouvelables
4.1.1 Description du problème
4.1.2 Une instance de problème
4.1.3 Complexité de problème
4.2 Modèle mathématique
4.2.1 Paramètres et indices
4.2.2 Variables
4.2.3 Modèle
4.2.4 Signification des équations
4.3 Benchmarks
4.4 Résultats numériques
4.5 Conclusion
5 Algorithme génétique pour le problème Flow-Shop sous contraintes de ressources non-renouvelables
5.1 Introduction
5.2 Algorithme Génétique (AG)
5.2.1 Codage utilisé
5.2.2 Génération de la population initiale
5.2.2.1 Les heuristiques constructives utilisées
5.2.3 Évaluation de la solution
5.2.4 Opérateur de sélection
5.2.5 Opérateur de croisement
5.2.6 Opérateur de mutation
5.2.7 La stratégie de remplacement
5.2.8 Mécanisme d’arrêt
5.3 Recherche locale
5.4 Paramétrage de l’algorithme génétique proposé
5.4.1 Taille de population
5.4.2 Probabilité de croisement
5.4.3 Probabilité de mutation
5.4.4 Application de la méthode de Taguchi
5.5 Résultats expérimentaux
5.5.1 Résultats de calcul pour les problèmes de petites tailles
5.5.2 Résultats de calcul pour les problèmes de moyennes à grandes tailles
5.6 Conclusion
6 Algorithme d’optimisation par essaims particulaires pour le Flow-Shop sous contraintes de ressources non-renouvelables
6.1 Introduction
6.2 Conception d’un algorithme d’OEP discrèt pour le Flow-Shop sous contraintes de ressources
6.2.1 Représentation de particule
6.2.2 Initialisation de l’essaim
6.2.3 Mise à jour de la vitesse et de la position
6.2.4 Stratégie de diversification
6.2.5 Opérateurs génétiques empruntés
6.2.5.1 Opérateur de croisement
6.2.5.2 Opérateur de mutation
6.2.6 Stratégie d’intensification
6.3 Paramétrage de l’algorithme
6.3.1 Taille de l’essaim
6.3.2 Critère d’arrêt
6.4 Résultats expérimentaux
6.4.1 Résultats de calcul pour les problèmes de petites tailles
6.4.2 Résultats de calcul pour les problèmes de moyennes à grandes tailles
6.5 Conclusion
Conclusions et perspectives
Bibliography

Télécharger le rapport complet