Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ÉCOLE DE TECHNOLOGIE SUPÉRIEURE UNIVERSITÉ DU QUÉBEC MÉMOIRE PRÉSENTÉ À L'ÉCOLE

ÉCOLE DE TECHNOLOGIE SUPÉRIEURE UNIVERSITÉ DU QUÉBEC MÉMOIRE PRÉSENTÉ À L'ÉCOLE DE TECHNOLOGIE SUPÉRIEURE COMME EXIGENCE PARTIELLE À L'OBTENTION DE LA MAÎTRISE EN GÉNIE MÉCANIQUE M.Ing. PAR CHERIF MAKREM OPTIMISATION DE L'ORDONNANCEMENT PAR L'APPROCHE HYBRIDE BASÉE SUR LES RÉSEAUX DE NEURONES MONTRÉAL, LE 21 DECEMBRE 2004 © droits réservés de Cherif Makrem CE MÉMOIRE A ÉTÉ ÉVALUÉ PAR UN JURY COMPOSÉ DE: M. Dao Thien My, directeur de mémoire Département de génie mécanique à l'École de Technologie Supérieure Mme Sylvie Nadeau, présidente de jury Département de génie mécanique à l'École de Technologie Supérieure M. Richard Lepage, membre de jury externe Département de génie de la production automatisée à l'École de Technologie Supérieure IL A FAIT L'OBJET D'UNE PRÉSENTATION DEVANT JURY LE 23 NOVEMBRE 2004 À L'ÉCOLE DE TECHNOLOGIE SUPÉRIEURE OPTIMISATION DE L'ORDONNANCEMENT PAR L'APPROCHE HYBRIDE BASÉE SUR LES RÉSEAUX DE NEURONES Cherif Makrem SOMMAIRE Les problèmes d'ordonnancement se posent dans de nombreux domaines tels que la productique et l'informatique. Leur variété vient de la diversité des données, des contraintes et des critères d'optimisation qu'ils impliquent. Ce mémoire traite le problème de l'ordonnancement déterministe dans un atelier à tâches («Job shop» et cellules de production) sur la base d'une utilisation des réseaux de neurones. Ce problème est un problème d'optimisation NP-Complet lorsque le nombre de machines et · de tâches est supérieur à deux. Les données sont constituées de l'ensemble des tâches à exécuter, de leurs gammes opératoires, de leurs durées ainsi que de l'ensemble des machines. Les contraintes prises en compte sont les contraintes de partage de ressources et de précédences. Les variables de décision concernent les dates de début et les dates de fin des opérations. Un critère d'optimisation est considéré, le "makespan" qui correspond à la minimisation d~ temps total de travail. L'utilisation des réseaux de neurones est intéressante car le parallélisme intrinsèque de ces derniers offre, a priori, une possibilité de traiter des problèmes de grandes tailles dans un temps limité. Une étude comparative des différentes approches de réseaux de neurones utilisés dans 1' optimisation a été effectuée. Elle nous a permis d'apprécier les potentialités des réseaux de neurones de Hopfield dans le traitement d'une variété de problèmes d'optimisation. Notre travail a consisté ensuite à ajuster les particularités des réseaux de neurones à mettre en oeuvre pour la résolution de notre problème d'ordonnancement. Les propositions de ce mémoire sont articulées autour d'une utilisation combinée des réseaux de neurones avec un algorithme heuristique. Cette combinaison peut apporter, dans la majorités des cas, une amélioration nette de la qualité de solutions. Enfin, une des particularités fondamentales des réseaux de neurones étant la robustesse, il nous a paru intéressant de chercher dans quelle mesure il est possible d'explorer utilement cette propriété. Cette démarche nous a conduit à la proposition d'un réseau récent de Hopfield (Quantized Hopfield), qui nous permet d'obtenir les solutions optimales très fréquemment et beaucoup plus rapidement que d'autres réseaux de Hopfield. OPTIMIZATION OF SCHEDULING BY THE HYBRID APPROACH BASED ON THE NEURAL NETWORKS Cherif Makrem ABSTRACT Scheduling problems occur often in various domains such as manufacturing and computer science. Their variety is due to the diversity of data, constraints and optimization criteria which they imply. This thesis studies the problem of deterministic scheduling in a job-shop and cellular manufacturing, using an artificial neural network approach. This is an NP-complete optimization problem when the number of machines and the number of tasks exceed 2. The data is composed of the set of tasks to be executed, their operational ranges, their duration and the set of machines on which they will be executed. The constraints which have been considered, are : resource sharing and precedence constraints. Decision variables correspond to the start and end dates of operations. One optimization criteria have been considered : makespan (which corresponds to the minimization of the total scheduling duration). The use of an artificial neural network is interesting since its intrinsic parallelism facilitates handling large sized problems in a limited time. A comparative study of various approaches of neural networks used in optimization has been undertaken in this thesis. This has enabled us to appreciate the potential of Hopfield neural networks for solving a variety of optimization problems. Our next contribution consists of adjusting specifies of neural networks to be implemented for solving our scheduling problem. Proposais made in this thesis are centred around : a combined utilisation of neural nets and heuristic algorithms. This combination can bring (under certain conditions) a significant improvement of the quality of solutions. Finally, robustness being a fundamental particularity of neural nets, it appeared interesting for us to explore under which conditions this property could be usefully exploited. This final approach led us to propose a recent kind of neural networks (Quantized Hopfield), which allows us to obtain optimal design solutions very frequently and much more quickly than other Hopfield networks. REMERCIEMENTS Je tiens à remercier mon directeur de recherche Dao Thien My pour son soutien, sa disponibilité et ses précieux conseils dans la présente recherche. Son bon jugement et son enthousiasme ont été pour moi une source de motivation. Je tiens à remercier Madame Sylvie Nadeau, Professeure à l'École de Technologie Supérieure, département de génie mécanique, de me faire l'honneur de s'intéresser à ce travail et de faire partie du jury. Je remercie également Monsieur Richard Lepage, Professeur à l'École de Technologie Supérieure, département de génie de la production automatisée, pour l'intérêt qu'il a bien voulu porter à ce travail et d'avoir accepté de faire partie du jury. De plus, je salue tous mes bons collègues du laboratoire qui ont su m'encourager et partager leurs précieuses informations quand le besoin urgent se présentait. Enfin, je remercie tous les membres de ma famille qui ont su me transmettre cette force de persévérer et d'entreprendre qui m'accompagne, à chaque fois, dans tout projet que je réalise. TABLE DES MATIÈRES Page SOMMAIRE ...................................................................................................................... i ABSTRACT ...................................................................................................................... ii REMERCIEMENTS ........................................................................................................ iii TABLE DES MATIÈRES ............................................................................................... iv LISTE DES TABLEAUX ............................................................................................... vii LISTE DES FIGURES .................................................................................................. viii LISTE DES ABRÉVIATIONS ......................................................................................... x INTRODUCTION ............................................................................................................ 1 CHAPITRE 1 L'ORDONNANCEMENT DE LA PRODUCTION ............................... 3 1.1 Introduction ................................................................................................... 3 1.2 Problématique de l'ordonnancement de la production ....... : .......................... 3 1.3 Le système traditionnel "Job Shop" .............................................................. 5 1.4 Du système "Job Shop" à la production cellulaire ....................................... 6 1.4.1 Conception d'un aménagement d'usine ........................................................ 8 1.4.2 Commande de flux opérationnel ................................................................... 9 1.4.3 Choix d'équipement ..................................................................................... 10 1.4.4 Mobilisation du personnel ........................................................................... 11 1.5 Les résultats escomptés de la production cellulaire .................................... 12 1.6 Les exigences et les limites de la production cellulaire .............................. 13 1.7 Différence entre JS et PC au niveau d'ordonnancement.. ........................... 14 1.8 Approches classiques des problèmes d'ordonnancement ........................... 16 CHAPITRE 2 LES APPROCHES NEURONALES ET L'ORDONNANCEMENT ... 19 2.1 2.2 2.3 2.4 2.4.1 2.4.2 2.5 2.5.1 2.5.1.1 2.5.1.2 2.5.1.3 Introduction ................................................................................................ 19 Historique ................................................................................................... 21 Neurone formel .......................................................................................... 22 Les approches neuronales et 1' optimisation ............................................... 24 Les neurones formels utilisés pour 1' optimisation ..................................... 24 Architectures de réseaux de neurones pour l'optimisation ........................ 25 Étude des différentes approches de RN utilisés dans l'optimisation ......... 26 Les réseaux de neurones récurrents de Hopfield ........................................ 27 Principes de fonctionnement du réseau de Hopfield pour l'optimisation .. 27 Réseaux de Hopfield binaires ..................................................................... 28 Réseaux de Hopfield analogiques .............................................................. 30 2.5.1.4 2.5.1.5 2.5.2 2.5.2.1 2.5.2.2 2.5.2.3 2.6 2.7 v Application des réseaux de Hopfield à 1' optimisation ............................... 31 Limitations des réseaux de Hopfield .......................................................... 33 La machine de Boltzmann (MB) ................................................................ 33 Le principe de recuit simulé [4] ................................................................. 34 Application des réseaux de Boltzmann à l'ordonnancement ..................... 35 Limitations des réseaux de Boltzmann ....................................................... 36 Le choix d'une technique neuronale pour l'ordonnancement.. .................. 36 Vers une approche hybride ......................................................................... 37 CHAPITRE 3 L'ORDONNANCEMENT AVEC LE RESEAU DE HOPFIELD 3.1 3.2 3.3 3.4 3.4.1 3.4.2 3.4.3 3.4.4 3.5 3.6 3.7 3.7.1 3.7.1.1 3.7.1.2 3.7.1.3 3.7.1.4 3.7.1.5 3.7.1.6 3.7.2 3.7.3 3.7.4 3.8 3.9 HYBRIDE .............................................................................................. 38 Introduction ................................................................................................ 38 Problématique ............................................................................................. 38 Objectif ....................................................................................................... 39 Critères à optimiser .................................................................................... 39 Critères basés sur le temps d'achèvement de la tâche ................................ 39 Critères basés sur les délais de livraison : .................................................. 40 Critères basés sur les coûts d'inventaire ................................................... .41 Critères basés sur les coûts d'utilisation .................................................... 41 Définition du problème d'ordonnancement job shop ................................. 41 Définition du problème d'ordonnancement production cellulaire ............. 42 Nouvelle approche hybride pour l'ordonnancement.. ................................ 43 Caractéristiques du RNH pour l'ordonnancement ..................................... 44 Codage du problème ................................................................................... 45 Contraintes à satisfaire ............................................................................... 46 Détermination de l'énergie du réseau ......................................................... 4 7 Détermination des équations d'évolution des neurones ............................. 50 La fonction sigmoïde d'entrée-sortie .......................................................... 52 Description de l'algorithme ........................................................................ 53 Mise en œuvre de la première phase de 1' approche proposée .................... 54 Caractéristiques de la procédure de recherche locale ................................. 59 Mise en œuvre de la deuxième phase de 1' approche proposée .................. 64 Performance de l'approche présentée ........................................................ 67 Conclusion .................................................................................................. 68 CHAPITRE 4 V ALIDA TION ET SYNTHÈSE ........................................................... 70 4.1 Introduction ................................................................................................ 70 4.2 Exemple d'ordonnancement Job Shop de 28 opérations uploads/Ingenierie_Lourd/ cherif-makrem.pdf