Practical comparison of approximation algorithms for scheduling problems

Pesquisa Operacional

Eduardo Candido Xavier¹  Flávio K. Miyazawa¹ 

[1] ,Universidade Estadual de Campinas Instituto de Computação Campinas SP

关键词: approximation algorithms;    practical analysis;    scheduling;    algoritmos de aproximação;    análise prática;    escalonamento;   

DOI  :  10.1590/S0101-74382004000200002

来源: SciELO

【 摘 要 】

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.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License