Um algoritmo heurístico para resolver o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência

Luciano Perdigão Cota, Matheus Nohra Haddad, Marcone Jamilson Freitas Souza, Alexandre Xavier Martins

Resumo


Este trabalho trata o Problema de Sequenciamento em Máquinas Paralelas NãoRelacionadas com Tempos de Preparação Dependentes da Sequência, objetivando minimizar o makespan. É proposto um algoritmo heurístico na qual a solução inicial é gerada por meio de um método construtivo guloso, e depois refinada pelo procedimento Iterated Local Search (ILS). O ILS usa como busca local o procedimento Adaptive Local Search (ALS), desenvolvido neste trabalho. O ALS consiste de duas buscas locais e uma perturbação, sendo que cada uma delas é escolhida de acordo com uma certa probabilidade, a qual depende do sucesso em iterações pregressas. Os experimentos computacionais mostraram que o algoritmo proposto supera dois algoritmos da literatura, tanto em termos de qualidade quanto em variabilidade da solução final. Além disso, o algoritmo estabeleceu novos limites superiores em mais de 95% das instâncias.

Palavras-chave


Máquinas Paralelas, Makespan, Iterated Local Search, Adaptive Local Search

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2015.003.01.0412

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato