| Revista: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000313081 |
| ISSN: | 0101-7438 |
| Autores: | Xavier, Eduardo Candido1 Miyazawa, Flavio K |
| Instituciones: | 1Universidade Estadual de Campinas, Instituto de Computacao, Campinas, Sao Paulo. Brasil |
| Año: | 2004 |
| Periodo: | May-Ago |
| Volumen: | 24 |
| Número: | 2 |
| Paginación: | 227-252 |
| País: | Brasil |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico, descriptivo |
| Resumen en inglés | 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 |
| Resumen en portugués | 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 |
| Disciplinas: | Matemáticas, Ingeniería |
| Palabras clave: | Matemáticas aplicadas, Ingeniería industrial, Algoritmos de aproximación, Análisis práctico, Calendarización |
| Keyword: | Mathematics, Engineering, Applied mathematics, Industrial engineering, Approximation algorithms, Practical analysis, Scheduling |
| Texto completo: | Texto completo (Ver HTML) |
