Otimização de leiaute utilizando busca tabu

• Ano de defesa: 1995
• Autor(a) principal: João Carlos Furtado
• Orientador(a): Luiz Antonio Nogueira Lorena
• Banca de defesa: Solon Venâncio de Carvalho, Nei Yoshihiro Soma
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Instituto Nacional de Pesquisas Espaciais (INPE)
• Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Computação Aplicada
• País: BR
• Resumo em Inglês: The search of better layouts is a combinatorial optimisation problem that arises in a wide variety of spacial planning contexts, in looking for a Layout of departments industry. Since no polinomial-time algorithm for attainning a global optimal solution is known some heuristics techniques are used. We study this subject, for a given problem, performing the following steps: 1) We generate an initial solution by using a clustering procedure; 2) We generate another initial solution, rearranging them randomly; 3) We apply the tabu search to the two initial solutions generated above; 4) We compare the results obtained in the step 3. The procedure is applied to four cases, namely, those with 12, 15, 20 and 30 facilities. In the space assigned to facilities there were occupied areas and the facilities cannot be used there, so we increased the difficulty of the problem. When we compared the initial layouts obtained in step 1 with the obtained in step 2, we conclued that step 1 obtained better layouts. From step 4, we conclued that the tabu search obtained sligthly better final layouts when applied to initial solutions generated in step 1 than those obtained starting from solutions generated in step 2. So we conclude that tabu search is an efficient search procedure independent of the quality of the initial solution.
• Link de acesso: http://urlib.net/sid.inpe.br/iris@1905/2005/07.29.00.20

A busca de melhores leiautes é um problema de otimização combinatória que surge em uma grande variedade de contextos de planejamento espacial, como no leiaute de departamentos em uma indústria. Como não existe algoritmo de otimização conhecido que obtenha uma solução ótima global em tempo polinomial, usam-se métodos heurísticos. Estudamos o assunto aplicando a seguinte sequencia de passos para um dado problema: 1) Geramos uma solução inicial através do procedimento de aglomeração; 2) Geramos uma outra solução inicial, recolocando as facilidades aleatoriamente; 3) Aplicamos a busca tabu as duas soluções iniciais geradas; 4) Comparamos os resultados obtidos no passo 3. Este procedimento é aplicado a quatro casos: os de 12, 15, 20 e 30 facilidades. No espaço destinado a alocação das facilidades já existiam áreas ocupadas e que não podiam ser utilizadas pelas facilidades, o que aumentou consideravelmente a dificuldade de tratamento do problema. Comparando os leiautes iniciais produzidos no passo 1 com os produzidos no passo 2, concluímos que o procedimento de aglomeração gerou leiautes iniciais de melhor qualidade. No passo 4, percebemos que a busca tabu, quando aplicada a solução inicial produzida pelo passo 1, gera leiautes finais de qualidade ligeiramente superiores aos obtidos, quando este procedimento é aplicado a solução inicial produzida pelo passo 2. Concluímos que independentemente da qualidade da solução inicial, a busca tabu é uma heurística eficiente no processo de busca.