Problèmes d’Ordonnancement d’Atelier

Les problèmes d’ordonnancement d’atelier

Dans un problème d’atelier, une pièce doit être usinée ou assemblée sur différentes machines. Chaque machine est une ressource disjonctive, c’est-à-dire qu’elle ne peut exécuter qu’une tâche à la fois, et les tâches sont liées exclusivement par des contraintes d’enchaînement. Plus précisément, les tâches sont regroupées en n entités appelées travaux ou lots. Chaque lot est constitué de m tâches à exécuter sur m machines distinctes, et dans le cas des problèmes d’atelier, une tâche est une opération, une ressource est une machine et chaque opération nécessite pour sa réalisation une machine. Dans le modèle de base de l’ordonnancement d’atelier, l’atelier est constitué de m machines, n travaux (jobs), disponibles à la date 0, doivent être réalisés, un travail i est constitué de ni opérations, l’opération j du travail i est notée (i,j) avec (i, 1) < (i, 2) < … < (i, ni) si le travail i possède une gamme ( A < B signifie A précède B). Une opération (i,j) utilise la machine mi,j pendant toute sa durée pi,j et ne peut être interrompue . Un atelier se définit par le nombre de machines qu’il contient et par son type. Une classification peut exister selon le nombre des machines et l’ordre d’utilisation des machines, pour réaliser un travail (par exemple fabrication d’un produit qui dépend de la nature de l’atelier). Solon les caractéristiques des machines on peut distinguer plusieurs types des problèmes :

Méthodes d’optimisation des problèmes d’ordonnancement :

Etant donnés un ensemble de tâches et un ensemble de ressources, il est nécessaire de programmer les tâches et d’affecter les ressources de façon à optimiser un ou plusieurs objectifs (un objectif correspondant à un critère de performance), en respectant un ensemble de contraintes. La principale difficulté à laquelle est confronté un décideur, en présence d’un problème d’optimisation est celui du choix d’une méthode efficace capable de produire une solution optimale en un temps de calcul raisonnable. Les différentes méthodes de résolution développées peuvent être classées en deux catégories : les méthodes exactes qui garantissent la complétude de la résolution et les méthodes approchées qui perdent la complétude pour gagner en efficacité.

Les méthodes exactes : On peut définir une méthode exacte comme étant une méthode qui fournit une solution optimale pour un problème d’optimisation. L’utilisation de ce type de méthodes s’avère particulièrement intéressante dans les cas des problèmes de petites tailles. La méthode par séparation et évaluation (branch and bound) constituent certainement celles qui sont les plus utilisées pour résoudre les problèmes d’optimisation multi objectifs [2]. D’autres méthodes telles que la programmation linéaire ou la programmation dynamique, sont aussi utilisées couramment. Toutes ces méthodes examinent d’une manière implicite, la totalité de l’espace de recherche pour produire la solution optimale[2].

La méthode de Branch and Bound : L’algorithme Branch and Bound consiste à placer progressivement les tâches sur les ressources en explorant un arbre de recherche décrivant toutes les combinaisons possibles. Il s’agit de trouver la meilleure configuration donnée de manière à élaguer les branches de l’arbre qui conduisent à de mauvaises solutions. L’algorithme branch and bound effectue une recherche complète de l’espace des solutions d’un problème donné, pour trouver la meilleure solution .La démarche de l’algorithme Branch and Bound consiste à :

.La programmation dynamique :

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

Les méta-heuristiques: Malgré l’évolution permanente de l’informatique, il existe toujours, pour un problème polynomial, une taille critique au-dessus de laquelle une énumération, même partielle, des solutions admissibles devient prohibitive. Compte tenu de ces difficultés, la plupart des spécialistes de l’optimisation combinatoire ont orienté leurs recherches vers le développement des méta-heuristiques. Une méta-heuristique est souvent définie comme une procédure exploitant au mieux la structure du problème considéré, dans le but de trouver une solution de qualité raisonnable en un temps de calcul aussi faible que possible. Les méta-heuristiques sont ainsi des méthodes de recherche générales, dédiées aux problèmes d’optimisation difficile. Elles sont, en général, présentées sous forme de concepts. Les principales méta-heuristiques sont celles basées sur la recherche locale, telles que le recuit simulé et la recherche Tabou, et celles basées sur les algorithmes évolutionnistes telles que les algorithmes génétiques ainsi que les algorithmes basés sur la recherche globale tels que les algorithmes de colonies de fourmis et les algorithmes reposant sur la méthode d’optimisation par essaim de particules

Conclusion

Dans ce projet, nous avons présenté les différentes caractéristiques d’un problème d’ordonnancement et les différents types de problèmes d’ordonnancement d’atelier. Nous avons traité en particulier le problème de flow shop et de job shop, mais la difficulté réside dans la résolution d’un problème d’ordonnancement par les méthodes heuristiques et méta-heuristiques ce qui nécessite une étude approfondie sur ces méthodes approchés

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

І-Les problèmes d’ordonnancement
1-Définitions et notions fondamentales
2- Notion d’objets et de critères
3- Contraintes d’ordonnancement
4- Résolution d’un problème d’ordonnancement
ІІ– Les problèmes d’ordonnancement d’atelier
1.Schémas de classification
2.les types des problèmes
2.1. Problèmes à une machine
2.3. Problèmes à machines parallèles
2.4. Problèmes de Flow shop
2.5. Problèmes de job shop
2.6. Problèmes d’open shop
3.La notion de la flexibilité
3.1. Flow shop hybride
3.2. Job shop flexible
Conclusion
III. Méthodes d’optimisation des problèmes d ordonnancement
1.Les méthodes exactes
1.1. La méthode de Branch and Bound
1.2. La programmation dynamique
1.3. La programmation linéaire
Les Heuristique
Les Méta-heuristiques
IV-Modélisation et optimisation des problèmes d’ordonnancement d’atelier
1.Job shop classique
1.1. Modélisation
1.2. Optimisation
1.2.1. Job shop à m >2 machines
1.2.2. Job shop à 2 machines
2.Flow shop classique
2.1. Exemple d’une modélisation de Flow shop
2.2. Méthodes d’optimisation
2.2.1 Flow shop à m>2 machines
2.2.2 Flow shop à 2 machines
Conclusion