Título: Um Algoritmo Baseado Em Iterated Local Search Para O Problema De Sequenciamento Em Máquinas Paralelas Não-Relacionadas Com Tempos De Preparação Dependentes Da Sequência
Autores: Haddad, Matheus Nohra; Souza, Marcone Jamilson Freitas; Santos, Haroldo Gambini; Silva, Leandro Augusto de Araújo
Resumo: Este trabalho aborda o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência. O objetivo é minimizar o tempo máximo de conclusão do sequenciamento, o chamado makespan. Visando sua resolução, é proposto um algoritmo heurístico, nomeado ILSVNDPR, que combina os procedimentos heurísticos Iterated Local Search (ILS), Variable Neighborhood Descent (VND) e Path Relinking (PR). O procedimento VND examina o espaço de soluções por meio de trocas de estruturas de vizinhanças baseadas em movimentos de inserções e trocas de tarefas. Após a determinação de um ótimo local em relação à s vizinhanças adotadas, aplica-se o procedimento PR com uma dada probabilidade, conectando esse ótimo local a uma solução elite formada durante o processo de busca. O algoritmo foi testado em conjuntos de problemas-teste da literatura e seus resultados comparados a uma versão do mesmo sem a aplicação do procedimento PR, assim como com dois algoritmos genéticos da literatura. Os experimentos computacionais mostraram que os resultados alcançados pelos algoritmos propostos superaram os resultados da literatura, em termos de qualidade da solução e variabilidade da solução. Também foram obtidos, para a maioria dos problemas-teste, novos limites superiores.
Palavras-chave: Sequenciamento em máquinas paralelas; Iterated Local Search; Variable Neighborhood Descent; Reconexão por Caminhos; makespan
Páginas: 8
Código DOI: 10.21528/CBIC2011-29.4
Artigo em pdf: st_29.4.pdf
Arquivo BibTex: st_29.4.bib