Problema de empaquetamiento de tiras

El problema de empaquetamiento de franjas es un problema de minimización geométrica bidimensional. Dado un conjunto de rectángulos alineados con el eje y una franja de ancho limitado y altura infinita, determine un empaquetamiento sin superposición de los rectángulos en la franja, minimizando su altura. Este problema es un problema de corte y empaquetamiento y se clasifica como un problema de dimensión abierta según Wäscher et al. ^[1]

Este problema surge en el área de programación, donde se modelan trabajos que requieren una porción contigua de la memoria durante un período de tiempo determinado. Otro ejemplo es el área de fabricación industrial, donde se deben cortar piezas rectangulares de una hoja de material (por ejemplo, tela o papel) que tiene un ancho fijo pero una longitud infinita, y se desea minimizar el material desperdiciado.

Este problema se estudió por primera vez en 1980. ^[2] Es fuertemente NP difícil y no existe ningún algoritmo de aproximación en tiempo polinomial con una razón menor que a menos que . Sin embargo, la mejor razón de aproximación lograda hasta ahora (por un algoritmo de tiempo polinomial de Harren et al. ^[3] ) es , lo que plantea la pregunta abierta de si existe un algoritmo con razón de aproximación . ${\displaystyle 3/2}$ ${\displaystyle P=NP}$ ${\displaystyle (5/3+\varepsilon )}$ ${\displaystyle 3/2}$

Definición

Una instancia del problema de empaquetamiento de tiras consiste en una tira con ancho y altura infinitos, así como un conjunto de elementos rectangulares. Cada elemento tiene un ancho y una altura . Un empaquetamiento de los elementos es una asignación que asigna cada esquina inferior izquierda de un elemento a una posición dentro de la tira. Un punto interno de un elemento colocado es un punto del conjunto . Dos elementos (colocados) se superponen si comparten un punto interno. La altura del empaquetamiento se define como . El objetivo es encontrar un empaquetamiento sin superposición de los elementos dentro de la tira mientras se minimiza la altura del empaquetamiento. ${\displaystyle I=({\mathcal {I}},W)}$ ${\displaystyle W=1}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle w_{i}\in (0,1]\cap \mathbb {Q} }$ ${\displaystyle h_{i}\in (0,1]\cap \mathbb {Q} }$ ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle (x_{i},y_{i})\in ([0,1-w_{i}]\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}}$ ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle \mathrm {inn} (i)=\{(x,y)\in \mathbb {Q} \times \mathbb {Q} |x_{i}<x<x_{i}+w_{i},y_{i}<y<y_{i}+h_{i}\}}$ ${\displaystyle \max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}}$

Esta definición se utiliza para todos los algoritmos de tiempo polinómico. Para los algoritmos de tiempo pseudopolinómico y FPT , la definición se modifica ligeramente para simplificar la notación. En este caso, todos los tamaños que aparecen son enteros. En particular, el ancho de la franja se da mediante un número entero arbitrario mayor que 1. Nótese que estas dos definiciones son equivalentes.

Variantes

Se han estudiado varias variantes del problema del empaquetamiento en tiras. Estas variantes se refieren a la geometría de los objetos, la dimensión del problema, la capacidad de rotación de los elementos y la estructura del empaquetamiento. ^[4]

Geometría: En la variante estándar de este problema, el conjunto de elementos dados consta de rectángulos. En un subcaso que se considera a menudo, todos los elementos deben ser cuadrados. Esta variante ya se consideró en el primer artículo sobre empaquetamiento en tiras. ^[2] Además, se han estudiado variantes en las que las formas son circulares o incluso irregulares. En este último caso, se denomina empaquetamiento en tiras irregulares .

Dimensión: Si bien no se menciona de otra manera, el problema del empaquetamiento de tiras es un problema bidimensional. Sin embargo, también se ha estudiado en tres o más dimensiones. En este caso, los objetos son hiperrectángulos y la tira está abierta en una dimensión y limitada en las dimensiones residuales.

Rotación: En el problema clásico de empaquetado en tiras, no se permite rotar los elementos. Sin embargo, se han estudiado variantes en las que se permite rotarlos 90 grados o incluso en un ángulo arbitrario.

Estructura: En el problema general del embalaje en tiras, la estructura del embalaje es irrelevante. Sin embargo, existen aplicaciones que tienen requisitos explícitos sobre la estructura del embalaje. Uno de estos requisitos es poder cortar los artículos de la tira mediante cortes horizontales o verticales de borde a borde. Los embalajes que permiten este tipo de corte se denominan embalajes de guillotina .

Dureza

El problema de empaquetamiento en tiras contiene el problema de empaquetamiento en contenedores como un caso especial cuando todos los elementos tienen la misma altura 1. Por esta razón, es fuertemente NP-duro, y no puede haber un algoritmo de aproximación de tiempo polinomial que tenga una relación de aproximación menor que a menos que . Además, a menos que , no puede haber un algoritmo de tiempo pseudo-polinomial que tenga una relación de aproximación menor que , ^[5] lo que se puede demostrar mediante una reducción del problema de 3 particiones fuertemente NP-completo . Nótese que ambos límites inferiores y también se cumplen para el caso en que se permite una rotación de los elementos de 90 grados. Además, Ashok et al. ^[6] demostraron que el empaquetamiento en tiras es W[1]-duro cuando se parametriza por la altura del empaquetamiento óptimo. ${\displaystyle 3/2}$ ${\displaystyle P=NP}$ ${\displaystyle P=NP}$ ${\displaystyle 5/4}$ ${\displaystyle 3/2}$ ${\displaystyle 5/4}$

Propiedades de las soluciones óptimas

Existen dos límites inferiores triviales para las soluciones óptimas. El primero es la altura del elemento más grande. Defina . Entonces se cumple que ${\displaystyle h_{\max }(I):=\max\{h(i)|i\in {\mathcal {I}}\}}$

${\displaystyle OPT(I)\geq h_{\max }(I)}$.

