Several studies have been carried out regarding optimizing production scheduling in industrial environments. As a result, new variants related to several problems have been incorporated into this study area to cover the most diverse cases presented in productive environments. In this sense, this dissertation aimed to study a production scheduling problem little stressed in the literature, the production scheduling problem in an open shop environment with many applications in the industrial and services areas. In this study, we observed essential constraints for the described environment, which became new variants for the problem: the sequence-dependent setup times; the study of blocking machines in the processing of operations; the study of reprocessing or repetition of operations in the production process and the delivery of products through the vehicle routing. The objective of these problems was to minimize the total duration of the schedule (makespan). We proposed heuristic methods for modeling and solving these problems, such as priority rules, constructive techniques, bio-inspired meta-heuristics, and mathematical programming methods such as integer linear programming and constraint programming models and matheuristics. For the computational tests, we ran the methods with robust data from classical literature instances adapted to the constraints of the problems under consideration and new instances proposed during the study. The results showed that the proposed exact and approximate methods provided quality solutions with computational efficiency and were competitive compared to the literature methods.

Nos últimos anos, diferentes estudos têm sido realizados no que tange à otimização da programação de tarefas em ambientes produtivos. Novas variantes, relacionadas a diferentes problemas, têm sido incorporadas a essa área de estudo a fim de se adequar ao maior número possível de ambientes reais de produção. Dentro desse contexto, a tese visou o estudo do problema de programação da produção em ambiente open shop. O open shop é um ambiente de produção pouco destacado na literatura, quando comparado aos ambientes clássicos de produção como o flow shop e o job shop, e possui diversas aplicações nos setores industriais e de serviços. Nesse estudo, foram observadas importantes características para o ambiente retratado, as quais se transformaram nas seguintes novas variantes para o problema: a consideração de tempos de preparação (setups) explícitos, dependente da sequência das operações e das máquinas; a existência de bloqueio de máquinas no processamento das operações; a existência de reprocessamento ou repetição de operações no processo produtivo; e a entrega dos produtos por meio da roteirização de veículos. O objetivo desses problemas foi encontrar soluções que minimizem algum indicador sobre o nível de serviço da operação, como a duração total da programação (makespan). Para a modelagem e a resolução desses problemas, foram utilizados métodos heurísticos: regras de prioridades; técnicas construtivas e meta-heurísticas bioinspiradas; e métodos de programação matemática, como modelos de programação linear inteira e de programação por restrições e mateurísticas. Para os testes computacionais, os métodos foram executados com dados robustos, advindos de clássicas instâncias da literatura adaptadas para as restrições dos problemas em consideração ou instâncias novas propostas durante o trabalho. Os resultados mostraram que os métodos exatos e aproximados forneceram soluções de alta qualidade e com eficiência computacional, sendo competitivos quando comparados com os atuais métodos da literatura.