Saved in:
| Main Author: | |
|---|---|
| Format: | Artículo científico |
| Language: | es |
| Published: |
Universidad Nacional Autónoma de México
2016
|
| Subjects: | |
| Online Access: | https://www.redalyc.org/articulo.oa?id=40445803001 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Una nueva estrategia heurística para el problema de Bin Packing Joaquín Pérez-Ortega Hilda Castillo-Zacatelco Darnes Vilariño-Ayala Adriana Mexicano-Santoyo José Crispín Zavala-Díaz Alicia Martínez-Rebollar Hugo Estrada-Esquivel Ingeniería BPP Heurística Bin Packing arcos de flujo modelo exacto para BPP 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. 2016 artículo científico 1405-7743 https://www.redalyc.org/articulo.oa?id=40445803001 es http://www.redalyc.org/revista.oa?id=404 Ingeniería. Investigación y Tecnología application/pdf Universidad Nacional Autónoma de México Ingeniería. Investigación y Tecnología (México) Num.2 Vol.VXII