Algoritmo para o problema de seqüenciamento em máquinas paralelas não-relacionadas

Production

Felipe Martins Müller²  Odon Bastos Dias¹  Olinto César Bassi De Araújo¹ 

[1] ,Universidade Federal de Santa Maria Centro de Tecnologia Programa de Pós-Graduação em Engenharia de Produção

关键词: Seqüenciamento;    Máquinas não-relacionadas;    Busca local;    Heurísticas;    Scheduling;    Unrelated machines;    Local search;    Heuristics;   

DOI  :  10.1590/S0103-65132002000200002

来源: SciELO

【 摘 要 】

Este trabalho trata do problema de seqüenciamento de n tarefas independentes em m máquinas paralelas não-relacionadas com o objetivo de minimizar o tempo de execução da máquina mais carregada (makespan). É proposto um novo algoritmo de busca local em conexão com um esquema de vizinhança que usa estrutura de intervalos e o conceito de eficiência das máquinas para cada tarefa. O algoritmo proposto, denominado Mutat, é comparado com outros algoritmos para avaliar a qualidade das soluções obtidas. A nova abordagem encontra soluções que superam, em qualidade e tempo computacional, o melhor algoritmo de busca local encontrado na literatura para este problema.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License