Esta pesquisa investiga problemas de escalonamento com penalidades de antecipação
e atraso em ambiente mono e multiprocessado envolvendo máquinas paralelas. Este
problema é também conhecido na literatura como escalonamento Just-in-Time, sistema
amplamente utilizado em indústrias para reduzir estoques e os custos decorrentes, a fim
de que o produto seja produzido de acordo com a demanda. Neste trabalho é proposta
uma estratégia algorítmica híbrida exato-heurística, baseada em uma formulação de
programação inteira arc-time e um algoritmo evolucionário fortemente baseado em
busca local, para melhor resolver problemas clássicos de escalonamento em máquinas
paralelas envolvendo penalidades de antecipação e atraso, com tarefas independentes e
tempos de processamento arbitrários. Os arcos são selecionados das soluções ótimas
locais obtidas pelo algoritmo genético fortemente baseado em busca local (GLS) com
movimentos generalizados de troca de pares, que são fornecidos como entrada para
a formulação arc-time, para gerar soluções melhores do que as obtidas por ambos
os métodos quando utilizados isoladamente. Os experimentos computacionais apresentam
resultados competitivos em relação à literatura. O método proposto também
resolve instâncias de tamanho maior de até 500 tarefas em máquinas paralelas idênticas.
|
