Practical comparison of approximation algorithms for scheduling problems

Autor(es)

Eduardo Candido Xavier ^[1] ; Flávio K. Miyazawa ^[2]

Afiliação do(s) autor(es)

^[1] Universidade Estadual de Campinas. Instituto de Computação

^[2] Universidade Estadual de Campinas. Instituto de Computação

• Tipo de documento: Artigo Científico
• Fonte: Pesquisa Operacional; v. 24, n. 2, p. 227-252, 2004-08-00.

Resumo

In this paper we consider an experimental study of approximation algorithms for scheduling problems in parallel machines minimizing the average weighted completion time. We implemented approximation algorithms for the following problems: P|r j|sigmaCj, P||sigmaw jCj, P|r j|sigmaw jCj, R||sigmaw jCj and R|r j|sigmaw jCj. We generated more than 1000 tests over more than 200 different instances and present some practical aspects of the implemented algorithms. We also made an experimental comparison on two lower bounds based on the formulations used by the algorithms. The first one is a semidefinite formulation for the problem R||sigmaw jCj and the other one is a linear formulation for the problem R|r j|sigmaw jCj. For all tests, the algorithms obtained very good results. We notice that algorithms using more refined techniques, when compared to algorithms with simple strategies, do not necessary lead to better results. We also present two heuristics, based on approximation algorithms, that generate solutions with better quality in almost all instances considered. (AU)

• Processo FAPESP: 01/04412-4 - Algoritmos de aproximação para problemas de escalonamento de tarefas
• Beneficiário: Eduardo Candido Xavier
• Modalidade de apoio: Bolsas no Brasil - Mestrado