"Algoritmos en paralelo para una variante del problema bin packing"

Figueroa-Mata, Geovanni
Carrera-Retana, Ernesto

2011

Descargar documento

Código del Proyecto: VIE-5402-1440-2601

En este informe se resumen los resultados obtenidos en la investigación realizada sobre una variante del problema bin packing. El objetivo fue dise˜nar e implementar algoritmos determin´ısticos y heur´ısticos en paralelo para resolver y aproximar la soluci´on a dicho problema. Se presenta el problema; se hace un análisis de la complejidad del mismo; se mencionan algunos de los modelos existentes para la programación en paralelo así como algunas bibliotecas que permiten el desarrollo de algoritmos con estos modelos; se introducen las m´etricas usuales que permiten medir el desempeño de un algoritmo en paralelo; y se resumen los experimentos realizados. En los diseños de los algoritmos se utilizó el modelo exploratorio, y su implementación se realizó utilizando la biblioteca OpenMP en C. Los resultados obtenidos en instancias de prueba mostraron mejoras en el tiempo de ejecución de hasta 10x con respecto a las implementaciones secuenciales de los algoritmos respectivos. Estos resultados permiten concluir que el diseño propuesto y la implementaci´on respectiva, resuelven de manera satisfactoria el problema planteado.

Instituto Tecnológico de Costa Rica. Vicerrectoría de Investigación y Extensión Dirección de Proyectos

Optimización combinatoria; Complejidad; Diseño; Sincronización; Escalabilidad;