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

Resumen

El problema de corte bidimensional consiste en satisfacer una demanda de objetos pequeños, piezas, a partir de un conjunto de objetos grandes, tableros, de forma que se maximice el beneficio o se minimice la pérdida 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 aquél en el que se dispone de un tablero del que se ha de cortar el máximo número de piezas de un solo tipo. Este problema es conocido como el Pallet Loading Problem, ya que su aplicación más habitual surge cuando un pallet rectangular se ha de llenar en la fábrica con el mayor número 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 habían sido aplicados hasta ahora a este problema. Este algoritmo ha permitido resolver óptimamente problemas de hasta 100 cajas que no habían sido resueltos en los trabajos publicados hasta la fecha. En segundo lugar, se ha desarrollado un algoritmo heurístico 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 función objetivo (maximizar el valor de las piezas cortadas o minimizar el área no utilizada del tablero) y de la existencia o no de cotas superiores en el número de piezas a cortar de cada tipo. Se han desarrollado algoritmos heurísticos que resuelven las cuatro versiones del problema. Inicialmente se han desarrollado algoritmos constructivos rápidos, que pueden servir como subrutinas de algoritmos más complejos. En una segunda fase, se ha diseñado un algoritmo metaheurístico más complejo, GRASP, para obtener soluciones, que superan en calidad y menor tiempo de computación a las de los mejores algoritmos publicados. ____________________________________________________________________________________________________