| Revista: | Ingeniería. Investigación y tecnología |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000410153 |
| ISSN: | 1405-7743 |
| Autors: | Pérez Ortega, Joaquín1 Castillo Zacatelco, Hilda1 Vilariño Ayala, Darnes2 Mexicano Santoyo, Adriana3 Zavala Díaz, José Crispín4 Martínez Rebollar, Alicia1 Estrada Esquivel, Hugo5 |
| Institucions: | 1Centro Nacional de Investigación y Desarrollo Tecnológico, Departamento de Ciencias Computacionales, Cuernavaca, Morelos. México 2Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación, Puebla. México 3Instituto Tecnológico de Ciudad Victoria, Ciudad Victoria, Tamaulipas. México 4Universidad Autónoma del Estado de Morelos, Facultad de Contaduría, Administración e Informática, Cuernavaca, Morelos. México 5Fondo de Información y Documentación para la Industria, Ciudad de México. México |
| Any: | 2016 |
| Període: | Abr-Jun |
| Volum: | 17 |
| Número: | 2 |
| Paginació: | 155-168 |
| País: | México |
| Idioma: | Español |
| Tipo de documento: | Artículo |
| Enfoque: | Aplicado, descriptivo |
| Resumen en español | 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 |
| Resumen en inglés | 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 |
| Disciplines | Ingeniería, Matemáticas |
| Paraules clau: | Ingeniería industrial, Matemáticas aplicadas, Contenedores, Embalaje, Heurística, Arcos de flujo |
| Keyword: | Engineering, Mathematics, Industrial engineering, Applied mathematics, Containers, Packing, Heuristics, Flow arcs |
| Text complet: | Texto completo (Ver HTML) |
