Una nueva estrategia heurística para el problema de Bin Packing
| dc.creator | Joaquín Pérez-Ortega | |
| dc.creator | Hilda Castillo-Zacatelco | |
| dc.creator | Darnes Vilariño-Ayala | |
| dc.creator | Adriana Mexicano-Santoyo | |
| dc.creator | José Crispín Zavala-Díaz | |
| dc.creator | Alicia Martínez-Rebollar | |
| dc.creator | Hugo Estrada-Esquivel | |
| dc.date | 2016 | |
| dc.date.accessioned | 2021-04-11T23:57:27Z | |
| dc.date.available | 2021-04-11T23:57:27Z | |
| dc.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. | |
| dc.format | application/pdf | |
| dc.identifier | http://www.redalyc.org/articulo.oa?id=40445803001 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12371/12329 | |
| dc.language | es | |
| dc.publisher | Universidad Nacional Autónoma de México | |
| dc.relation | http://www.redalyc.org/revista.oa?id=404 | |
| dc.rights | Ingeniería. Investigación y Tecnología | |
| dc.source | Ingeniería. Investigación y Tecnología (México) Num.2 Vol.VXII | |
| dc.subject | Ingeniería | |
| dc.subject | Heurística | |
| dc.subject | Bin Packing | |
| dc.subject | arcos de flujo | |
| dc.subject | modelo exacto para BPP | |
| dc.subject | Instancias dellímite inferior | |
| dc.subject | BPP | |
| dc.title | Una nueva estrategia heurística para el problema de Bin Packing | |
| dc.type | Artículo científico |