Otro límite inferior viene dado por el área total de los elementos. Definamos entonces que se cumple que ${\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)}$

${\displaystyle OPT(I)\geq \mathrm {AREA} ({\mathcal {I}})/W}$.

Los dos límites inferiores siguientes tienen en cuenta el hecho de que ciertos elementos no se pueden colocar uno al lado del otro en la tira, y se pueden calcular en . ^[7] Para el primer límite inferior suponga que los elementos están ordenados por altura no creciente. Defina . Para cada defina el primer índice tal que . Entonces se cumple que ${\displaystyle {\mathcal {O}}(n\log(n))}$ ${\displaystyle k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}}$ ${\displaystyle l>k}$ ${\displaystyle i(l)\leq k}$ ${\displaystyle w(l)+\sum _{j=1}^{i(l)}w(j)>W}$

${\displaystyle OPT(I)\geq \max\{h(l)+h(i(l))|l>k\wedge w(l)+\sum _{j=1}^{i(l)}w(j)>W\}}$. ^[7]

Para el segundo límite inferior, divida el conjunto de elementos en tres conjuntos. Sea y defina , , y . Entonces se cumple que ${\displaystyle \alpha \in [1,W/2]\cap \mathbb {N} }$ ${\displaystyle {\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}}$ ${\displaystyle {\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}}$ ${\displaystyle {\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}}$

${\displaystyle OPT(I)\geq \max _{\alpha \in [1,W/2]\cap \mathbb {N} }{\Bigg \{}\sum _{i\in {\mathcal {I}}_{1}(\alpha )\cup {\mathcal {I}}_{2}(\alpha )}h(i)+\left({\frac {\sum _{i\in {\mathcal {I}}_{3}(\alpha )h(i)w(i)-\sum _{i\in {\mathcal {I}}_{2}(\alpha )}(W-w(i))h(i)}}{W}}\right)_{+}{\Bigg \}}}$, ^[7] donde para cada . ${\displaystyle (x)_{+}:=\max\{x,0\}}$ ${\displaystyle x\in \mathbb {R} }$

Por otra parte, Steinberg ^[8] ha demostrado que la altura de una solución óptima puede estar acotada superiormente por

${\displaystyle OPT(I)\leq 2\max\{h_{\max }(I),\mathrm {AREA} ({\mathcal {I}})/W\}.}$

Más precisamente, demostró que dados a y a entonces los elementos pueden colocarse dentro de una caja con ancho y alto si ${\displaystyle W\geq w_{\max }({\mathcal {I}})}$ ${\displaystyle H\geq h_{\max }(I)}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle W}$ ${\displaystyle H}$

${\displaystyle WH\geq 2\mathrm {AREA} ({\mathcal {I}})+(2w_{\max }({\mathcal {I}})-W)_{+}(2h_{\max }(I)-H)_{+}}$, dónde . ${\displaystyle (x)_{+}:=\max\{x,0\}}$

Algoritmos de aproximación de tiempo polinomial

Dado que este problema es NP-hard, se han estudiado algoritmos de aproximación para este problema. La mayoría de los enfoques heurísticos tienen una razón de aproximación entre y . Encontrar un algoritmo con una razón inferior parece complicado, y la complejidad de los algoritmos correspondientes aumenta en relación con su tiempo de ejecución y sus descripciones. La razón de aproximación más pequeña lograda hasta ahora es . ${\displaystyle 3}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle (5/3+\varepsilon )}$

De abajo hacia arriba y justificado a la izquierda (BL)

Un ejemplo de soluciones generadas por el algoritmo Bottom-Up Left-Justified.

Este algoritmo fue descrito por primera vez por Baker et al. ^[2] y funciona de la siguiente manera:

Sea una secuencia de elementos rectangulares. El algoritmo itera la secuencia en el orden dado. Para cada elemento considerado , busca la posición más baja para colocarlo y luego lo desplaza lo más a la izquierda posible. Por lo tanto, lo coloca en la coordenada más a la izquierda posible en la franja. ${\displaystyle L}$ ${\displaystyle r\in L}$ ${\displaystyle r}$ ${\displaystyle (x,y)}$

Este algoritmo tiene las siguientes propiedades:

• La razón de aproximación de este algoritmo no puede limitarse mediante una constante. Más precisamente, demostraron que para cada existe una lista de elementos rectangulares ordenados por ancho creciente de manera que , donde es la altura del empaquetamiento creado por el algoritmo BL y es la altura de la solución óptima para . ^[2] ${\displaystyle M>0}$ ${\displaystyle L}$ ${\displaystyle BL(L)/OPT(L)>M}$ ${\displaystyle BL(L)}$ ${\displaystyle OPT(L)}$ ${\displaystyle L}$
• Si los artículos se ordenan por ancho decreciente, entonces . ^[2] ${\displaystyle BL(L)/OPT(L)\leq 3}$
• Si los elementos son todos cuadrados y están ordenados por ancho decreciente, entonces . ^[2] ${\displaystyle BL(L)/OPT(L)\leq 2}$
• Para cualquier , existe una lista de rectángulos ordenados por anchos decrecientes tales que . ^[2] ${\displaystyle \delta >0}$ ${\displaystyle L}$ ${\displaystyle BL(L)/OPT(L)>3-\delta }$
• Para cualquier , existe una lista de cuadrados ordenados por anchos decrecientes tales que . ^[2] ${\displaystyle \delta >0}$ ${\displaystyle L}$ ${\displaystyle BL(L)/OPT(L)>2-\delta }$
• Para cada , existe una instancia que contiene solo cuadrados donde cada orden de los cuadrados tiene una relación de , es decir, existen instancias donde BL no encuentra el óptimo incluso cuando itera todos los órdenes posibles de los elementos. ^[2] En 2024, Hougardy y Zondervan mejoraron este límite inferior a . ^[19] ${\displaystyle \varepsilon \in (0,1]}$ ${\displaystyle L}$ ${\displaystyle BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}}$ ${\displaystyle BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}}$

Ajuste siguiente de altura decreciente (NFDH)

