Algoritmos heurísticos eficientes para problemas de corte en dos dimensiones

Resum

El problema de corte en dos dimensiones (TDC) consiste en cortar con maximo beneficio un tablero rectangular en un conjunto finito de pequeñas piezas rectangulares, Este problema tiene un extenso campo de aplicaciones en la industria y comercio. Aparece en el corte de madera, carton, cristal, plastico, laminas metalicas, etc. El problema (TDC) se puede considerar como un subproblema o version sencilla de un problema de corte mas general en el cual se debe satisfacer toda la demanda de piezas a partir de un conjunto de tableros de distintos tamaños. En este trabajo imponemos a los patrones de corte las siguientes restricciones: Las piezas tienen orientacion fija, los cortes son de tipo gillotina y se realizan sin limite de etapas. Para resolver el problema (TDC) utilizamos los siguientes algoritmos heuristicos: constructivo, GRASP, tabu Search y Path Relinking. Estos algoritmos no han sido utilizados hasta la fecha para resolver este problema. El algoritmo Constructivo se basa en el calculo de cotas superiores sobre las piezas. El algoritmo GRASP utiliza el algoritmo Constructvo para construir una solucion y en la fase de mejora considera la fusion de rectangulos desperdicio con sus piezas adyacentes para cortarlos nuevamente con el algoritmo Constructivo posiblemente con mayor valor. Con respecto al algoritmo Tabu Search se consideran los siguientes elementos. Se realizan movimientos que mantienen la propiedad de corte guillotina. La selección del movimiento considera un rectangulo al azar y todas sus piezas adyacentes y luego selecciona como movimiento el de mejor funcion objetivo. En la lista tabu se guardan las dimensiones del rectangulo cortado, la posicion que ocupa y la pieza cortada de su esquina inferior izquierda. El algoritmo Path Relinking lo aplicamos a un conjunto de soluciones de gran calidad obtenidas con GRASP. Los resultados computacionales muestran que estos procedimientos metaheuristicos son muy eficientes y obtieen