Problema de la mochila irrestricta bidimensional guillotinada

Unconstrained Two-Dimensional Knapsack Problem

​Los problemas de empaquetamiento y corte óptimo son considerados clásicos dentro de la investigación de operaciones, debido a su gran espectro de aplicación en la industria y su alta complejidad tanto matemática como computacional. En este trabajo se presenta el problema de empaquetamiento óptimo bidimensional irrestricto de piezas rectangulares en una sola placa, con pesos asociados a las piezas y sin estos, al tiempo que se considera la posibilidad de rotar 90° las piezas y con restricciones de corte tipo guillotina (problema de la mochila bidimensional irrestricta guillotinada). Se describe el modelo matemático aplicado por diferentes grupos de investigación que estudian esta temática. Se propone, además, un tipo de codificación para aplicarla en este problema y se resuelve mediante un algoritmo de optimización que combina las principales características de cúmulo de partículas, recocido simulado y algoritmos genéticos. Para comprobar la eficiencia de la metodología presentada se tomaron casos de prueba de la literatura especializada, se analizan y comparan los métodos de solución presentados con los últimos avances del problema y se obtienen resultados de excelente calidad y nunca antes reportados en la literatura especializada.

INTRODUCCIÓN

El problema de la mochila irrestricta bidimensional guillotinada se usa para resolver problemas de corte que se presentan cuando el material es una pieza rectangular donde se deben ubicar piezas rectangulares más pequeñas de las que se conoce el tamaño y un costo asociado. El objetivo es maximizar el valor de las piezas cortadas. Las características de este problema son las siguientes:

• El costo asociado puede o no estar relacionado con el área de la pieza que se va a ubicar. Si el costo es igual al área de la pieza, se está resolviendo el problema sin pesos (unweighted version), y si el costo es diferente del área del ítem, el problema que se va a resolver es el problema con pesos (weighted version).
• La orientación de las piezas, es decir, una pieza de alto h y ancho w es diferente de una pieza de longitud w y alto h (without rotation). Si se considera que las dimensiones (h, w) y (w, h) representan las dimensiones de la misma pieza, se está abordando un problema con rotación (with rotation).
• Los patrones de corte son del tipo guillotina. Cada corte produce dos subrectángulos. Los cortes van de un extremo al otro del rectángulo original.
• No existe un límite máximo del número de piezas que se vayan a cortar de cada tipo (unconstrained version).

Gilmore y Gomory (1965 y 1966) proponen un algoritmo recursivo exacto sobre la base de la programación dinámica para resolver el problema.