Un ejemplo de NFDH y FFDH aplicados a la misma instancia

Este algoritmo fue descrito por primera vez por Coffman et al. ^[9] en 1980 y funciona de la siguiente manera:

Sea el conjunto dado de elementos rectangulares. Primero, el algoritmo ordena los elementos por orden de altura no creciente. Luego, comenzando en la posición , el algoritmo coloca los elementos uno al lado del otro en la franja hasta que el siguiente elemento se superponga al borde derecho de la franja. En este punto, el algoritmo define un nuevo nivel en la parte superior del elemento más alto en el nivel actual y coloca los elementos uno al lado del otro en este nuevo nivel. ${\displaystyle {\mathcal {I}}}$ ${\displaystyle (0,0)}$

Este algoritmo tiene las siguientes propiedades:

• El tiempo de ejecución puede limitarse mediante y si los elementos ya están ordenados incluso por . ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}$ ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}$
• Para cada conjunto de elementos , produce un empaquetamiento de altura , donde es la altura más grande de un elemento en . ^[9] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}$ ${\displaystyle h_{\max }}$ ${\displaystyle {\mathcal {I}}}$
• Para cada existe un conjunto de rectángulos tales que ^[9] ${\displaystyle \varepsilon >0}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).}$
• El embalaje que se genera es un embalaje de guillotina, es decir, los artículos se pueden obtener mediante una secuencia de cortes horizontales o verticales de borde a borde.

Primer ajuste de altura decreciente (FFDH)

Este algoritmo, descrito por primera vez por Coffman et al. ^[9] en 1980, funciona de manera similar al algoritmo NFDH. Sin embargo, al colocar el siguiente elemento, el algoritmo escanea los niveles de abajo a arriba y coloca el elemento en el primer nivel en el que encaja. Solo se abre un nuevo nivel si el elemento no encaja en ninguno de los anteriores.

Este algoritmo tiene las siguientes propiedades:

• El tiempo de ejecución puede limitarse mediante , ya que hay como máximo niveles. ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$ ${\displaystyle |{\mathcal {I}}|}$
• Para cada conjunto de elementos produce un empaquetamiento de altura , donde es la altura más grande de un elemento en . ^[9] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})}$ ${\displaystyle h_{\max }}$ ${\displaystyle {\mathcal {I}}}$
• Sea . Para cualquier conjunto de elementos y tira con ancho tal que para cada , se cumple que . Además, para cada , existe un conjunto de elementos con . ^[9] ${\displaystyle m\geq 2}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle W}$ ${\displaystyle w(i)\leq W/m}$ ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})}$
• Si todos los elementos de son cuadrados, se cumple que . Además, para cada , existe un conjunto de cuadrados tales que . ^[9] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})}$
• El embalaje que se genera es un embalaje de guillotina, es decir, los artículos se pueden obtener mediante una secuencia de cortes horizontales o verticales de borde a borde.

El algoritmo de ajuste dividido (SF)

Este algoritmo fue descrito por primera vez por Coffman et al. ^[9] Para un conjunto dado de elementos y una tira con ancho , funciona de la siguiente manera: ${\displaystyle {\mathcal {I}}}$ ${\displaystyle W}$

1. Determinar , el entero más grande tal que los rectángulos dados tengan ancho o menos. ${\displaystyle m\in \mathbb {N} }$ ${\displaystyle W/m}$
2. Dividir en dos conjuntos y , de modo que contenga todos los elementos con un ancho mientras que contenga todos los elementos con . ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}_{wide}}$ ${\displaystyle {\mathcal {I}}_{narrow}}$ ${\displaystyle {\mathcal {I}}_{wide}}$ ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle w(i)>W/(m+1)}$ ${\displaystyle {\mathcal {I}}_{narrow}}$ ${\displaystyle w(i)\leq W/(m+1)}$
3. Orden y por altura no creciente. ${\displaystyle {\mathcal {I}}_{wide}}$ ${\displaystyle {\mathcal {I}}_{narrow}}$
4. Empaquete los artículos con el algoritmo FFDH. ${\displaystyle {\mathcal {I}}_{wide}}$
5. Reordenar los niveles/estantes construidos por FFDH de tal manera que todos los estantes con un ancho total mayor que estén debajo de los más estrechos. ${\displaystyle W(m+1)/(m+2)}$
6. Esto deja un área rectangular de , junto a niveles/estantes más estrechos, que no contiene ningún artículo. ${\displaystyle R}$ ${\displaystyle W/(m+2)}$
7. Utilice el algoritmo FFDH para empaquetar los elementos utilizando el área también. ${\displaystyle {\mathcal {I}}_{narrow}}$ ${\displaystyle R}$

Este algoritmo tiene las siguientes propiedades:

• Para cada conjunto de elementos y el correspondiente , se cumple que . ^[9] Nótese que para , se cumple que ${\displaystyle {\mathcal {I}}}$ ${\displaystyle m}$ ${\displaystyle SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }}$ ${\displaystyle m=1}$ ${\displaystyle SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }}$
• Para cada , existe un conjunto de elementos tales que . ^[9] ${\displaystyle \varepsilon >0}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})}$

Algoritmo de Sleator

Para un conjunto dado de elementos y una tira con ancho , funciona de la siguiente manera: ${\displaystyle {\mathcal {I}}}$ ${\displaystyle W}$

