O problema de sequenciamento com restrições de cadência

Este trabalho é fruto da colaboração com uma grande empresa multinacional de automóveis, que impõe dois tipos de cadência no sequenciamento de suas operações de montagem, para que tarefas com atributos mais exigentes não sejam alocadas próximas umas das outras. O objetivo é sequenciar o número máximo de tarefas consecutivas, respeitando as restrições mencionadas. O problema de sequenciamento é aqui formalizado e provado ser fortemente NP-completo. Uma formulação de programação inteira é proposta, bem como uma formulação que encontra uma sequência viável com dado número de tarefas, se assim existir. Esta última é utilizada em algoritmos de busca binários e iterativos, aprimorados pelos limites dual combinatório e primal heurístico. Resultados computacionais revelaram melhor performance dos seguintes algoritmos: busca binária com limites dual trivial ou combinatório e primal heurístico; e busca iterativa com limite dual combinatório. As instâncias que refletem as demandas da empresa são resolvidas na otimalidade em segundos.