Optimisation de l'ordonnancement par l'approche hybride basée sur les réseaux de neurones

Cherif, Makrem (2004). Optimisation de l'ordonnancement par l'approche hybride basée sur les réseaux de neurones. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (3MB) | Prévisualisation

Résumé

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 du 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 l'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é 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.

Titre traduit

Optimization of scheduling by the hybrid approach based on the neural networks

Résumé traduit

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 specifics of neural networks to be implemented for solving our scheduling problem. Proposals 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.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Mémoire présenté à l'École de technologie supérieure comme exigence partielle à l'obtention de la maîtrise en génie mécanique". Bibliogr.: f. [103]-106.
Mots-clés libres:	Approche, Hopfield, Hybride, Neuronal, Neurone, Optimisation, Ordonnancement, Production, Reseau, Validation
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Dao, Thien-My
Programme:	Maîtrise en ingénierie > Génie mécanique
Date de dépôt:	20 avr. 2011 16:21
Dernière modification:	21 oct. 2016 00:35
URI:	https://espace.etsmtl.ca/id/eprint/712

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt