Le choix d’une technique neuronale pour l’ordonnancement

Problématique de l’ordonnancement de la production

  L’environnement actuel des entreprises est caractérisé par des marchés soumis à une forte concurrence et sur lesquels les exigences et les attentes des clients deviennent de plus en plus fortes en termes de qualité, de coût et de délais de mise à disposition (Figure 1 ). Cette évolution se renforce par le développement rapide des nouvelles technologies de l’information et de la communication qui permettent une relation directe entre les entreprises et entre les entreprises et leurs clients. Dans un tel contexte, la performance de l’entreprise se construit selon deux dimensions :
– une dimension technologique qui vise à développer les performances intrinsèques des produits mis sur le marché afin de satisfaire aux exigences de qualité et de réduction du coût de possession des produits. L’innovation technologique joue ici un rôle important et peut constituer un élément différenciateur déterminant pour la pénétration et le développement d’un marché. Il faut relever à ce niveau que l’évolution technologique rapide des produits et les exigences de personnalisation de ces produits qu’attendent les marchés conduisent les entreprises à abandonner souvent les productions de masse pour s’orienter vers des productions de petites ou moyennes séries, sinon à la commande. Ceci leur impose donc d’avoir des systèmes de production flexibles et évolutifs, capables de s’adapter aux exigences et aux besoins des marchés rapidement et efficacement.
– une dimension organisationnelle, qui vise à développer la performance en termes de durée des cycles de fabrication, respect des dates de livraison prévues, gestion des stocks et des en-cours, adaptation et réactivité face aux variations du carnet commercial. Cette dimension joue un rôle de plus en plus important, dans la mesure où les marchés sont de plus en plus versatiles et évolutifs et exigent des temps de réponse des entreprises de plus en plus courts. Il faut donc disposer de méthodes et d’outils de plus en plus performants pour 1′ organisation et la conduite de la production. Pour atteindre ces objectifs, l’organisation repose en général sur la mise en œuvre d’un certain nombre de fonctions, parmi lesquelles la fonction ordonnancement joue un rôle essentiel. Cette fonction vise en effet à contrôler les priorités, à préserver le bien-être du personnel, à prévoir les activités de maintenance préventive et prédictive, à organiser l’utilisation des ressources technologiques et humaines présentes dans les ateliers de 1′ entreprise pour satisfaire soit directement les demandes des clients, soit les demandes issues d’un plan de production préparé par la fonction de planification de l’entreprise. Cette fonction doit organiser l’exécution simultanée de multiples travaux à l’aide de ressources polyvalentes disponibles en quantités limitées, ce qui constitue un problème complexe à résoudre, un problème d’allocation de ressources sujet à des contraintes. Bien sûr, au sein des entreprises, cette fonction a toujours existé, mais elle est aujourd’hui confrontée à des problèmes de plus en plus complexes à résoudre, à cause du grand nombre de travaux qu’elle doit simultanément réaliser, et pour chacun d’eux des délais de réalisation de plus en plus courts.

Le système traditionnel « Job Shop »

   L’environnement de « Job Shop » (JS) est un système de production où les équipements sont regroupés par types d’opérations, l’aménagement d’usine est habituellement divisé en plusieurs ateliers, chacun se composant de machines de types semblables pour exécuter une fonction (figure 2). L’avantage d’un tel aménagement est l’utilisation maximale du parc machine. De plus, il permet l’achat d’un équipement à usages multiples, peut supporter une variété de requis de procédé, flexible dans l’allocation du personnel et des équipements et moins vulnérables aux arrêts causés par un bris mécanique ou une absence. Dans ce type d’aménagement, le cheminement des produits est généralement irrégulier, la taille de lot est habituellement grande pour réduire au minimum le prix de revient unitaire de mise en course, ce qui crée des difficultés de manutention et de circulation entre les diverses sections. En outre, la planification de la production, spécialement l’ordonnancement, y est relativement complexe puisque n’importe quelle section peut constituer un point d’entrée, de transit ou de sortie du produit dans le système. Les responsables de cette planification ont alors de plus en plus recours à 1′ informatique dans leur travail.

Approches classiques des problèmes d’ordonnancement

   Les méthodes de résolution des problèmes d’ordonnancement sont largement présentées dans la littérature [7]. Elles puisent dans toutes les techniques d’optimisation:
