| Journal: | Ingeniería. Investigación y tecnología |
| Database: | PERIÓDICA |
| System number: | 000410156 |
| ISSN: | 1405-7743 |
| Authors: | Gatica, Gustavo1 Reyes, Pablo1 Contreras Bolton, Carlos2 Linfati, Rodrigo3 Escobar, John Willmer4 |
| Institutions: | 1Universidad Andrés Bello, Facultad de Ingeniería, Santiago de Chile. Chile 2Universidad de Santiago de Chile, Departamento de Ingeniería Informática, Santiago de Chile. Chile 3Universidad del Bío-Bío, Departamento de Ingeniería Industrial, Chillán, Ñuble. Chile 4Universidad del Valle, Departamento de Contabilidad y Finanzas, Cali, Valle del Cauca. Colombia |
| Year: | 2016 |
| Season: | Abr-Jun |
| Volumen: | 17 |
| Number: | 2 |
| Pages: | 179-190 |
| Country: | México |
| Language: | Español |
| Document type: | Artículo |
| Approach: | Aplicado, descriptivo |
| Spanish abstract | La capacidad del ser humano para resolver problemas NP-Duro de forma manual no ha recibido la debida atención por la comunidad científica. Este artículo considera el problema del Strip Packing, que consiste en posicionar ortogonalmente un conjunto de piezas rectangulares dentro de un contenedor de ancho fijo y altura infinita, sin solaparlas, minimizando la altura alcanzada de las piezas dentro del contenedor. Se desarrolló un juego computacional que permite obtener soluciones manuales, propuestas por jugadores expertos, para distintas instancias del problema. La contribución del artículo consiste en presentar un algoritmo que se extrajo mediante patrones y minería de datos aplicada a soluciones encontradas por los jugadores expertos. El algoritmo generado se basa en elementos de árboles y heurísticas presentes en la literatura. Adicionalmente se presentan resultados computacionales, donde se logra encontrar la mejor solución conocida en 94.3% de un conjunto de instancias de la literatura y 79% para instancias generadas aleatoriamente |
| English abstract | The ability of the humans to manually solve NP-hard problems had not received much attention of the scientific community. This paper considers the Strip Packing Problem (SPP), in which a set of rectangular pieces has to be placed orthogonally in a container with a given width and an infinite length. The pieces are not allowed to overlap (i.e. be stacked one over the other). The aim of the SPP is to minimize the overall length of the strip. In this paper, we have developed a computational game to allow manual solutions by expert gamers for different instances of the problem. The main contribution of the paper is the presentation of an algorithm based on patterns and data mining retrieved from the results achieved by expert gamers. The proposed algorithm is based on decision-trees and heuristics proposed in literature. Finally, the proposed approach is able to find the best-known solutions for the 94.3% of a set of instances proposed in the literature, and 79% for instances generated randomly |
| Disciplines: | Ingeniería, Ciencias de la computación |
| Keyword: | Ingeniería industrial, Procesamiento de datos, Embalaje, Contenedores, Algoritmos, Minería de datos, Sistemas expertos |
| Keyword: | Engineering, Computer science, Industrial engineering, Data processing, Packing, Containers, Algorithms, Data mining, Expert systems |
| Full text: | Texto completo (Ver HTML) |
