Algoritmos heurísticos y exactos para problemas de corte no guillotina en dos dimensiones

El problema de corte bidimensional consiste en satisfacer una demanda de objetos pequenos, piezas, a partir de un conjunto de objetos grandes, tableros, de forma que se maximice el beneficio o se minimice la perdida del material sobrante. En esta Tesis se han abordado dos problemas concretos de corte en dos dimensiones. En ellos suponemos que las piezas a cortar y los tableros son rectangulares y que se permiten cortes que no sean de tipo guillotina. El primer problema tratado ha sido aquel en el que se dispone de un tablero del que se ha de cortar el maximo numero de piezas de un solo tipo. Este problema es conocido como el Pallet Loading Problem, ya que su aplicacion mas habitual surge cuando un pallet rectangular se ha de llenar en la fabrica con el mayor numero posible de cajas de un solo producto.. Nuestro trabajo ha consistido, en primer lugar, en el desarrollo de un algoritmo exacto, basado en procedimientos Branch and Cut, que no habian sido aplicados hasta ahora a este problema. Este algoritmo ha permitido resolver optimamente problemas de hasta 100 cajas que no habian sido resueltos en los trabajos publicados hasta la fecha. En segundo lugar, se ha desarrollado un algoritmo heuristico basado en Tabu Search que resuelve de forma eficiente problemas de hasta 150 cajas. El segundo problema tratado es el problema en el que se dispone de un tablero, del que se ha de cortar un subconjunto de las piezas demandadas. Este problema admite, a su vez, cuatro subproblemas, dependiendo de la funcion objetivo (maximizar el valor de las piezas cortadas o minimizar el area no utilizada del tablero) y de la existencia o no de cotas superiores en el numero de piezas a cortar de cada tipo. Se han desarrollado algoritmos heuristicos que resuelven las cuatro versiones del problema. Inicialmente se han desarrollado algoritmos constructivos rapidos, que pueden servir como subrutinas de algoritmos mas complejos. En una segunda fase, se ha disenado un algoritmo metaheuristico mas complejo, GRASP, para obtener soluciones, que superan en calidad y menor tiempo de computacion a las de los mejores algoritmos publicados.