• les méthodes de programmation mathématique [32] sont extrêmement fréquentes dans les applications. Plusieurs heuristiques visent à réduire le volume de l’enveloppe convexe des solutions en ajoutant des contraintes.
• Les méthodes arborescentes [4] sont des méthodes exactes, qui essaient d’énumérer les solutions réalisables de manière à trouver rapidement de bonnes solutions. Appliquées aux problèmes d’ordonnancement, ces approches nécessitent des temps de calcul qui croissent exponentiellement avec le nombre de variables.
• Les méthodes de programmation dynamique [ 4] sont des techniques énumératives fondées sur l’idée que des solutions à des sous problèmes du problème peuvent aider à guider la recherche de la solution optimale du problème global. Là encore, cette approche atteint ses limites pour les problèmes de grandes tailles. D’après l’étude présenté par Berard, Azzaro-pantel, Pibouleau et Domenech en 1997 [7], ces méthodes présentent l’avantage de garantir l’optimalité de la solution fournie, si le problème est convexe. Pour des problèmes de taille réelle, ces procédures requièrent des temps d’exécution prohibitifs et sont alors généralement associées à des méthodes heuristiques ou des algorithmes de recherche locale, ce qui leur fait perdre beaucoup de leur rigueur mathématique. Les algorithmes basés sur la programmation mathématique ou sur la programmation dynamique s’avèrent très rapidement inadaptés pour des problèmes de grande taille. La plupart des méthodes proposées pour la résolution des problèmes d’ordonnancement sont du type procédures arborescentes fondées sur une modélisation par un graphe disjonctif. D’autres sont basées notamment sur la programmation linéaire en nombres entiers. Plus récemment, les méthodes de type recuit simulé (RS) [31] et algorithmes génétiques (AG) [33] ont été utilisées. Les méthodes de type RS, que nous présenterons ultérieurement, sont des méthodes dérivées de la physique statistique et destinées à éviter les minima locaux des fonctions de coût (voir paragraphe 2.5.2.1 page 34) et pour les algorithmes génétiques des solutions potentielles sont considérées comme des individus qui évoluentdans une population.

Historique

  Les premiers à proposer un modèle sont deux biophysiciens de Chicago, McCulloch et Pitts, qui inventent en 1943 le premier neurone formel qui portera leurs noms (neurone de McCulloch-Pitts). Quelques années plus tard, en 1949, Hebb propose une formulation du mécanisme d’apprentissage [26], sous la forme d’une règle de modification des connexions synaptiques (règle de Hebb ). Le premier réseau de neurones artificiels apparaît en 1958, grâce aux travaux de Rosenblatt [27] qui conçoit le fameux perceptron. Le perceptron est inspiré du système visuel (en terme d’architecture neurobiologique) et possède une couche de neurones d’entrée (« perceptive ») ainsi qu’une couche de neurones de sortie (« décisionnelle »). Ce réseau parvient à apprendre à identifier des formes simples et à calculer certaines fonctions logiques. Il constitue donc le premier système artificiel présentant une faculté jusque là réservée aux êtres vivants : la capacité d’apprendre par l’expérience. Malgré tout l’enthousiasme que soulève le travail de Rosenblatt dans le début des années 60, la fin de cette décennie sera marquée en 1969, par une critique virulente du perceptron par Minsky et Pa pert [28]. Ils utilisent une solide argumentation athématique pour démontrer les limitations des réseaux de neurones à une seule couche. Ils montrent toutes les limites de ce modèle, et soulèvent particulièrement l’incapacité du perceptron à résoudre les problèmes non linéairement séparables, tel que le célèbre problème du XOR (OU exclusif). Il s’en suivra alors, face à la déception, une période noire d’une quinzaine d’années dans le domaine des réseaux de neurones artificiels.

Étude des différentes approches de RN utilisés dans l’optimisation

  En 1994, Dagli [ 6] a présenté plusieurs types de réseaux neuronaux utilisés pour l’optimisation :
• réseau de recherche
• réseau probabiliste
• réseau de concurrence
• réseau correcteur d’erreurs
Dans un réseau de recherche, le réseau de neurone est installé de telle manière que la dynamique du réseau conduit fréquemment vers un minimum local qui représente une solution possible, qui n’est pas nécessairement proche de l’optimum ou bien qui ne correspbnd pas à une solution acceptable. Un exemple de ce type est l’approche de réseau de Hopfield. Les réseaux probabilistes sont utilisés pour éviter d’être piégé trop facilement dans des minima locaux, ils sont basés sur les résultats probabilistes de la sortie de réseau. Un exemple de ce type est l’approche des machines de Boltzmann. Dans le type de réseaux de compétition, la solution vient du gagnant de la compétition d’un groupe de neurones de sorties par des inhibitions latérales pour s’assurer que seulement un choix simple est fait. Un exemple de ce type est la carte auto-organisatrice de Kohonen. Dans quelques cas complexes où beaucoup de contraintes sont présentes, les réseaux correcteurs d’erreurs sont utilisés pour apprendre les modèles de sortie des ordonnancements. Un exemple de ce type est l’approche populaire perceptron multicouche (PM). Dans ce que suit on va s’intéresser seulement aux deux premiers types qui sont les plus utilisé dans l’ordonnancement des opérations manufacturières.

