O problema da gestão ótima da diversidade de cablagens

Abstract

Neste trabalho, aborda-se o problema da gestão ótima da diversidade, que pode ser considerado um caso particular do problema da p-mediana, aplicado na indústria automóvel. Em primeiro lugar, descreve-se o problema e estudam-se algumas das suas caraterísticas combinatórias. Sendo um problema de otimização combinatória classificado como NP-difícil, usualmente, aplicam-se na sua resolução métodos heurísticos. Nesta tese, estuda-se um algoritmo Greedy com detalhe, de modo a inferir estratégias que o tornem mais eficiente na resolução do problema. Assim, estudam-se algumas caraterísticas combinatórias desse algoritmo Greedy, para um caso particular, e apresentam-se algumas propriedades do mesmo. De seguida, dado que na realidade o problema da gestão ótima da diversidade de cablagens pode ser decomposto em vários subproblemas, mais fáceis de resolver, apresenta-se a abordagem que consiste na aplicação dum algoritmo Greedy em duas etapas, numa primeira etapa o algoritmo é aplicado a cada subproblema e, numa segunda etapa, é aplicado para determinar a melhor forma de combinar as soluções dos vários subproblemas. Por último, é feito um estudo estatístico, com uma amostra de 5 problemas reais de uma empresa de cablagens, de modo a analisar a existência de caraterísticas comuns na resolução dos mesmos, através dum algoritmo Greedy. A partir de alguns resultados observados nesse estudo e pelo facto de, para problemas de grande dimensão, esse algoritmo demorar mais tempo que o desejado a encontrar uma solução, consideram-se duas variantes do mesmo que resultam de restrições na pesquisa que é feita pelo algoritmo original, de forma a torná-lo mais rápido. É apresentado um pequeno estudo computacional para comparar as diferentes variantes do algoritmo.

This study covers the optimal diversity management problem, which can be seen as a particular case of p-median problem, applied to automotive industry. The starting point is the problem description as well as a study of some of its combinatorial characteristics. As a combinatorial optimization problem classified as NP-hard, heuristic methods are often used on its resolution. In this thesis, a Greedy algorithm is studied in deep detail, in order to find some strategies to improve it for a more efficient problem resolution. Thus, some particular combinatorial characteristics of this Greedy algorithm are studied, for a particular case, and some of its properties are presented. Thereafter, since optimal diversity management problem can be decomposed into several sub problems – easier to solve – an approach which consists in the application of a Greedy algorithm in two steps is presented: a first step where the algorithm is applied to each sub problem, and a second step where it is applied to determine the best way to combine the several sub problem solutions. Finally, a statistical study is made with a sample of 5 real problems of a wiring harness company in order to analyze the existence of common characteristics in their resolutions, by applying a Greedy algorithm. Based on some results of the previous study and since for real world applications this algorithm may take longer than desired to find a solution, two variants of this algorithm are considered, those resulting from restrictions in the search made by the original algorithm in order to make it faster. A small computational study is presented in order to compare the several variants of the algorithm.