Abordagens Exatas e Algoritmo Heurístico para o Problema de Seleção e Sequenciamento de Ordens de Produção com Tempos de Setup

O problema de seleção e sequenciamento de ordens de produção (OAS) consiste em, simultaneamente, decidir quais ordens (tarefas) serão aceitas para serem processadas, assim como sua sequência associada. Esse problema geralmente surge quando uma empresa não tem a capacidade necessária para atender a demanda, sendo assim, forçadas a rejeitar algumas ordens. No presente trabalho foi considerado a variação do OAS onde cada tarefa tem um tempo de processamento, data de entrega, release date, deadline, receita e peso de penalização por atraso. Além disso, para cada par de tarefas i e j, há um tempo de setup requerido antes de ser iniciado o processamento de j se essa tarefa é sequenciada imediatamente depois da tarefa i. O objetivo é selecionar e sequenciar um subconjunto de tarefas que maximize o lucro total, que é dado pela receita total menos o total de penalização por atraso. Para resolver esse problema NP-difícil, foi proposta uma nova formulação matemática com arcos indexados no tempo que foi capaz de resolver instâncias de até 50 tarefas. Entretanto, uma vez que essa formulação depende de um número pseudo-polinomial de variáveis, instâncias maiores não são possíveis de serem resolvidas na prática. Para superar essa limitação, foi desenvolvido um algoritmo exato a partir dessa formulação baseado em uma relaxação lagrangeana. Foi implementada uma busca local baseada em um algoritmo meta-heurística para obter limites inferiores de alta qualidade. Foram realizados experimentos computacionais em 1500 instâncias que variam de 10 até 100 tarefas, e os resultados obtidos indicam que os métodos exatos e heurístico propostos são capazes de encontrar resultados extremamente competitivos quando comparados com os disponíveis na literatura.

Autores: Yuri Laio Silva; Anand Subramanian; Artur A. Pessoa