1. Encuentra todos los elementos con un ancho mayor que y apílalos en la parte inferior de la tira (en orden aleatorio). Llama a la altura total de estos elementos . Todos los demás elementos se colocarán encima de . ${\displaystyle W/2}$ ${\displaystyle h_{0}}$ ${\displaystyle h_{0}}$
2. Ordena todos los elementos restantes en orden no creciente de altura. Los elementos se colocarán en este orden.
3. Considere la línea horizontal como un estante. El algoritmo coloca los elementos en este estante en orden no creciente de altura hasta que no quede ningún elemento o el siguiente no quepa. ${\displaystyle h_{0}}$
4. Dibuje una línea vertical en , que corte la tira en dos mitades iguales. ${\displaystyle W/2}$
5. Sea el punto más alto cubierto por cualquier elemento en la mitad izquierda y el punto correspondiente en la mitad derecha. Dibuje dos segmentos de línea horizontales de longitud en y a través de la mitad izquierda y derecha de la tira. Estas dos líneas construyen nuevos estantes en los que el algoritmo colocará los elementos, como en el paso 3. Elija la mitad que tiene el estante inferior y coloque los elementos en este estante hasta que no quepa ningún otro elemento. Repita este paso hasta que no quede ningún elemento. ${\displaystyle h_{l}}$ ${\displaystyle h_{r}}$ ${\displaystyle W/2}$ ${\displaystyle h_{l}}$ ${\displaystyle h_{r}}$

Este algoritmo tiene las siguientes propiedades:

• El tiempo de ejecución puede limitarse mediante y si los elementos ya están ordenados incluso por . ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}$ ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}$
• Para cada conjunto de elementos produce un empaquetamiento de altura , donde es la altura más grande de un elemento en . ^[10] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})}$ ${\displaystyle h_{\max }}$ ${\displaystyle {\mathcal {I}}}$

El algoritmo de división (SP)

Este algoritmo es una extensión del enfoque de Sleator y fue descrito por primera vez por Golan. ^[11] Coloca los elementos en orden no creciente de ancho. La idea intuitiva es dividir la tira en subtiras mientras se colocan algunos elementos. Siempre que sea posible, el algoritmo coloca el elemento actual lado a lado de un elemento ya colocado . En este caso, divide la subtira correspondiente en dos partes: una que contiene el primer elemento y la otra que contiene el elemento actual . Si esto no es posible, coloca encima de un elemento ya colocado y no divide la subtira. ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i}$

Este algoritmo crea un conjuntoSde sub-franjas. Para cada sub-franjas ∈ SConocemos su esquina inferior izquierda.s.xposiciónys.yposición, su anchos.ancho, las líneas horizontales paralelas al borde superior e inferior del elemento colocado en último lugar dentro de esta subfranjacenayMás lento, así como el ancho de la mismas.Ancho del elemento.

La función Algoritmo de división (SP) se  ingresa:  elementos I, ancho de la tiraYo Salida:  Un embalaje de los artículos. Orden I en orden no creciente de ancho; Definir lista vacía S de sub-tiras; Defina una nueva subfranja s con s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W; Añadir s a S; mientras no esté vacío hago i := I.pop(); Elimina el elemento más ancho de I Define una nueva lista S_2 que contiene todas las subfranjas con s.width - s.itemWidth ≥ i.width; S_2 contiene todas las subtiras donde i encaja junto al elemento ya colocado.  Si S_2 está vacío, entonces,  en este caso, coloque el elemento encima de otro. Encuentre la subtira s en S con el s.upper más pequeño; es decir, la subtira menos llena. Coloque i en la posición (posición_s.x, posición_superior); Actualizar s: s.lower := s.upper; s.upper := s.upper+i.height; s.itemWidth := i.width; De lo contrario  , en este caso, coloque el elemento junto a otro en el mismo nivel y divida la subtira correspondiente en esta posición. Encuentra s ∈ S_2 con el s.lower más pequeño; Coloque i en la posición (s.xposition + s.itemWidth, s.lower); Quitar s de S; Definir dos nuevas subfranjas s1 y s2 con s1.xposition = s.xposition, s1.yposition = s.superior, s1.width = s.itemWidth, s1.inferior = s.superior, s1.superior = s.superior, s1.itemWidth = s.itemWidth; s2.xposition = s.xposition+s.itemWidth, s2.yposition = s.lower, s2.width = s.width - s.itemWidth, s2.lower = s.lower, s2.upper = s.lower + i.height, s2.itemWidth = i.width; S.add(s1,s2);  función de retorno final

Este algoritmo tiene las siguientes propiedades:

• El tiempo de ejecución se puede limitar por ya que el número de subbandas está limitado por . ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$ ${\displaystyle |{\mathcal {I}}|}$
• Para cualquier conjunto de elementos se cumple que . ^[11] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}$
• Para cualquier , existe un conjunto de elementos tales que . ^[11] ${\displaystyle \varepsilon >0}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})}$
• Para cualquier y , existe un conjunto de elementos tales que . ^[11] ${\displaystyle \varepsilon >0}$ ${\displaystyle C>0}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C}$

Ajuste inverso (RF)

Este algoritmo fue descrito por primera vez por Schiermeyer. ^[13] La descripción de este algoritmo necesita alguna notación adicional. Para un elemento colocado , su esquina inferior izquierda se denota por y su esquina superior derecha por . ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle (a_{i},c_{i})}$ ${\displaystyle (b_{i},d_{i})}$

Dado un conjunto de elementos y una franja de ancho , funciona de la siguiente manera: ${\displaystyle {\mathcal {I}}}$ ${\displaystyle W}$

