Apresentações
Uma meta-heurística para o problema do job shop
Jorge José de Magalhães Mendes
— ISEP
Nesta comunicação apresenta-se um algoritmo genético híbrido para a resolução do Problema Job Shop. A representação cromossómica utiliza chaves aleatórias. O sequenciamento das operações é realizado com recurso a uma heurística baseada em prioridades definidas pelo algoritmo genético.
A heurística gera sequenciamentos activos parametrizados. Após a obtenção de um sequenciamento é aplicada uma heurística de pesquisa local para melhorar a solução. O algoritmo é testado num conjunto de problemas padrão retirados da literatura da especialidade e é comparado com outras abordagens. Os resultados computacionais validam o bom desempenho do algoritmo em termos de qualidade da solução.
Palavras-chave:
Job Shop, Planeamento (Scheduling), Algoritmos Genéticos, Chaves Aleatórias.
Referências:
“A hybrid genetic algorithm for the job shop scheduling problem”, European Journal of Operational Research, Vol. 167, pp. 77-95, 2005 (co-autores: José F. Gonçalves e Maurício G. C. Resende).
"Uma Meta-heurística para o Job Shop Problem", Actas do Congreso de Métodos Numéricos en Ingeniería 2005, Granada - Espanha, 4-7 de Julho de 2005 (coautores: José F. Gonçalves e M.G.C. Resende).