Evolutionary heuristic for programming problems in no-wait flowshop with setup times

Este trabalho aborda o problema de no-wait flowshop em um ambiente com custos de setup apartados dos tempos de processamento, são investigados os casos de setups dependentes e independentes da seqüência para makespan e total flowtime. Diversas aplicações práticas podem ser modeladas sob estas suposições, dentre elas destacamos a indústria química e alimentícia. É proposta uma metaheurística evolutiva baseada em algoritmo genético e clustering search e seus resultados são comparados com os métodos de Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) através dos bancos de dados de Ruiz e Stützle (2008) e Ruiz e Allahverdi (2007). Os métodos são avaliados segundo o percentual de sucesso e desvio relativo médio. Os resultados obtidos demonstram a superioridade do método proposto para problemas de grande porte.This work intends to research the no-wait flowshop scheduling problem with setup times separated from the processing costs; the both cases where the sequence is dependent and independent are targeted for makespan and total flowtime. There are numerous practical situations that can be modeled under these assumptions, such as, chemical industry, food processing, etc. A hybrid metaheuristic method based on a genetic algorithm and clustering search is proposed and its results are compared to the methods of Brown et al (2004), França et al (2006) e Ruiz e Allahverdi (2007) using the data base from Ruiz e Stützle (2008) and Ruiz e Allahverdi (2007). The methods are evaluated as regarding the success rate and average relative deviation. The results show that the proposed method delivers better solutions for problems with higher complexity