Optimization of the scheduling strategy using meta-heuristics approach in the context of cellular manufacturing with multiples products

Alzidani, Mahmoud (2021). Optimization of the scheduling strategy using meta-heuristics approach in the context of cellular manufacturing with multiples products. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

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

Résumé

Production scheduling is at the heart of the plant's planning and control system. One of the attractive production planning systems is Cellular Manufacturing Systems (CMS). CMS is a structural system based on group theory. Several advantages of the SFC concept mainly include the reduction of makespan and flow time. CMS is an NP-hard optimization problem. Depending on the size of the problem, the number of machines, and the number of parts, the computing time required to obtain the optimal solution increases exponentially. To solve NPhard optimization problems, metaheuristic algorithms are the best solution to get good solutions in a reasonable time.

In this work, we propose a new methodology to optimize parts' sequence in each manufacturing cell, including exceptional items. This technique is based on the RC-Filter algorithm. The proposed methodology was used to optimize the sequence of parts, including exceptional items, to minimize the time required. The proposed approach has been validated using thirteen problems taken from the literature. The results were compared to those provided by the Extended Great Deluge.

A cellular manufacturing system is a structured system based on the concept of a group. One of the advantages of this concept is that it can reduce production time. Optimizing cell manufacturing systems are categorized as NP-Hard, where the computational time increases exponentially with the problem's size. Utilizing metaheuristic algorithms will be an excellent solution to solve the NP-Hard problem in a reasonable time. In this work, we proposed a new hybrid approach to optimize the sequence of parts in each cell and exceptional elements. The proposed hybrid methodology is based on the RC-Filter algorithm and the Extended Great Deluge algorithm. The proposed tool is used to optimize the sequence of parts, including exceptional items in each cell, in order to minimize makespan. The proposed approach was validated using 13 problems, and the results were compared with those provided by other algorithms. A cellular manufacturing environment is generally the most efficient environment for minimizing makespan, flow time, and handling.

On the other hand, in most cases, a cell production environment requires distinctive elements' performance. This task generates many delays and intercellular movements. This problem is seen as a fundamental challenge to be solved to achieve the minimum makespan with exceptional elements and the minimum intercellular movement. In this work, a methodology was proposed, called the simulated annealing meta-heuristic algorithm, to obtain the best sequence of parts, allowing the minimum makespan.

This work has been divided into two steps, and each step contains two parts; these steps are as follows:

In the first part of the first step, we used simulated annealing to find the best sequence of exceptional elements without changing the cell's architecture. This is an optimization step as a jobshop problem, as there was much intercellular movement. In the second part, we optimized the sequence in each cell. These two parts represent the first stage of this work. To reduce intercellular movements, we used a dynamic cellular environment. In the second step of this work, a dynamic manufacturing cell was used. This step has two parts. In the first part, new cells were designed using only exceptional elements. Likewise, the machines used to manufacture exceptional items have been transferred to other cells. During the first part, the exceptional elements were made from a specific cell architecture. The goal of this part was to give the minimum of inter-cellular movements and manipulations. The second part of this step was to save the original cells' configuration, and the part sequences were optimized in each of them. Part sequence optimization was performed using the simulated annealing algorithm.

Titre traduit

Optimisation de la stratégie d'ordonnancement en utilisant l'approche méta-heuristique dans le cadre de la fabrication cellulaire avec de multiples produit

Résumé traduit

