Contenido

Estas son variantes de los problemas bidimensionales de corte de material, empaquetado en contenedores") y empaquetado de rectángulos, donde los cortes están obligados a ser cortes con guillotina.[6]​.

Algoritmos de optimización

El caso especial en el que solo hay un tipo (es decir, todos los rectángulos objetivo son idénticos y están en la misma orientación) se denomina problema de "carga de palet con guillotina". Tarnowski, Terno y Scheithauer[10]​ idearon un algoritmo de tiempo polinomial para resolverlo.

Sin embargo, cuando hay dos o más tipos, todos los problemas de optimización relacionados con el corte con guillotina son NP-hard. Debido a su importancia práctica, se han ideado varios algoritmos exactos") y algoritmos de aproximación.

La separación con guillotina es un problema relacionado en el que la entrada es una colección de n formas convexas separadas por pares en el plano, y el objetivo es separarlos usando una secuencia de cortes de guillotina. Obviamente, puede que no sea posible separarlas todas. Jorge Urrutia Galicia") planteó la cuestión de si es posible separar una fracción constante de ellos,[18]​ es decir, si existe una constante c tal que, en cualquier colección de tamaño n, hay un subconjunto de tamaño cn que es separable con guillotina.

Pach y Tardos[19]​ demostraron que:.

Abed, Chalermsook, Correa, Karrenbauer, Pérez-Lantero, Soto y Wiese[20]​ demostraron que:.

Khan y Pittu[21]​ demostraron:.

Algunas variantes del problema incluyen:.

En el problema de verificación de patrones, hay un patrón de corte dado como una secuencia de puntos (x,y), para i en 1,...,m, donde (x,y) es la coordenada inferior izquierda del rectángulo i (hay un único rectángulo de cada dimensión objetivo). El objetivo es decidir si este patrón se puede implementar utilizando únicamente cortes de guillotina y, de ser así, encontrar una secuencia para dichos cortes.

Una condición necesaria obvia es que no se superpongan dos rectángulos de entrada en ambas dimensiones. Ben Messaoud, Chengbin y Espinouse[5]​ fijaron una condición más fuerte, que es a la vez necesaria y suficiente. Los rectángulos de entrada están ordenados de izquierda a derecha, de modo que x = ... = x. Existe una permutación p sobre los índices tal que, con esta permutación, los rectángulos quedarían ordenados de abajo hacia arriba, es decir, y = ... = y. Dados cuatro índices i = i y j = j, el conjunto E(i,i,j,j) contiene los índices de todos los rectángulos cuya esquina inferior izquierda está en el rectángulo [x,x] X [y,y]. Un patrón de corte es un patrón de guillotina si y solo si, para todas las cuaternas de índices i = i y j = j, al menos se cumple una de las siguientes condiciones para E(i,i,j,j):.

La condición 2 implica que los rectángulos en E(i,i,j,j) pueden separarse mediante un corte vertical (que va entre los dos intervalos horizontales). La condición 3 implica que los rectángulos en E(i,i,j,j) se pueden separar mediante un corte horizontal. Todas las condiciones juntas implican que, si cualquier conjunto de rectángulos adyacentes contiene más de un elemento, entonces pueden separarse mediante algún corte con guillotina.

Esta condición se puede verificar mediante el siguiente algoritmo:.

Encontrar un corte con guillotina para un patrón determinado se realiza de la siguiente manera:.

La ordenación de los pasos se realiza una vez y el paso de fusión se realiza m-1 veces. Por lo tanto, el tiempo de ejecución de todo el algoritmo es O(m).

Cuando el algoritmo devuelve "sí", también produce una secuencia de cortes de guillotina; cuando devuelve "no", también produce subconjuntos específicos de rectángulos que no pueden separarse mediante cortes con guillotina.

La condición necesaria y suficiente se puede utilizar para presentar el problema de corte de tiras con guillotina como programa lineal entero mixto.[5]​ Su modelo tiene 3n/4 variables binarias y 2n restricciones, y no se considera útil en la práctica.

Contenido

Estas son variantes de los problemas bidimensionales de corte de material, empaquetado en contenedores") y empaquetado de rectángulos, donde los cortes están obligados a ser cortes con guillotina.[6]​.

Algoritmos de optimización

El caso especial en el que solo hay un tipo (es decir, todos los rectángulos objetivo son idénticos y están en la misma orientación) se denomina problema de "carga de palet con guillotina". Tarnowski, Terno y Scheithauer[10]​ idearon un algoritmo de tiempo polinomial para resolverlo.

Sin embargo, cuando hay dos o más tipos, todos los problemas de optimización relacionados con el corte con guillotina son NP-hard. Debido a su importancia práctica, se han ideado varios algoritmos exactos") y algoritmos de aproximación.

La separación con guillotina es un problema relacionado en el que la entrada es una colección de n formas convexas separadas por pares en el plano, y el objetivo es separarlos usando una secuencia de cortes de guillotina. Obviamente, puede que no sea posible separarlas todas. Jorge Urrutia Galicia") planteó la cuestión de si es posible separar una fracción constante de ellos,[18]​ es decir, si existe una constante c tal que, en cualquier colección de tamaño n, hay un subconjunto de tamaño cn que es separable con guillotina.

Pach y Tardos[19]​ demostraron que:.

Abed, Chalermsook, Correa, Karrenbauer, Pérez-Lantero, Soto y Wiese[20]​ demostraron que:.

Khan y Pittu[21]​ demostraron:.

Algunas variantes del problema incluyen:.