Un algoritmo para el Strip Packing Problem obtenido mediante la extracción de habilidades de expertos usando minería de datos

详细信息    查看全文

• 作者：Gatica Gustavo^a ; ^{ggatica@unab.cl" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Reyes Pablo^b ; ^{pabl.reyes@uandresbello.edu" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Contreras-Bolton Carlos^c ; ^{carlos.contrerasb@usach.cl" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Linfati Rodrigo^d ; ^{rlinfati@ubiobio.cl" class="auth_mail" title="E-mail the corresponding author}Author Vitae ; Escobar John Willmer^e ; ^{john.wilmer.escobar@correounivalle.edu.co" class="auth_mail" title="E-mail the corresponding author}Author Vitae
• 关键词：Strip Packing Problem ; minerí ; a de algoritmos y patrones ; habilidades de expertos
• 刊名：Ingeniería, Investigación y Tecnología
• 出版年：2016
• 出版时间：April-June 2016
• 年：2016
• 卷：17
• 期：2
• 页码：179-190
• 全文大小：730 K

文摘

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 m>Strip Packingm>, 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.