Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/24567
Type: Artigo de periódico
Title: Practical comparison of approximation algorithms for scheduling problems
Author: Xavier, Eduardo Candido
Miyazawa, Flávio K.
Abstract: 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.
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.
Subject: algoritmos de aproximação
análise prática
escalonamento
approximation algorithms
practical analysis
scheduling
Editor: Sociedade Brasileira de Pesquisa Operacional
Rights: aberto
Identifier DOI: 10.1590/S0101-74382004000200002
Address: http://dx.doi.org/10.1590/S0101-74382004000200002
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382004000200002
Date Issue: 1-Aug-2004
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
S0101-74382004000200002.pdf1.3 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.