Título: Algoritmo Híbrido De ACS E AG Para Minimizar O Makespan Do Problema De Job Shop Com Tempo De Processamento Incerto
Autores: Carvalho, Márcia Braga de; Yamakami, Akebo; Bonfim, Tatiane Regina
Resumo: Neste artigo apresentaremos uma hibridização entre os algoritmos de otimização por colônia de formigas e o algoritmo genético (AG) para resolver o problema de escalonamento job shop com tempo de processamento incerto e com o objetivo de minimizar o makespan fuzzy do problema. Como o problema job shop é considerado NP-difícil, sua resolução através de métodos convencionais torná-se inviável. Desta forma neste artigo propomos uma nova abordagem híbrida que trabalha com os algoritmos ant colony system (ACS) e algoritmo genético com busca local conhecido como algoritmo memético (MA) com a finalidade de obter um conjunto de escalonamentos com alto grau de possibilidade de serem ótimos. Implementamos 4 versões híbridas para resolver o problema e testamos estas versões em 10 problemas conhecidos da literatura.
Palavras-chave: Escalonamento job shop; tempo de processamento incerto; sistema de colônia de formigas; algoritmo genético
Páginas: 8
Código DOI: 10.21528/CBIC2011-33.6
Artigo em pdf: st_33.6.pdf
Arquivo BibTex: st_33.6.bib