O problema de programação de operações ou scheduling é um processo de decisão que desempenha um papel crucial em muitas indústrias de manufatura e de serviços. Sua essência concentra-se nas atividades de alocação e sequenciamento. Neste contexto, é de grande importância o desenvolvimento de técnicas que auxiliem na tomada de decisão da sequência de produção. De acordo com a revisão de literatura realizada nesta pesquisa, análises e proposição de técnicas de solução para o denominado ambiente de produção flow shop sem estoques intermediários entre as máquinas (bloqueio) vem ganhando notoriedade nas últimas décadas, na sua maioria, sem a adição de restrições adicionais. Levando-se em conta a lacuna encontrada na literatura para esta área, nesta tese são propostos métodos de solução para o problema de programação de operações em ambientes flow shop com m máquinas, considerando bloqueio, tempos de setup dependentes da sequência e ocorrência de manutenção preventiva. As funções-objetivo tratadas foram a minimização da duração total da programação e do tempo total de fluxo dado que o custo total de manutenção preventiva exigido pela sequência não ultrapasse um dado valor. Um modelo de programação linear inteira mista (MILP) e formas de cálculo das datas de início e término das tarefas. Uma busca local para avaliação do reposicionamento das MPs foi desenvolvida para minimização da função-objetivo. Métodos heurísticos (construtivos e metaheurísticas) encontrados para os problemas de minimização da duração total da programação (C_max) e do tempo total de fluxo (Σ _iC_i) foram adaptados e propostos, no intuito de minimizar as funções-objetivo. Os métodos foram implementados e testados em dois cenários de ocorrência de manutenções preventivas, com instâncias de problemas de pequeno, médio e grande portes. Resultados estatísticos mostraram que em comparação com o MILP proposto, as metaheurísticas Iterated Greedy e GRASP(HPF2) obtiveram os melhores desempenhos para a minimização de C_max e de Σ_iC_i, respectivamente, em problemas de pequeno porte. Para problemas de médio e grande portes, Iterated Greedy e Variable Block Insertion Heuristic (VBIH) apresentaram o melhor desempenho geral nos dois cenários avaliados. Por fim, pode-se constatar experimentalmente que a busca local proposta obteve melhorias significativas e expressivas na qualidade da solução gerada pelas metaheurísticas, o que sugere seu uso como parte da metodologia de solução dos problemas estudados.

Scheduling is a decision process that plays a crucial role in many manufacturing and service industries. Its essence focuses on allocation and sequencing decisions. In this context, it is of great importance the development of techniques that can be used as a support to the decision making of the production sequence. According to the literature review carried out in this research, analysis and proposition of solution techniques for the so-called blocking flow shop scheduling problem has gained notoriety over the last decades, mostrly without the additional constraints. Taking into account the gap found in the literature for this area, in this thesis is addressed the m-machine blocking flow shop scheduling problem, with sequence-dependent setup times, preventive maintenance operations occurrences and minimization of hierarchical objective functions. The research aims to propose solution techniques to minimize the makespan (C_max) and the total flow time (Σ_iC_i) given that the preventive maintenance total cost required by the sequence does not exceed a given value. A mixed integer linear programming (MILP) and forms of objective-fucntion computation were proposed. A local search for MP rescheduling was developed, aiming to minimize the objective-functions. Heuristic methods of the literature for the minimization of C_max and Σ_iC_i have been adopted to minimize the preventive maintenance total cost and the hierarquical objective-functions of the approached problems. The methods were implemented and tested over two preventive maintenance instance problems configurations. Statistical results showed that, compared to the proposed MILP, the Iterated Greedy and GRASP(HPF2) obtained the best performances for the C_max and Σ_iC_i minimization, respectively. For medium and large problems, Iterated Greedy and VBIH showed the best overall performances in both evaluated scenarios. Finally, it can be seen that the proposed local search significantly improved the quality solution generated by the metaheuristics, which suggests its use as part of the solution methodology of the problems studied here.