Pesquisa Operacional | |
Uma heurística de trocas para o problema de sequenciamento de tarefas em processadores uniformes | |
Felipe Martins Müller2  Sergio João Limberger1  | |
[1] ,Universidade Federal de Santa Maria Centro de Tecnologia Departamento de Eletrônica e ComputaçãoSanta Maria RS | |
关键词: Problemas de Seqüenciamento; Otimização Combinatória; Heurísticas; scheduling problems; combinatorial optimization; heuristics; | |
DOI : 10.1590/S0101-74382000000100005 | |
来源: SciELO | |
【 摘 要 】
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.
【 授权许可】
CC BY
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202103040083720ZK.pdf | 151KB | download |