Una nueva estrategia heurística para el problema de Bin Packing

• Published in: Ingeniería, investigación y tecnología investigación y tecnología, 2016-04, Vol.17 (2), p.155-168
• Main Authors: Pérez-Ortega, Joaquín, Castillo-Zacatelco, Hilda, Vilariño-Ayala, Darnes, Mexicano-Santoyo, Adriana, Zavala-Díaz, José Crispín, Martínez-Rebollar, Alicia, Estrada-Esquivel, Hugo
• Format: Article
• Language: por ; spa
• Subjects: arcos de flujo; Bin Packing; BPP; Engineering, Multidisciplinary; exact model for BPP; flow arcs; heuristic; heurística; instances of the BPP; instancias del; lower bound; límite inferior; modelo exacto para BPP
• ISSN: 1405-7743
• DOI: 10.1016/j.riit.2016.06.001

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 estrategia 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 variables 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 conjuntos 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. The Bin Packing problem (BPP) is NP-hard, the use of exact methods for solving BPP instances require a high number of variables and therefore a high computational cost. In this paper a new heuristic strategy for solving the BPP instances, which guarantees obtain optimal solutions, is proposed. The proposed strategy includes the use of a new model based on flow arcs. In the proposed model, the number of variables was reduced by previous allocation of objects in bins. Additionally, our approach includes a heuristic that allows reducing the instance size and thereby the solution algorithm search space. To validate the proposed approach, experiments were performed using the test sets hard28, 53nirup, bin1data and falkenauer, all of them well known in the state of the art. The results show that it using our approach is possible to find the optimal solution for all test set. Also, the execution time was reduced in regard the reported time obtained by using the flow arc model. Time reductions were up to 19.7 and 43% for 53nirup and hard28 test set, respectively.