Uma heurística de trocas para o problema de sequenciamento de tarefas em processadores uniformes
AUTOR(ES)
Müller, Felipe Martins, Limberger, Sergio João
FONTE
Pesquisa Operacional
DATA DE PUBLICAÇÃO
2000-06
RESUMO
O sequenciamento de tarefas independentes de forma não preemptiva em sistemas de processadores uniformes, com o objetivo de minimizar o tempo total de execução (makespan), é o assunto do presente artigo. Considera-se um conjunto de n tarefas, onde cada tarefa possui um tempo de processamento, e um conjunto m > ou = 2 de processadores com velocidades de processamento sigma1 = 1£s2<= ...£sm. Sendo o problema de encontrar o mínimo makespan considerado NP-difícil, desenvolveu-se uma heurística de trocas poderosa para resolvê-lo. A heurística proposta é composta de três fases: alocação inicial, balanceamento de carga e fase de dupla troca. A principal característica desta nova heurística é a de prescindir de uma pré-ordenação das tarefas. A heurística desenvolvida foi comparada com um limitante inferior da solução ótima e também com outras três heurísticas apresentando um desempenho superior, encontrando a solução ótima em um grande número de casos as custas de um baixo esforço computacional.
ASSUNTO(S)
problemas de seqüenciamento otimização combinatória heurísticas
Documentos Relacionados
- Uma nova heurística para o problema de minimização de trocas de ferramentas
- Sequenciamento de processadores paralelos utilizando a meta heurística busca Tabu
- Algoritmos heuristicos e exatos para resolução do problema de sequenciamento em processadores paralelos
- Otimização por colônia de formigas para o problema de sequenciamento de tarefas em uma única máquina com terceirização permitida
- Otimização bi-objetivo para o problema de sequenciamento de tarefas em uma maquina com tempos de preparação dependentes da sequencia