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

• Autores: Ramón Álvarez Valdés , Antonio Parajón Guevara, José Manuel Tamarit Goerlich
• Localización: XXVI Congreso Nacional de Estadística e Investigación Operativa: Úbeda, 6-9 de noviembre de 2001, 2001, ISBN 84-8439-080-2
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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.