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

AUTOR(ES)

Müller, Felipe Martins, Dias, Odon Bastos, Araújo, Olinto César Bassi de

FONTE

Production

DATA DE PUBLICAÇÃO

2002

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.

ASSUNTO(S)

seqüenciamento máquinas não-relacionadas busca local heurísticas

Documentos Relacionados

• Um problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes de máquina e da sequência:: modelos e algoritmos exato.
• Programação em maquinas paralelas não-relacionadas, sujeitas a divisão de tarefas
• Heurísticas para o Problema de Dimensionamento de Lotes com Máquinas Paralelas Flexíveis
• Heuristicas para a minimização dos atrasos em sequenciamento de maquinas paralelas com tempos de preparação dependentes da sequência
• Evolutionary Algorithms for Parallel Machine Scheduling Problems with Sequence Dependent Setup Times