Una nueva estrategia heurística para el problema de Bin Packing
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Nacional Autónoma de México
Abstract
Description
El problema de Bin Packing (BPP) es NP-duro, por lo que un método exacto para resolver instancias del BPP requiere un gran número de variables y demasiado tiempo de ejecución. En este trabajo se propone una nueva estra- tegia heurística para resolver instancias del BPP en donde se garantiza la solución óptima. La estrategia propuesta incluye el uso de un nuevo modelo exacto basado en arcos de flujo. En el modelo propuesto, el número de varia - bles se redujo asignando objetos en contenedores. Adicionalmente se incluye una heurística que mediante el preprocesado de la instancia permite reducir su tamaño y con ello el espacio de búsqueda del algoritmo de solución. Para validar el enfoque propuesto, se realizaron experimentos usando los conjun- tos de prueba hard28, 53nirup, bin1data, uniform, triplets y subconjuntos de otras instancias, todos ellos conocidos en el estado del arte. Los resultados muestran que empleando nuestro enfoque es posible encontrar la solución óptima de todas las instancias de prueba. Además, el tiempo de ejecución se redujo en relación con lo reportado por el modelo basado en arcos de flujo. Las reducciones de tiempo fueron de 19.7 y 43% para los conjuntos 53nirup y hard28, respectivamente.
Keywords
Ingeniería, Heurística, Bin Packing, arcos de flujo, modelo exacto para BPP, Instancias dellímite inferior, BPP