1. Apila todos los rectángulos de ancho mayor que uno encima del otro (en orden aleatorio) en la parte inferior de la tira. Indica la altura de esta pila. Todos los demás elementos se empacarán arriba . ${\displaystyle W/2}$ ${\displaystyle H_{0}}$ ${\displaystyle H_{0}}$
2. Ordene los elementos restantes en orden de altura no creciente y considere los elementos en este orden en los siguientes pasos. Sea la altura del elemento más alto de estos elementos restantes. ${\displaystyle h_{\max }}$
3. Coloque los elementos uno por uno alineados a la izquierda en un estante definido por hasta que no quepa ningún otro elemento en este estante o no quede ningún elemento. Llame a este estante el primer nivel . ${\displaystyle H_{0}}$
4. Sea la altura del artículo desempaquetado más alto. Defina un nuevo estante en . El algoritmo llenará este estante de derecha a izquierda, alineando los artículos a la derecha, de modo que los artículos toquen este estante con su parte superior. Llame a este estante el segundo nivel inverso . ${\displaystyle h_{1}}$ ${\displaystyle H_{0}+h_{\max }+h_{1}}$
5. Colocar los artículos en los dos estantes siguiendo el método First-Fit, es decir, colocar los artículos en el primer nivel donde quepan y en el segundo en caso contrario. Continuar hasta que no queden artículos o el ancho total de los artículos en el segundo estante sea al menos . ${\displaystyle W/2}$
6. Desplazar el segundo nivel inverso hacia abajo hasta que un elemento de este toca un elemento del primer nivel. Definir como la nueva posición vertical del estante desplazado. Sea y el par de elementos que se tocan más a la derecha con colocados en el primer nivel y en el segundo nivel inverso. Definir . ${\displaystyle H_{1}}$ ${\displaystyle f}$ ${\displaystyle s}$ ${\displaystyle f}$ ${\displaystyle s}$ ${\displaystyle x_{r}:=\max(b_{f},b_{s})}$
7. Si entonces es el último rectángulo colocado en el segundo nivel inverso. Mueva todos los demás elementos de este nivel hacia abajo (todos en la misma cantidad) hasta que el primero toque un elemento del primer nivel. Nuevamente, el algoritmo determina el par de elementos que se tocan más a la derecha y . Defina como la cantidad en la que se desplazó el estante hacia abajo. ${\displaystyle x_{r}<W/2}$ ${\displaystyle s}$ ${\displaystyle f'}$ ${\displaystyle s'}$ ${\displaystyle h_{2}}$
   1. Si se desplaza hacia la izquierda hasta tocar otro elemento o el borde de la tira, defina el tercer nivel en la parte superior de . ${\displaystyle h_{2}\leq h(s)}$ ${\displaystyle s}$ ${\displaystyle s'}$
   2. Si , entonces, cambia el tercer nivel a la parte superior de . Coloca el elemento alineado a la izquierda en este tercer nivel, de modo que toque un elemento del primer nivel a su izquierda. ${\displaystyle h_{2}>h(s)}$ ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle s}$
8. Continúe empaquetando los elementos utilizando la heurística First-Fit. Cada nivel siguiente (comenzando en el nivel tres) está definido por una línea horizontal que pasa por la parte superior del elemento más grande del nivel anterior. Tenga en cuenta que el primer elemento colocado en el siguiente nivel podría no tocar el borde de la tira con su lado izquierdo, sino un elemento del primer nivel o el elemento . ${\displaystyle s}$

Este algoritmo tiene las siguientes propiedades:

• El tiempo de ejecución puede limitarse mediante , ya que hay como máximo niveles. ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$ ${\displaystyle |{\mathcal {I}}|}$
• Para cada conjunto de elementos produce un empaquetamiento de altura . ^[13] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})}$

Algoritmo de Steinberg (ST)

El algoritmo de Steinberg es recursivo. Dado un conjunto de elementos rectangulares y una región objetivo rectangular con ancho y alto , propone cuatro reglas de reducción, que colocan algunos de los elementos y dejan una región rectangular más pequeña con las mismas propiedades que antes con respecto a los elementos residuales. Considere las siguientes notaciones: Dado un conjunto de elementos, denotamos por la altura del elemento más alta en , el ancho del elemento más grande que aparece en y por el área total de estos elementos. Steinberg muestra que si ${\displaystyle {\mathcal {I}}}$ ${\displaystyle W}$ ${\displaystyle H}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle h_{\max }({\mathcal {I}})}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle w_{\max }({\mathcal {I}})}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)}$

${\displaystyle h_{\max }({\mathcal {I}})\leq H}$, , y , donde , ${\displaystyle w_{\max }({\mathcal {I}})\leq W}$ ${\displaystyle \mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}}$ ${\displaystyle (a)_{+}:=\max\{0,a\}}$

Entonces, todos los elementos se pueden colocar dentro de la región objetivo de tamaño . Cada regla de reducción producirá un área objetivo más pequeña y un subconjunto de elementos que se deben colocar. Cuando la condición anterior se cumple antes de que comience el procedimiento, entonces el subproblema creado también tendrá esta propiedad. ${\displaystyle W\times H}$

Procedimiento 1 : Se puede aplicar si . ${\displaystyle w_{\max }({\mathcal {I}}')\geq W/2}$

1. Encuentra todos los elementos con ancho y elimínalos de . ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle w(i)\geq W/2}$ ${\displaystyle {\mathcal {I}}}$
2. Ordénelos por ancho no creciente y colóquelos alineados a la izquierda en la parte inferior de la región de destino. Sea su altura total. ${\displaystyle h_{0}}$
3. Encuentra todos los elementos con ancho . Quítalos y colócalos en un nuevo conjunto . ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle h(i)>H-h_{0}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}_{H}}$
4. Si está vacío, defina la nueva región objetivo como el área superior , es decir, tiene altura y ancho . Resuelva el problema que consiste en esta nueva región objetivo y el conjunto reducido de elementos con uno de los procedimientos. ${\displaystyle {\mathcal {I}}_{H}}$ ${\displaystyle h_{0}}$ ${\displaystyle H-h_{0}}$ ${\displaystyle W}$
5. Si no está vacío, ordénelo por altura no creciente y coloque los elementos alineados a la derecha uno por uno en la esquina superior derecha del área de destino. Sea el ancho total de estos elementos. Defina una nueva área de destino con ancho y altura en la esquina superior izquierda. Resuelva el problema que consiste en esta nueva región de destino y el conjunto reducido de elementos con uno de los procedimientos. ${\displaystyle {\mathcal {I}}_{H}}$ ${\displaystyle w_{0}}$ ${\displaystyle W-w_{0}}$ ${\displaystyle H-h_{0}}$

