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

详细信息    查看全文

• 作者：Joaqu&iacute ; n Pé ; rez-Ortega^a ; ^{jpo_cenidet@yahoo.com.mx" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Hilda Castillo-Zacatelco^a ; ^{hildacz@gmail.com" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Darnes Vilariñ ; o-Ayala^b ; ^{darnesv@yahoo.com" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Adriana Mexicano-Santoyo^c ; ^{mexicanoa@gmail.com" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; José ; Crisp&iacute ; n Zavala-D&iacute ; az^d ; ^{crispin_zavala@uaem.mx" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Alicia Mart&iacute ; nez-Rebollar^a ; ^{dcc@cenidet.edu.mx" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Hugo Estrada-Esquivel^e ; ^{hestrada@dsic.upv.es" class="auth_mail" title="E-mail the corresponding author}Author Vitae
• 关键词：heur&iacute ; stica ; Bin Packing ; arcos de flujo ; modelo exacto para BPP ; l&iacute ; mite inferior ; instancias del ; BPP
• 刊名：Ingeniería, Investigación y Tecnología
• 出版年：2016
• 出版时间：April-June 2016
• 年：2016
• 卷：17
• 期：2
• 页码：155-168
• 全文大小：579 K

文摘

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.