Anais do Simpósio Brasileiro de Pesquisa Operacional
Anais do Simpósio Brasileiro de Pesquisa Operacional

Este artigo aborda um problema de sequenciamento de lotes de tarefas em máquinas paralelas uniformes com capacidades diferentes. As tarefas possuem tamanhos diferentes e são classificadas em famílias. Os lotes são formados com tarefas da mesma família e o tamanho de um lote deve respeitar a capacidade da máquina. O problema consiste em agrupar as tarefas em lotes e sequenciar os lotes formados nas máquinas de tal maneira que o tempo máximo de conclusão de todos os lotes (makespan) seja minimizado. Neste trabalho, inicialmente é proposto um modelo de Programação Linear Inteira Mista a fim de obter soluções ótimas para instâncias pequenas do problema. Como o problema é NP-Difícil, para resolver instâncias de grande porte, propõe-se um algoritmo heurístico de Evolução Diferencial Discreta com Busca Local (DDE-H). O bom desempenho do algoritmo proposto é avaliado através da comparação com um algoritmo Iterated Greedy e um algoritmo DDE da literatura.