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

Abstract

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.