Submitted by Secretaria Pós de Produção (tpp@vm.uff.br) on 2017-07-27T19:12:43Z
No. of bitstreams: 1
D2016 - Frederico Galaxe Paes.pdf: 5062594 bytes, checksum: 6141e589af7945cfd88fe0b9b3d62443 (MD5) / Made available in DSpace on 2017-07-27T19:12:43Z (GMT). No. of bitstreams: 1
D2016 - Frederico Galaxe Paes.pdf: 5062594 bytes, checksum: 6141e589af7945cfd88fe0b9b3d62443 (MD5) / Este trabalho aborda os seguintes problemas: Problema Quadrático de Alocação (PQA), Problema de Leiaute de Facilidades com Áreas Diferentes (PLFAD) e o Problema Job Shop Sem Espera (PJSSE). O PQA é um clássico problema de otimização combinatória, cujo objetivo é minimizar a soma das distâncias entre pares de locais distintos, ponderadas pelos fluxos entre as facilidades neles alocadas. O objetivo desta parte do trabalho é investigar técnicas heurísticas da literatura com base num conjunto de instâncias de referência do PQA. Os experimentos relatadosenvolveramAlgoritmosMeméticos(AM),técnicasdediversidadeadaptativa,algoritmos ILS (Iterated Local Search), busca locais 2-exchange e cadeia de ejeção (Ejection Chain). Doze algoritmos foram testados em 37 instâncias de referência obtidas da QAPLIB levando à escolha da combinação de técnicas mais adequada ao problema. A partir das observações obtidas do estudo anterior, decidiu-se abordar o PLFAD, de natureza semelhante ao PQA. No PLFAD, o objetivo é dimensionar e localizar facilidades retangulares em um espaço ilimitado e contínuo, sem sobreposição, de modo a minimizar a soma das distâncias entre facilidades ponderada pelos fluxos de manuseio de material. Porém, a pesquisa mostrou que devido a estrutura amarrada apresentada pelas soluções do PLFAD, métodos tradicionais de busca local tornam o problema caro computacionalmente, principalmente pelo tratamento da inviabilidade, devido a sobreposição. Duas abordagens algorítmicas são então introduzidas para tratar o problema: um Algoritmo Genético (GA) básico e um GA combinado com uma estratégia de decomposiçãoviadesconstruçãoereconstruçãoparcialdasolução. Paradecomporeficientemente o problema, uma estrutura especial é imposta às soluções impedindo que as facilidade cruzem os eixos X ou Y. Embora esta restrição possa deteriorar o valor da melhor solução encontrada, ela também aumenta muito a capacidade de busca do método em problemas de médio e grande porte. Comomostradopelosexperimentos,oalgoritmoresultanteproduzsoluçõesdealtaqualidadepara doisgruposdeinstânciasclássicasdaliteratura,melhorando6das8melhoressoluçõesconhecidas do primeiro grupo e todas as instâncias de médio e grande porte do segundo grupo. Para algumas das maiores instâncias do segundo grupo, com 90 ou 100 facilidades, a melhora média das soluções ficou em torno de6%ou7%quando comparado aos algoritmos anteriores, com menor tempo de CPU. Para tais instâncias, métodos exatos atuais são impraticáveis. Finalmente é apresentado o PJSSE, escolhido devido às suas soluções apresentarem uma natureza semelhante àquelas do PLFAD. Uma algoritmo baseado em GA, cuja construção da solução é efetuada por um algoritmo guloso eficiente, é proposto para resolver instâncias de referência da literatura obtendo resultados promissores e com menor tempo computacional comparado com abordagens anteriores, principalmente em instâncias de grande porte. / This work address the following problems: Quadratic Assignment Problem (QAP), Unequal Area Facility Layout Problem (UA-FLP), and the Job Shop Problem No-Wait (JSPNW). The QAP is a classic combinatorial optimization problem, which aims to minimize the sum of distances between pairs of different locations, weighted by flows between facilities allocated in them. The objective of this part of the work is to investigate heuristic techniques of the literature based on a benchmark datasets of the QAP. We perform experiments with Memetic Algorithms (MA), adaptive diversity techniques, Iterated Local Search (ILS) algorithms, local searches 2−exchange andEjectionChains. Twelvealgorithmshavebeentestedin37benchmarkdatasets obtained from QAPLIB thus enabling to identify a combination of more suitable techiques for the problem. Based on the observations of the previous study, we decided to address the UA-FLP, of similar nature to QAP. The UA-FLP, aims to dimension and locate rectangular facilities in an unlimited floor space, without overlap, while minimizing the sum of distances among facilities weighted by “material-handling"flows. However, the research has shown that due to the tight structure of good UA-FLP solutions, traditional methods of local search make the problem expensive computationally, mainly by infeasibility treatment due to overlap. We introduce two algorithmic approaches to address this problem: a simple Genetic Algorithm (GA), and a GA combined with a decomposition strategy via partial solution deconstructions and reconstructions. To efficiently decompose the problem, we impose a solution structure where no facility should cross the X or Y axis. Although this restriction can possibly deteriorate the value of the best achievable solution, it also greatly enhances the search capabilities of the method on medium and large problems. As highlighted by our experiments, the resulting algorithm produces solutions of high quality for the two classic datasets of the literature, improving 6 out of the 8 best known solutions from the first set and all medium- and large-scale instances from the second set. For some of the largest instances of the second set, with 90 or 100 facilities, the average solution improvement goes as high as 6% or 7% when compared to previous algorithms, in less CPU time. For such instances, current exact methods are impracticable. Finally is presented the PJSSE, chosen because of its solutions present a nature similar to those of PLFAD. An algorithm based on GA, where the construction of the solution is made by an greedy eficient algorithm, is proposed to solve benchmark instances of the literature. Promising results have been achieved in less CPU-time than previous approaches, especially for larger scale instances.
| Identifer | oai:union.ndltd.org:IBICT/oai:https://app.uff.br/riuff:1/4077 |
| Date | 27 July 2017 |
| Creators | Paes, Frederico Galaxe |
| Contributors | Ochi, Luiz Satoru, Vidal, Thibaut Victor Gaston, Penna, Puca Huachi Vaz, Coelho, Igor Machado, Alvim, Adriana Cesario de Faria, Pessoa, Artur Alves |
| Publisher | Niterói |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFF, instname:Universidade Federal Fluminense, instacron:UFF |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds