This paper proposes and investigates a metaheuristic tabu search algorithm (TSA)
that generates optimal or near optimal solutions sequences for the feedback length minimization
problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a
non-linear combinatorial optimization problem, belonging to the NP-hard class, and
therefore finding an exact optimal solution is very hard and time consuming, especially
on medium and large problem instances.
First, we introduce the subject and provide a review of the related literature and problem
definitions. Using the tabu search method (TSM) paradigm, this paper presents a
new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback
length minimization problem, using two different neighborhoods based on swaps
of two activities and shifting an activity to a different position. Furthermore, this paper
includes numerical results for analyzing the performance of the proposed TSA and for
fixing the proper values of its parameters. Then we compare our results on benchmarked
problems with those already published in the literature.
We conclude that the proposed tabu search algorithm is very promising because it
outperforms the existing methods, and because no other tabu search method for the
FLMP is reported in the literature. The proposed tabu search algorithm applied to the
process layer of the multidimensional design structure matrices proves to be a key optimization
method for an optimal product development. / Ce mémoire présente un nouvel algorithme métaheuristique de recherche taboue
pour trouver des solutions optimales ou sous-optimales au problème de minimisation de
la longueur des dépendances d’une matrice de conception (FLMP). Ce problème comporte
une fonction économique non-linéaire et il appartient à la classe NP-ardu. Il
s’ensuit qu’il est très difficile à trouver une solution optimale exacte en temps réel pour
les problèmes de taille moyenne ou grande.
D’abord, on présente le problème et une revue de la littérature associée. Ensuite, on
analyse le problème, et on présente les détails du nouvel algorithme de recherche taboue
produisant des solutions au problème de réduction de l’effet de retour en utilisant
deux voisinages différents, le premier basé sur l’échange des positions de deux activités
("swap"), et le second sur le déplacement d’une activité à une position différente
("shift"). Des résultats numériques permettent d’analyser le comportement de l’algorithme
et de comparer les deux voisinages. La première étape consiste à déterminer de
bonnes valeurs pour les paramètres en utilisant des problèmes générés aléatoirement.
Ensuite nos résultats sont comparés avec ceux obtenus dans la littérature.
On conclut que l’algorithme de recherche taboue proposé est très prometteur, car nos
résultats sont meilleurs que ceux publiés dans la litérature. D’autant plus que la recherche
taboue semble avoir été utilisée pour la première fois sur ce problème.
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/16161 |
| Date | 04 1900 |
| Creators | Laza, Vlad Lucian |
| Contributors | Ferland, Jacques, Lamghari, Amina, Dimitrakopoulos, Roussos |
| Source Sets | Université de Montréal |
| Language | English |
| Detected Language | French |
| Type | Thèse ou Mémoire numérique / Electronic Thesis or Dissertation |
Page generated in 0.0018 seconds