O problema de programação de operações em ambiente no-wait flow shop tem sido abordado desde a década de 60. Por se tratar de um ambiente em que as tarefas devem ser processadas continuamente e sem interrupções entre uma máquina e outra, um tempo de espera entre o início da tarefa anterior e o início da tarefa atual deve ser determinado na primeira máquina. Neste sentido, uma vez que a tarefa inicia seu processamento, as máquinas devem estar disponíveis para que atendam a restrição de no-wait. Portanto, operações de manutenção preventiva são necessárias para que a programação seja atendida sem maiores problemas. Este trabalho aborda dois problemas: no-wait flow shop e no-wait flow shop com operações de manutenção preventiva. O critério de desempenho adotado foi a duração total da programação (makespan). Por meio de uma revisão de literatura, mecanismos de construção de soluções foram identificadas e classificadas e, baseando-se em tais, novos métodos heurísticos construtivos simples e compostos foram propostos para o problema no-wait flow shop e uma heurística composta foi desenvolvida considerando as operações de manutenção preventiva. Experimentações computacionais para os dois problemas foram realizadas para fins de comparação e avaliação dos métodos propostos com os métodos heurísticos construtivos da literatura. Para o problema F_m|no - wait|C_max resultados evidenciaram que as heurísticas propostas H4GPSL_LS e MH4GPSL_LS superaram as heurísticas da literatura em qualidade de solução, com diferença estatisticamente significativa no nível de 5% de significância. Para o problema F_m|no - wait, m(k)|C_max, pode-se constatar que a heurística BIH_LS e as heurísticas H4GPSL_LS e MH4GPSL_LS apresentaram desempenho superior com diferença estatística significativa no nível de 5% de significância em comparação as heurísticas da literatura.

The no-wait flow shop scheduling problem has been studied since 60's. In this environment, jobs must be processed continuously without interruption between one machine and another, and because of this, a delay between the start time of the previous job and the start time of the current job must be determined in the first machine. In this sense, since a job starts its processing, the machines must be available to respect the no-wait constraint. Therefore, preventive maintenance operations are needed. This work adresses two problems: the m machine no-wait flow shop and the m machine no-wait flow shop with preventive maintenance operations. The performance measure adopted was the makespan. By means of a literature review, mechanisms of solution construction were identified and classified. New simple and composite constructive heuristics were proposed to the no-wait flow shop problem and a new composite constructive heuristic was developed considering the preventive maintenance operations. Computational experiments and their respective analyses for both problems were carried out to compare and evaluate the performance between the proposed methods and the constructive heuristics of the literature. Regarding F_m|no - wait|C_max problem, results show that the proposed heuristics H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature in quality of the solution and is statistically significative to 5% of significance level. To the F_m|no - wait, m(k)|C_max problem it can be seen that the proposed heuristic BIH_LS and H4GPSL_LS and MH4GPSL_LS outperformed the heuristics of the literature and is statistically better to 5% of significance level.