Resumen de Un estudio computacional de algorítmos heurísticos basados en programación lineal para problemas de corte en dos dimensiones

Ramón Álvarez Valdés , Antonio Parajón Guevara, José Manuel Tamarit Goerlich

• En este trabajo desarrollamos y comparamos diferentes métodos heurísticos para resolver el problema general de corte en dos dimensiones. Seguimos el esquema de generación de columnas de Gilmore y Gomory, obteniendo en cada iteración un nuevo patrón de corte al resolver un subproblema sobre un tablero. Para resolver este subproblema hemos desarrollado tres procedimientos heurísticos basados en técnicas GRASP y tabu search. Obtenemos soluciones enteras a partir de las soluciones fraccionarias del algoritmo de Gilmore y Gomory, comparando tres procedimientos de redondeo: redondeo superior, ramificación y acotación truncada y un problema residual. Los resultados computacionales muestran la eficiencia de los algoritmos.