Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/16185
Title in Portuguese: Algoritimo genético aplicado aos problema de seqüenciamento permutacional flowshop sem e com restrição de espera
Title: Genetic algorithm applied to the permutational flowshop scheduling problem without and with wait restriction
Author: Gomes, Francisco Régis Abreu
Advisor(s): Silva, José Lassance de Castro
Keywords: Logística
Algoritmo genético
Diversificação e intensificação
Issue Date: 15-Feb-2008
Citation: GOMES, F. R. A. (2008)
Abstract in Portuguese: Neste trabalho foram tratados dois problemas: o primeiro é denominado Continuous Permutation Flowshop Scheduling Problem (CPFSP), que possui a restrição de que nenhuma tarefa pode esperar por processamento entre máquinas consecutivas; o segundo é denominado de Permutation Flowshop Scheduling Problem (PFSP), em que a restrição anterior não existe. A metaheurística Algoritmo Genético (AG) tem sido aplicada com sucesso ao PFSP, mas até o momento não foi encontrado na literatura algo que mostre que o AG é um bom método para o CPFSP. O objetivo deste trabalho foi desenvolver um AG eficiente paras esses dois problemas, mas que não precisa utilizar inicialização eficiente e/ou hibridização com outra técnica de busca. O desenvolvimento do AG proposto levou em consideração as características, diversificação e a intensificação, que inspiraram a criação de três procedimentos que melhoraram o desempenho do AG proposto. Foram realizados vários experimentos com as instâncias de Taillard (1993), Reeves (1995) e Heller (1960). Os resultados foram comparados com outros métodos encontrados na literatura. Foram construídos polinômios com a utilização de Interpolação Lagrangeana para determinar o tempo execução do AG proposto. Por fim, o método foi aplicado num problema real. Os resultados mostraram que o AG proposto é o melhor método para o CPFSP e que fica muito próximo do melhor AG encontrado na literatura com inicialização eficiente para o PFSP
Abstract: In this work two problems were solved: the first is Continuous Perm utation Flowshop Scheduling Problem (CPFSP) it possesses the constraint that no j ob can wait for processing among serial machines; the second is Permutation Flowshop Scheduling Problem (PFSP), in that the previous restriction does not exist. The metaheurist ic Genetic Algorithm (GA) has been applied with success for solving the PFSP, but up to now it was not found in the literature something that shows that GA is a good method for CPFS P. The objective of this work was to develop an efficient GA for both problems, but that does not need to use an initialization efficient and/or hybridization allied with other se arch technique. The development of proposed GA took in consideration the characteristics, diversification and the intensification, that inspired the creation of three procedure s that further improved the proposed GA. Several experiments were accomplished with the ins tances of Taillard (1993), Reeves (1995) and Heller (1960). The results were compared wi th other methods found in the literature. Polynomials were built with Lagrangeana's Interpolation use to determine the time execution of proposed GA. Finally, the method wa s applied in a real problem. The results showed that proposed GA is the best method for CPFSP and that is very close of best GA found in the literature with efficie nt initialization for PFSP.
Description: GOMES, F. R. A. Algoritimo genético aplicado aos problema de seqüenciamento permutacional flowshop sem e com restrição de espera. 2008. 141 f. Dissertação (Mestrado em Logística e Pesquisa Operacional) – Pró-Reitoria de Pesquisa e Pós-Graduação, Universidade Federal do Ceará, Fortaleza, 2008.
URI: http://www.repositorio.ufc.br/handle/riufc/16185
metadata.dc.type: Dissertação
Appears in Collections:GESLOG - Dissertações defendidas na UFC

Files in This Item:
File Description SizeFormat 
2008_dis_fragomes.pdf968,95 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.