Algoritimo genético aplicado aos problema de seqüenciamento permutacional flowshop sem e com restrição de espera

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.