Publicação
Algoritmo para o problema de seqüenciamento em máquinas paralelas não-relacionadas
| Resumo: | 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. |
|---|---|
| Autores principais: | Müller,Felipe Martins |
| Outros Autores: | Dias,Odon Bastos; Araújo,Olinto César Bassi de |
| Assunto: | Seqüenciamento Máquinas não-relacionadas Busca local Heurísticas |
| Ano: | 2002 |
| País: | Brasil |
| Tipo de documento: | artigo |
| Tipo de acesso: | acesso aberto |
| Instituição associada: | IBICT |
| Idioma: | português |
| Origem: | Oasisbr |
| Resumo: | 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. |
|---|
Atividades financiadas
Não foram encontrados projetos financiados.