La planification de la production est au coeur du système de planification et de contrôle. Parmi les solutions les plus intéressantes on trouve la fabrication cellulaire (Cellular Manufacturing Systems CMS). Le CMS est un système structurel basé sur la théorie des groupes. Son concept présente plusieurs avantages, notamment la réduction du temps total d’exécution et du temps d'écoulement. La planification de la fabrication cellulaire est un problème d'optimisation NPdifficile. Selon la taille du problème, le nombre de machines et le nombre de pièces, le temps de calcul nécessaire pour obtenir la solution optimale augmente de façon exponentielle. Pour résoudre les problèmes d'optimisation de ce type, les algorithmes métaheuristiques sont jugés les meilleures pour obtenir des bonnes solutions dans un temps raisonnable. Dans ce travail, nous proposons une nouvelle méthodologie pour optimiser la séquence des pièces dans chaque cellule de fabrication, y compris les articles exceptionnels. Cette technique est basée sur l'algorithme RC-Filter. La méthodologie proposée a permis de minimiser le temps requis. Elle a été validée à l'aide de treize problèmes tirés de la littérature. Les résultats ont été comparés à ceux fournis par le Grand Déluge étendu. Comme la fabrication cellulaire est un système structuré basé sur le concept de groupe, il a plusieurs avantages comme la réduction du temps de production. Le problème de l'optimisation étant classé NP-difficile, le temps de calcul augmente exponentiellement avec la taille du problème. L'utilisation des algorithmes métaheuristiques est une excellente solution pour la résolution dans un temps raisonnable. Dans ce travail, nous avons proposé une nouvelle approche hybride pour optimiser la séquence des pièces dans chaque cellule ainsi que les éléments exceptionnels. La méthodologie hybride proposée est basée sur l'algorithme RC-Filter et l'algorithme Extended Great Deluge. L'outil proposé est utilisé pour optimiser la séquence des pièces y compris les éléments exceptionnels dans chaque cellule afin de minimiser le temps total d’exécution. L'approche proposée a été validée en utilisant 13 problèmes et les résultats ont été comparés à ceux fournis par d'autres algorithmes. Un environnement de fabrication cellulaire est généralement l'environnement le plus efficace en termes de minimisation du temps total d’exécution, du temps de passage et de la manutention. Par contre, dans la plupart des cas, un environnement de production cellulaire nécessite l'exécution d'éléments exceptionnels. Cette tâche génère de nombreux retards et mouvements intercellulaires. Ce problème est considéré comme un défi important à résoudre afin d'atteindre non seulement le temps d’exécution minimum, mais aussi les mouvements intercellulaires. Dans ce travail, une méthodologie a été proposée, appelée l'algorithme métaheuristique de recuit simulé, afin d'obtenir la meilleure séquence de pièces, qui permet d'obtenir le temps d’exécution minimum. Ce travail a été divisé en deux étapes et chaque étape contient deux parties: Dans la première partie de la première étape, nous avons utilisé le recuit simulé pour trouver la meilleure séquence d'éléments exceptionnels sans changer l'architecture de la cellule. C'est une étape d'optimisation comme un problème des ateliers à cheminements multiples (Job Shop), car il y avait beaucoup de mouvement intercellulaire. Dans la deuxième partie, nous avons optimisé la séquence dans chaque cellule. Pour réduire les mouvements intercellulaires, nous avons utilisé un environnement cellulaire dynamique. Dans la deuxième étape de ce travail, nous avons utilisé une cellule de fabrication dynamique. Cette étape comporte deux parties. Dans la première partie, de snouvelles cellules ont été conçues en utilisant uniquement des éléments exceptionnels. De même, les machines utilisées pour fabriquer les éléments exceptionnels ont été transférées dans d'autres cellules. Au cours de la première partie, les éléments exceptionnels ont été fabriqués à partir d'une architecture de cellule spécifique. Le but de cette partie était de donner le minimum de mouvements et de manipulations intercellulaires. La deuxième partie de cette étape consistait à sauvegarder la configuration des cellules d'origine et les séquences de pièces ont été optimisées dans chacune d'elles. L'optimisation des séquences de pièces a été réalisée à l'aide de l'algorithme de recuit simulé. Mots clés : fabrication cellulaire, algorithme méta-heuristique, temps total d’exécution, éléments exceptionnels.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Thesis presented to École de technologie supérieure in partial fulfillment for the degree of doctor of philosophy". Comprend des références bibliographiques (pages 105-114).
Mots-clés libres:	fabrication cellulaire, algorithme de méta-heuristique, makespan, éléments exceptionnels.
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Dao, Thien-My
Programme:	Doctorat en génie > Génie
Date de dépôt:	23 nov. 2021 16:10
Dernière modification:	23 nov. 2021 16:10
URI:	https://espace.etsmtl.ca/id/eprint/2788

Gestion Actions (Identification requise)

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