Table des matières

ABSTRACT
REMERCIEMENTS
LISTE DES TABLEAUX
LISTE DES FIGURES
LISTE DES ABRÉVIATIONS
INTRODUCTION
CHAPITRE 1 L’ORDONNANCEMENT DE LA PRODUCTION 
1.1 Introduction 
1.2 Problématique de l’ordonnancement de la production 
1.3 Le système traditionnel « Job Shop » 
1.4 Du système « Job Shop » à la production cellulaire 
1.4.1 Conception d’un aménagement d’usine
1.4.2 Commande de flux opérationnel
1.4.3 Choix d’équipement
1.4.4 Mobilisation du personnel
1.5 Les résultats escomptés de la production cellulaire 
1.6 Les exigences et les limites de la production cellulaire 
1.7 Différence entre JS et PC au niveau d’ordonnancement 
1.8 Approches classiques des problèmes d’ordonnancement 
CHAPITRE 2 LES APPROCHES NEURONALES ET L’ORDONNANCEMENT  
2.1 Introduction
2.2 Historique
2.3 Neurone formel
2.4 Les approches neuronales et 1′ optimisation
2.4.1 Les neurones formels utilisés pour 1′ optimisation
2.4.2 Architectures de réseaux de neurones pour l’optimisation
2.5 Étude des différentes approches de RN utilisés dans l’optimisation
2.5.1 Les réseaux de neurones récurrents de Hopfield
2.5.1.1 Principes de fonctionnement du réseau de Hopfield pour l’optimisation
2.5.1.2 Réseaux de Hopfield binaires
2.5.1.3 Réseaux de Hopfield analogiques
2.5.1.4 Application des réseaux de Hopfield à 1′ optimisation
2.5.1.5 Limitations des réseaux de Hopfield
2.5.2 La machine de Boltzmann (MB)
2.5.2.1 Le principe de recuit simulé
2.5.2.2 Application des réseaux de Boltzmann à l’ordonnancement
2.5.2.3 Limitations des réseaux de Boltzmann
2.6 Le choix d’une technique neuronale pour l’ordonnancement
2.7 Vers une approche hybride
CHAPITRE 3 L’ORDONNANCEMENT AVEC LE RESEAU DE HOPFIELD HYBRIDE
3.1 Introduction
3.2 Problématique
3.3 Objectif
3.4 Critères à optimiser
3.4.1 Critères basés sur le temps d’achèvement de la tâche
3.4.2 Critères basés sur les délais de livraison
3.4.3 Critères basés sur les coûts d’inventaire
3.4.4 Critères basés sur les coûts d’utilisation
3.5 Définition du problème d’ordonnancement job shop 
3.6 Définition du problème d’ordonnancement production cellulaire
3.7 Nouvelle approche hybride pour l’ordonnancement
3.7.1 Caractéristiques du RNH pour l’ordonnancement
3.7.1.1 Codage du problème
3.7.1.2 Contraintes à satisfaire
3.7.1.3 Détermination de l’énergie du réseau
3.7.1.4 Détermination des équations d’évolution des neurones
3.7.1.5 La fonction sigmoïde d’entrée-sortie
3.7.1.6 La fonction sigmoïde d’entrée-sortie
3.7.2 Mise en œuvre de la première phase de 1′ approche proposée
3.7.3 Caractéristiques de la procédure de recherche locale
3.7.4 Mise en œuvre de la deuxième phase de 1′ approche proposée
3.8 Performance de l’approche présentée
3.9  Conclusion 
CHAPITRE 4 V ALIDA TION ET SYNTHÈSE 
4.1 Introduction 
4.2 Exemple d’ordonnancement Job Shop de 28 opérations 
4.3 Exemple d’ordonnancement Job Shop de 50 opérations 
4.4 Conclusion
CONCLUSION
ANNEXES
1 : Les propriétés de convergence des réseaux de Hopfield
2 : Quelques définitions utiles
3 : Code Matlab pour l’exemple 1 (12 Opérations)
4 : C ode Matlab pour 1 ‘exemple 2 (28 Opérations)
5 : Code Matlab pour l’exemple 3 (50 Opérations)
BIBLIOGRAPHIE

Télécharger le rapport complet