Modelos matemáticos para programação de job shop com tempos de setup independentes da sequência

Este trabalho aborda o problema de programação da produção em job shop com tempos de setup explícitos e independentes da sequência de processamento das tarefas visando minimizar a duração total da programação (makespan). Na conhecida notação de três campos, este problema é representado por Jm|sjk|Cmax. O ambiente job shop é aquele em que há um conjunto de máquinas ou recursos diferentes que devem processar um conjunto de tarefas, sendo que cada tarefa possui uma rota específica e pré-determinada para processamento nas máquinas. Para problemas com duas máquinas, nesta pesquisa propõe-se uma adaptação no clássico Algoritmo de Jackson, que fornece a solução ótima para o caso com setup incluído nos tempos de processamento das tarefas. E para problemas genéricos com m máquinas, foram elaborados e implementados dois modelos matemáticos de programação linear inteira mista para os casos de setup antecipado (aquele que pode ser iniciado antes da liberação da tarefa) e não antecipado, que fornecem soluções em tempo computacional viável para problemas-testes com até 20 tarefas e 7 máquinas.