Artículos de revistas
Un algoritmo para el Strip Packing Problem obtenido mediante la extracción de habilidades de expertos usando minería de datos
Autor
Gatica, Gustavo; Universidad Andrés Bello, Chile
Universidad de Santiago de Chile
Facultad de Ingeniería
Reyes, Pablo; Universidad Andrés Bello, Chile
Facultad de Ingeniería
Contreras-Bolton, Carlos; Universidad de Santiago de Chile
Departamento de Ingeniería Informática
Linfati, Rodrigo; Universidad del Bío-Bío, Chile
Departamento de Ingeniería Industrial, Chile
Escobar John, Willmer; Universidad del Valle, Colombia
Departamento de Contabilidad y Finanzas
Institución
Resumen
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.
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Physical Education in Chile: One Tells the History of the Discipline in the Writings of the First Official Publication of Physical Education Institute of the University of Chile (1934-1962)
Poblete Gálvez, Carolina; Moreno Doña, Alberto; Rivera García, Enrique -
Is it possible to evaluate attitudinal competences when cameras are off? Remote education experience in the Self-regulation course, Universidad de Valparaíso, Chile
Marchant-Pizarro, Carlos; Escalona-Montes de Oca, Ivy