Practical comparison of approximation algorithms for scheduling problems
AUTOR(ES)
Xavier, Eduardo Candido, Miyazawa, Flávio K.
FONTE
Pesquisa Operacional
DATA DE PUBLICAÇÃO
2004-08
RESUMO
Neste artigo consideramos um estudo experimental de alguns algoritmos aproximados para problemas de escalonamento em máquinas paralelas onde se deve minimizar o tempo de término ponderado das tarefas. Foram implementados algoritmos aproximados para os seguintes problemas: P|r j|sigmaCj, P||sigmaw jCj, P|r j|sigmaw jCj, R||sigmaw jCj and R|r j|sigmaw jC j . Foram gerados mais de 1000 testes sobre mais de 200 instâncias diferentes e com isso apresentamos aspectos práticos dos algoritmos implementados. Também fizemos um estudo experimental sobre dois limitantes inferiores baseados em formulações usadas pelos algoritmos. A primeira é uma formulação semidefinida para o problema R||sigmaw jCj e a outra é uma formulação linear para o problema R|r j|sigmaw jCj. Em todos os testes os algoritmos obtiveram resultados muito bons. Notamos que algoritmos usando técnicas mais refinadas, quando comparados com algoritmos que usam estratégias simples, não necessariamente geram soluções melhores. Também apresentamos duas heurísticas, baseadas nos algoritmos aproximados, que geram soluções de melhor qualidade em quase todas as instâncias consideradas.
ASSUNTO(S)
algoritmos de aproximação análise prática escalonamento
Documentos Relacionados
- Algoritmos para problemas de escalonamento em grades
- Approximation algorithms
- A comparison of simulated annealing algorithms in the scheduling of multiproduct serial batch plants
- Evaluation of non-singular BEM algorithms for potential problems
- Food webs: a ladder for picking strawberries or a practical tool for practical problems?