Procedimiento 2 : Se puede aplicar si se cumplen las siguientes condiciones: , , y existen dos elementos diferentes con , , , y . ${\displaystyle w_{\max }({\mathcal {I}})\leq W/2}$ ${\displaystyle h_{\max }({\mathcal {I}})\leq H/2}$ ${\displaystyle i,i'\in {\mathcal {I}}}$ ${\displaystyle w(i)\geq W/4}$ ${\displaystyle w(i')\geq W/4}$ ${\displaystyle h(i)\geq H/4}$ ${\displaystyle h(i')\geq H/4}$ ${\displaystyle 2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H}$

1. Encuéntrelos y elimínelos de . ${\displaystyle i}$ ${\displaystyle i'}$ ${\displaystyle {\mathcal {I}}}$
2. Coloque el más ancho en la esquina inferior izquierda del área objetivo y el más angosto alineado a la izquierda en la parte superior del primero.
3. Defina una nueva área de destino a la derecha de ambos elementos, de modo que tenga el ancho y la altura . ${\displaystyle W-\max\{w(i),w(i')\}}$ ${\displaystyle H}$
4. Coloque los elementos residuales en la nueva área objetivo utilizando uno de los procedimientos. ${\displaystyle {\mathcal {I}}}$

Procedimiento 3 : Se puede aplicar si se cumplen las siguientes condiciones: , , , y al ordenar los elementos por ancho decreciente existe un índice tal que al definir como los primeros elementos se cumple que además de ${\displaystyle w_{\max }({\mathcal {I}})\leq W/2}$ ${\displaystyle h_{\max }({\mathcal {I}})\leq H/2}$ ${\displaystyle |{\mathcal {I}}|>1}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {I'}}}$ ${\displaystyle m}$ ${\displaystyle \mathrm {AREA} ({\mathcal {I}})-WH/4\leq \mathrm {AREA} ({\mathcal {I'}})\leq 3WH/8}$ ${\displaystyle w(i_{m+1})\leq W/4}$

1. Colocar . ${\displaystyle W_{1}:=\max {W/2,2\mathrm {AREA} ({\mathcal {I'}})/H}}$
2. Define dos nuevas áreas objetivo rectangulares, una en la esquina inferior izquierda de la original, con altura y ancho , y la otra a la izquierda de esta, con altura y ancho . ${\displaystyle H}$ ${\displaystyle W_{1}}$ ${\displaystyle H}$ ${\displaystyle W-W_{1}}$
3. Utilice uno de los procedimientos para colocar los elementos en la primera área de destino nueva y los elementos en la segunda. ${\displaystyle {\mathcal {I'}}}$ ${\displaystyle {\mathcal {I}}\setminus {\mathcal {I'}}}$

Tenga en cuenta que los procedimientos 1 a 3 tienen una versión simétrica al intercambiar la altura y el ancho de los elementos y la región de destino.

Procedimiento 4 : Se puede aplicar si se cumplen las siguientes condiciones: , , y existe un elemento tal que . ${\displaystyle w_{\max }({\mathcal {I}})\leq W/2}$ ${\displaystyle h_{\max }({\mathcal {I}})\leq H/2}$ ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4}$

1. Coloque el objeto en la esquina inferior izquierda del área objetivo y retírelo de . ${\displaystyle i}$ ${\displaystyle {\mathcal {I}}}$
2. Defina una nueva área objetivo a la derecha de este elemento de modo que tenga el ancho y la altura y coloque los elementos residuales dentro de esta área utilizando uno de los procedimientos. ${\displaystyle W-w(i)}$ ${\displaystyle H}$

Este algoritmo tiene las siguientes propiedades:

• El tiempo de ejecución puede limitarse mediante . ^[8] ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))}$
• Para cada conjunto de elementos produce un empaquetamiento de altura . ^[8] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})}$

Algoritmos de aproximación temporal pseudopolinomiales

Para mejorar el límite inferior de los algoritmos de tiempo polinómico, se han considerado algoritmos de tiempo pseudopolinómico para el problema de empaquetamiento de tiras. Al considerar este tipo de algoritmos, todos los tamaños de los elementos y la tira se dan como integrales. Además, se permite que el ancho de la tira aparezca polinómicamente en el tiempo de ejecución. Tenga en cuenta que esto ya no se considera un tiempo de ejecución polinómico ya que, en el caso dado, el ancho de la tira necesita un tamaño de codificación de . ${\displaystyle 3/2}$ ${\displaystyle W}$ ${\displaystyle \log(W)}$

Los algoritmos de tiempo pseudopolinomial que se han desarrollado utilizan en su mayoría el mismo enfoque. Se demuestra que cada solución óptima se puede simplificar y transformar en una que tenga una de un número constante de estructuras. Luego, el algoritmo itera todas estas estructuras y coloca los elementos dentro mediante programación lineal y dinámica. La mejor relación lograda hasta ahora es . ^[20] mientras que no puede haber un algoritmo de tiempo pseudopolinomial con una relación mejor que a menos que ^[5] ${\displaystyle (5/4+\varepsilon )OPT(I)}$ ${\displaystyle 5/4}$ ${\displaystyle P=NP}$

Algoritmos en línea

En la variante en línea del embalaje en tiras, los artículos llegan a lo largo del tiempo. Cuando llega un artículo, debe colocarse inmediatamente antes de que se conozca el siguiente artículo. Se han considerado dos tipos de algoritmos en línea. En la primera variante, no se permite alterar el embalaje una vez que se coloca un artículo. En la segunda, los artículos pueden volver a empaquetarse cuando llega otro artículo. Esta variante se denomina modelo de migración.

La calidad de un algoritmo en línea se mide por la relación competitiva (absoluta)

${\displaystyle \mathrm {sup} _{I}A(I)/OPT(I)}$,

donde corresponde a la solución generada por el algoritmo en línea y corresponde al tamaño de la solución óptima. Además de la razón competitiva absoluta, se ha estudiado la razón competitiva asintótica de los algoritmos en línea. Para los casos con se define como ${\displaystyle A(I)}$ ${\displaystyle OPT(I)}$ ${\displaystyle I}$ ${\displaystyle h_{\max }(I)\leq 1}$

${\displaystyle \lim \mathrm {sup} _{OPT(I)\rightarrow \infty }A(I)/OPT(I)}$.

Tenga en cuenta que todas las instancias se pueden escalar de manera tal que . ${\displaystyle h_{\max }(I)\leq 1}$

El marco de trabajo de Han et al. ^[29] es aplicable en el entorno en línea si el algoritmo de empaquetamiento de bins en línea pertenece a la clase Super Harmonic. Por lo tanto, el algoritmo de empaquetamiento de bins en línea de Seiden, Harmonic++ ^[30], implica un algoritmo para el empaquetamiento de franjas en línea con una relación asintótica de 1,58889.

Referencias

1. Wäscher, Gerhard; Haußner, Heike; Schumann, Holger (16 de diciembre de 2007). "Una tipología mejorada de los problemas de corte y empaquetamiento". Revista Europea de Investigación Operativa . 183 (3): 1109–1130. doi :10.1016/j.ejor.2005.12.047. ISSN  0377-2217.
2. Baker, Brenda S.; Coffman Jr., Edward G.; Rivest, Ronald L. (1980). "Empaquetamientos ortogonales en dos dimensiones". SIAM J. Comput . 9 (4): 846–855. CiteSeerX 10.1.1.309.8883 . doi :10.1137/0209064. 
3. Harren, Rolf; Jansen, Klaus; Prädel, Lars; van Stee, Rob (febrero de 2014). "Una aproximación (5/3 + épsilon) para el empaquetamiento de franjas". Geometría computacional . 47 (2): 248–267. doi : 10.1016/j.comgeo.2013.08.008 .
4. Neuenfeldt Junior, Alvaro Luiz. "El problema del empaquetamiento de tiras rectangulares bidimensionales" (PDF) . 10820228.
5. Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (2019). "Resultados de complejidad e inaproximabilidad para programación de tareas paralelas y empaquetamiento de bandas". Teoría de sistemas informáticos . 64 : 120–140. arXiv : 1705.04587 . doi :10.1007/s00224-019-09910-6. S2CID  67168004.
6. Ashok, Pradeesha; Kolay, Sudeshna; Meesum, SM; Saurabh, Saket (enero de 2017). "Complejidad parametrizada del empaquetamiento de bandas y del empaquetamiento de volumen mínimo". Ciencias de la computación teórica . 661 : 56–64. doi : 10.1016/j.tcs.2016.11.034 .
7. Martello, Silvano; Monaci, Michele; Vigo, Daniele (1 de agosto de 2003). "Un enfoque exacto al problema del empaquetamiento de bandas". INFORMS Journal on Computing . 15 (3): 310–319. doi :10.1287/ijoc.15.3.310.16082. ISSN  1091-9856.
8. Steinberg, A. (marzo de 1997). "Un algoritmo de empaquetamiento de bandas con límite de rendimiento absoluto 2". Revista SIAM de informática . 26 (2): 401–409. doi :10.1137/S0097539793255801.
9. Coffman Jr., Edward G.; Garey, MR; Johnson, David S.; Tarjan, Robert Endre (1980). "Límites de rendimiento para algoritmos de empaquetamiento bidimensional orientados a niveles". SIAM J. Comput . 9 (4): 808–826. doi :10.1137/0209062.
10. Sleator, Daniel Dominic (1980). "Un algoritmo 2,5 veces óptimo para empaquetamiento en dos dimensiones". Inf. Process. Lett . 10 : 37–40. doi :10.1016/0020-0190(80)90121-0.
11. Golan, Igal (agosto de 1981). "Límites de rendimiento para algoritmos de empaquetamiento bidimensionales orientados ortogonalmente". Revista SIAM de informática . 10 (3): 571–582. doi :10.1137/0210042.
12. Baker, Brenda S; Brown, Donna J; Katseff, Howard P (diciembre de 1981). "Un algoritmo 5/4 para empaquetamiento bidimensional". Journal of Algorithms . 2 (4): 348–368. doi :10.1016/0196-6774(81)90034-1.
13. Schiermeyer, Ingo (1994). "Reverse-Fit: Un algoritmo 2-óptimo para empaquetar rectángulos". Algoritmos — ESA '94 . Apuntes de clase en Ciencias de la Computación. Vol. 855. Springer Berlin Heidelberg. págs. 290–299. doi :10.1007/bfb0049416. ISBN 978-3-540-58434-6.
14. Kenyon, Claire ; Rémila, Eric (noviembre de 2000). "Una solución casi óptima para un problema de material de corte bidimensional". Matemáticas de la investigación de operaciones . 25 (4): 645–656. doi :10.1287/moor.25.4.645.12118. S2CID  5361969.
15. Harren, Rolf; van Stee, Rob (2009). "Razones de aproximación absoluta mejoradas para problemas de empaquetamiento bidimensional". Aproximación, aleatorización y optimización combinatoria. Algoritmos y técnicas . Apuntes de clase en informática. Vol. 5687. págs. 177–189. Código Bibliográfico :2009LNCS.5687..177H. doi :10.1007/978-3-642-03685-9_14. ISBN: 978-3-642-03685-9_14 . 978-3-642-03684-2.
16. Jansen, Klaus; Solis-Oba, Roberto (agosto de 2009). "Empaquetamiento rectangular con aumento de recursos unidimensional". Optimización discreta . 6 (3): 310–323. doi :10.1016/j.disopt.2009.04.001.
17. Bougeret, Marin; Dutot, Pierre-Francois; Jansen, Klaus; Robenek, Christina; Trystram, Denis (5 de abril de 2012). "Algoritmos de aproximación para empaquetado de múltiples bandas y programación de trabajos paralelos en plataformas". Matemáticas discretas, algoritmos y aplicaciones . 03 (4): 553–586. doi :10.1142/S1793830911001413.
18. Sviridenko, Maxim (enero de 2012). "Una nota sobre el algoritmo de empaquetamiento de bandas Kenyon-Remila". Information Processing Letters . 112 (1–2): 10–12. doi :10.1016/j.ipl.2011.10.003.
19. Hougardy, Stefan; Zondervan, Bart (26 de febrero de 2024), El algoritmo inferior izquierdo para el problema de empaquetamiento de tiras , arXiv : 2402.16572
20. Jansen, Klaus; Rau, Malin (2019). "Cerrando la brecha para el empaquetamiento de tiras pseudopolinomiales" . Procedimientos internacionales de informática de Leibniz (LIPIcs). vol. 144. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. págs. 62:1–62:14. doi : 10.4230/LIPIcs.ESA.2019.62 . ISBN 9783959771245. Número de identificación del sujeto  24303167.
21. Jansen, Klaus; Thöle, Ralf (enero de 2010). "Algoritmos de aproximación para la programación de trabajos paralelos". Revista SIAM de informática . 39 (8): 3571–3615. doi :10.1137/080736491.
22. Nadiradze, Giorgi; Wiese, Andreas (21 de diciembre de 2015). "Sobre la aproximación del empaquetamiento de bandas con una relación mejor que 3/2". Actas del vigésimo séptimo simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemáticas Industriales y Aplicadas. págs. 1491–1510. doi :10.1137/1.9781611974331.ch102. ISBN . 978-1-61197-433-1.
23. Gálvez, Waldo; Grandoni, Fabricio; Ingala, Salvatore; Khan, Arindam (2016). "Aproximación mejorada del tiempo pseudopolinomial para el embalaje en tiras" . Procedimientos internacionales de informática de Leibniz (LIPIcs). vol. 65. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. págs. 9:1–9:14. doi : 10.4230/LIPIcs.FSTTCS.2016.9 . ISBN 9783959770279.S2CID3205478  .​
24. Jansen, Klaus; Rau, Malin (29-31 de marzo de 2017). "Aproximación mejorada para empaquetamiento de bandas bidimensional con ancho limitado por polinomios". WALCOM: Algoritmos y computación . Apuntes de clase en informática. Vol. 10167. págs. 409-420. arXiv : 1610.04430 . doi :10.1007/978-3-319-53925-6_32. ISBN . 978-3-319-53924-9.S2CID15768136  .​
25. Baker, Brenda S.; Schwarz, Jerald S. (1 de agosto de 1983). "Algoritmos de estantería para problemas de empaquetamiento bidimensional". Revista SIAM de Computación . 12 (3): 508–525. doi :10.1137/0212033. ISSN  0097-5397.
26. Csirik, János; Woeginger, Gerhard J. (28 de agosto de 1997). "Algoritmos de estantería para el empaquetado en línea de tiras". Cartas de procesamiento de la información . 63 (4): 171–175. doi :10.1016/S0020-0190(97)00120-8. ISSN  0020-0190.
27. Hurink, Johann L.; Paulus, Jacob Jan (2007). "Algoritmo en línea para programación de trabajos en paralelo y empaquetamiento de bandas" (PDF) . Aproximación y algoritmos en línea . Apuntes de clase en informática. Vol. 4927. Springer Berlin Heidelberg. págs. 67–74. doi :10.1007/978-3-540-77918-6_6. ISBN . 978-3-540-77917-9.
28. Ye, Deshi; Han, Xin; Zhang, Guochuan (1 de mayo de 2009). "Una nota sobre el empaquetamiento de bandas en línea". Revista de optimización combinatoria . 17 (4): 417–423. doi :10.1007/s10878-007-9125-x. ISSN  1573-2886. S2CID  37635252.
29. Han, Xin; Iwama, Kazuo; Ye, Deshi; Zhang, Guochuan (2007). "Empaquetado en tiras frente a empaquetado en contenedores". Aspectos algorítmicos de la información y la gestión . Apuntes de clase sobre informática. Vol. 4508. Springer Berlin Heidelberg. págs. 358–367. arXiv : cs/0607046 . doi :10.1007/978-3-540-72870-2_34. ISBN . 978-3-540-72868-9.S2CID  580 .
30. Seiden, Steven S. (2001). "Sobre el problema del empaquetamiento de contenedores en línea". Autómatas, lenguajes y programación . Apuntes de clase en informática. Vol. 2076. Springer Berlin Heidelberg. págs. 237–248. doi :10.1007/3-540-48224-5_20. ISBN 978-3-540-42287-7.
31. Brown, Donna J.; Baker, Brenda S.; Katseff, Howard P. (1 de noviembre de 1982). "Límites inferiores para algoritmos de empaquetamiento bidimensional en línea". Acta Informatica . 18 (2): 207–225. doi :10.1007/BF00264439. hdl : 2142/74223 . ISSN  1432-0525. S2CID  21170278.
32. Johannes, Berit (1 de octubre de 2006). "Programación de trabajos paralelos para minimizar el tiempo de ejecución" (PDF) . Journal of Scheduling . 9 (5): 433–452. doi :10.1007/s10951-006-8497-6. ​​hdl :20.500.11850/36804. ISSN  1099-1425. S2CID  18819458.
33. Hurink, JL; Paulus, JJ (1 de enero de 2008). "La programación en línea de trabajos paralelos en dos máquinas es 2-competitiva" (PDF) . Operations Research Letters . 36 (1): 51–56. doi :10.1016/j.orl.2007.06.001. ISSN  0167-6377. S2CID  15561044.
34. Kern, Walter; Paulus, Jacob Jan (2009). "Una nota sobre el límite inferior para el empaquetado en línea". Operations Research Letters .
35. Balogh, János; Békési, József; Galambos, Gábor (6 de julio de 2012). "Nuevos límites inferiores para determinadas clases de algoritmos de embalaje de contenedores". Informática Teórica . 440–441: 1–13. doi : 10.1016/j.tcs.2012.04.017 . ISSN  0304-3975.
36. Yu, Guosong; Mao, Yanling; Xiao, Jiaoliao (1 de mayo de 2016). "Un nuevo límite inferior para el empaquetamiento en línea". Revista Europea de Investigación Operativa . 250 (3): 754–759. doi :10.1016/j.ejor.2015.10.012. ISSN  0377-2217.