Problema de embalaje de tiras

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

Este problema surge en el área de la programación, donde modela trabajos que requieren una porción contigua de la memoria durante un período de tiempo determinado. Otro ejemplo es el área de la fabricación industrial, donde es necesario 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 de tiempo polinómico con una relación menor que a menos que . Sin embargo, la mejor relación de aproximación lograda hasta ahora (mediante un algoritmo de tiempo polinomial de Harren et al. ^[3] ) es , lo que impone una pregunta abierta sobre si existe un algoritmo con relación de aproximación . ${\displaystyle 3/2}$ ${\displaystyle P=NP}$ ${\displaystyle (5/3+\varepsilon )}$ ${\displaystyle 3/2}$

Definición

Un ejemplo del problema del embalaje en tiras consiste en una tira con ancho y alto infinitos, así como un conjunto de elementos rectangulares. Cada elemento tiene un ancho y un alto . Un embalaje de los artículos es un mapeo que asigna cada esquina inferior izquierda de un artículo a una posición dentro de la tira. Un punto interior de un elemento colocado es un punto del conjunto . Dos elementos (colocados) se superponen si comparten un punto interior. La altura del embalaje se define como . El objetivo es encontrar un embalaje sin superposiciones de los artículos dentro de la tira minimizando la altura del embalaje. ${\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 polinomial. Para los algoritmos de tiempo pseudopolinomial y FPT , la definición se modifica ligeramente para simplificar la notación. En este caso, todos los tamaños que aparecen son integrales. Especialmente el ancho de la tira viene dado por un número entero arbitrario mayor que 1. Tenga en cuenta que estas dos definiciones son equivalentes.

Variantes

Se han estudiado varias variantes del problema del embalaje 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 artículos y la estructura del embalaje. ^[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 tienen que ser cuadrados. Esta variante ya se consideró en el primer artículo sobre embalaje en tiras. ^[2] Además, se han estudiado variantes donde las formas son circulares o incluso irregulares. En este último caso, se denomina embalaje en tiras irregulares .

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

Rotación: en el problema clásico del embalaje en tiras, no se permite rotar los artículos. Sin embargo, se han estudiado variantes en las que se permite girar 90 grados o incluso 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. Las empaquetaduras que permiten este tipo de corte se denominan empaquetaduras de guillotina .

Dureza

El problema del embalaje en tiras contiene el problema del embalaje 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 ningún 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 pseudopolinomial que tenga una relación de aproximación menor que , ^[5], lo que puede demostrarse mediante una reducción del problema de 3 particiones fuertemente NP-completo . Tenga en cuenta que ambos límites inferiores también se cumplen en el caso de que se permita una rotación de los elementos de 90 grados. Además, fue demostrado por Ashok et al. ^[6] ese empaque en tira es de dureza W[1] cuando se parametriza por la altura del empaque óptimo. ${\displaystyle 3/2}$ ${\displaystyle P=NP}$ ${\displaystyle P=NP}$ ${\displaystyle 5/4}$ ${\displaystyle 3/2}$ ${\displaystyle 5/4}$

Propiedades de las soluciones óptimas.

Hay dos límites inferiores triviales para las soluciones óptimas. La primera es la altura del elemento más grande. Definir . Entonces se sostiene 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 artículos. Definir entonces 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 franja y se pueden calcular en . ^[7] Para el primer límite inferior, suponga que los elementos están ordenados por altura no creciente. Definir . Para cada uno, defina el primer índice de manera que . Entonces se sostiene 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. Dejemos y definamos , , y . Entonces se sostiene 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 otro lado, 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 , los elementos se pueden colocar 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-difícil, se han estudiado algoritmos de aproximación para este problema. La mayoría de los enfoques heurísticos tienen una relación de aproximación entre y . Encontrar un algoritmo con una relación inferior parece complicado, y la complejidad de los algoritmos correspondientes aumenta en cuanto a su tiempo de ejecución y sus descripciones. El ratio de aproximación más pequeño logrado hasta el momento es . ${\displaystyle 3}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle (5/3+\varepsilon )}$

Abajo arriba 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] 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 inferior para colocarlo y luego lo desplaza lo más hacia la izquierda posible. Por lo tanto, se coloca en la coordenada más abajo 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 relación de aproximación de este algoritmo no puede estar limitada por una constante. Más precisamente, demostraron que para cada uno existe una lista de elementos rectangulares ordenados por ancho creciente, de modo que , donde es la altura del embalaje 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 están ordenados por anchos decrecientes, entonces . ^[2] ${\displaystyle BL(L)/OPT(L)\leq 3}$
• Si los elementos son todos cuadrados y están ordenados por anchos decrecientes, entonces . ^[2] ${\displaystyle BL(L)/OPT(L)\leq 2}$
• Para cualquiera , 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 cualquiera , 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 proporción de , es decir, existen instancias donde BL no encuentra el óptimo incluso al iterar 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 }}}$

Altura decreciente de siguiente ajuste (NFDH)

Un ejemplo de NFDH y FFDH aplicado 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 clasifica 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 tira hasta que el siguiente elemento se superponga al borde derecho de la tira. En este punto, el algoritmo define un nuevo nivel en la parte superior del elemento más alto del 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 estar limitado por 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 artículos , produce un embalaje de altura , donde es la altura más grande de un artículo 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 generado es un embalaje de guillotina. Esto significa que los artículos se pueden obtener mediante una secuencia de cortes horizontales o verticales de borde a borde.

Altura decreciente de primer ajuste (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 hacia arriba y coloca el elemento en el primer nivel en el que encajará. Sólo se abre un nuevo nivel si el elemento no encaja en ninguno anterior.

Este algoritmo tiene las siguientes propiedades:

• El tiempo de ejecución puede estar limitado por , ya que en la mayoría de los niveles los hay . ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$ ${\displaystyle |{\mathcal {I}}|}$
• Para cada conjunto de artículos, produce un embalaje de altura , donde es la altura más grande de un artículo 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}}}$
• Dejar . Para cualquier conjunto de elementos y tira con un ancho tal que para cada uno , se cumple . Además, para cada uno , 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 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 generado es un embalaje de guillotina. Esto significa que 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 determinado de elementos y una tira con ancho , funciona de la siguiente manera: ${\displaystyle {\mathcal {I}}}$ ${\displaystyle W}$

1. Determinado , el número entero más grande tal que los rectángulos dados tengan ancho o menos. ${\displaystyle m\in \mathbb {N} }$ ${\displaystyle W/m}$
2. Divida 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. Empaque los artículos con el algoritmo FFDH. ${\displaystyle {\mathcal {I}}_{wide}}$
5. Reordene los niveles/estantes construidos por FFDH de modo que todos los estantes con un ancho total mayor queden debajo de los más estrechos. ${\displaystyle W(m+1)/(m+2)}$
6. Esto deja un área rectangular , junto a niveles/estantes más estrechos, que no contiene ningún artículo. ${\displaystyle R}$ ${\displaystyle W/(m+2)}$
7. Utilice también el algoritmo FFDH para empaquetar los artículos utilizando el área . ${\displaystyle {\mathcal {I}}_{narrow}}$ ${\displaystyle R}$

Este algoritmo tiene las siguientes propiedades:

• Para cada conjunto de elementos y el correspondiente , se cumple eso . ^[9] Tenga en cuenta 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 uno , hay 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 determinado de elementos y una tira con ancho , funciona de la siguiente manera: ${\displaystyle {\mathcal {I}}}$ ${\displaystyle W}$

1. Encuentre todos los elementos con un ancho mayor que y apílelos en la parte inferior de la tira (en orden aleatorio). Llame a la altura total de estos elementos . Todos los demás elementos se colocarán arriba . ${\displaystyle W/2}$ ${\displaystyle h_{0}}$ ${\displaystyle h_{0}}$
2. Ordene todos los elementos restantes en orden no creciente de altura. Los artículos se colocarán en este orden.
3. Considere la línea horizontal como un estante. El algoritmo coloca los artículos en este estante en orden de altura no creciente hasta que no queda ningún artículo o el siguiente no cabe. ${\displaystyle h_{0}}$
4. Dibuja 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. Dibuja dos segmentos de línea horizontal de longitud a lo largo de la mitad izquierda y derecha de la tira. Estas dos líneas construyen nuevos estantes en los que el algoritmo colocará los artículos, como en el paso 3. Elija la mitad que tiene el estante inferior y coloque los artículos en este estante hasta que no quepa ningún otro artículo. 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 estar limitado por 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 artículos, produce un embalaje de altura , donde es la altura más grande de un artículo 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 al lado de un elemento ya colocado . En este caso, divide la subfranja correspondiente en dos partes: una que contiene el primer elemento y la otra que contiene el elemento actual . Si esto no es posible, se 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 subfranjas. Para cada subfranjas ∈ Sconocemos su esquina inferior izquierdas.xposiciónys.yposición, su anchos.ancho, las líneas horizontales paralelas al borde superior e inferior del artículo colocado en último lugar dentro de esta subfranjacenayMás lento, así como el ancho del mismo.s.itemAncho.

Se ingresa  la función Algoritmo de división (SP) :  elementos I, ancho de la tiraW. Salida:  Un embalaje de los artículos. Ordenar I en orden no creciente de anchos; Defina la lista vacía S de subfranjas; Defina una nueva subfranja s con s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W; Agregue s a S; mientras no lo vacío hago i := I.pop(); Elimina el elemento más ancho de I Defina una nueva lista S_2 que contenga 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 ,  en este caso, coloque el elemento encima de otro. Encuentre la subfranja s en S con la s.superior más pequeña; es decir, la subfranja menos llena Coloque i en la posición (s.xposition, s.upper); Actualizar s: s.lower := s.upper; s.superior := s.superior+i.altura; s.itemWidth:= i.width; de lo contrario,  en este caso, coloque el artículo al lado de otro en el mismo nivel y divida la subtira correspondiente en esta posición. Encuentre 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; Defina dos nuevas subfranjas s1 y s2 con s1.xposition = s.xposition, s1.yposition = s.upper, s1.width = s.itemWidth, s1.lower = s.upper, s1.upper = s.upper, 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. altura, s2.itemWidth = i.width; S.add(s1,s2);  función final de retorno

Este algoritmo tiene las siguientes propiedades:

• El tiempo de ejecución puede estar limitado por ya que el número de subfranjas está limitado por . ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$ ${\displaystyle |{\mathcal {I}}|}$
• Para cualquier conjunto de elementos se cumple eso . ^[11] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}$
• Para cualquiera , existe un conjunto de elementos tales que . ^[11] ${\displaystyle \varepsilon >0}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})}$
• Para cualquiera 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 indica con y su esquina superior derecha con . ${\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 uno encima del otro (en orden aleatorio) en la parte inferior de la tira. Denota por la altura de esta pila. Todos los demás artículos se empaquetará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 más alto de estos elementos restantes. ${\displaystyle h_{\max }}$
3. Coloque los artículos uno por uno alineados a la izquierda en un estante definido por hasta que no quepa ningún otro artículo en este estante o no quede ningún artículo. 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. Coloque los artículos en los dos estantes gracias al First-Fit, es decir, colocando los artículos en el primer nivel donde encajan y en el segundo en caso contrario. Continúe hasta que no queden artículos o hasta que el ancho total de los artículos en el segundo estante sea al menos . ${\displaystyle W/2}$
6. Mueve el segundo nivel inverso hacia abajo hasta que un elemento toque un elemento del primer nivel. Definir como la nueva posición vertical del estante desplazado. Sea y sea el par de elementos en contacto más a la derecha 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 el último rectángulo se coloca en el segundo nivel inverso. Mueve 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 en contacto 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. Luego , muévase hacia la izquierda hasta que toque 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, defina el tercer nivel en la parte superior de . Colóquelo 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 es posible que el primer elemento colocado en el siguiente nivel no toque 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 estar limitado por , ya que en la mayoría de los niveles los hay . ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$ ${\displaystyle |{\mathcal {I}}|}$
• Para cada conjunto de artículos produce un embalaje 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, lo denotamos por la altura más alta del elemento en , el ancho más grande del elemento 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 de tamaño objetivo . Cada regla de reducción producirá un área objetivo más pequeña y un subconjunto de elementos que deberán colocarse. Cuando la condición anterior se cumple antes de que comenzara el procedimiento, 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. Busque todos los elementos con ancho y elimínelos . ${\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 artículos con ancho . Retírelos y colóquelos en un juego nuevo . ${\displaystyle i\in {\mathcal {I}}}$ ${\displaystyle h(i)>H-h_{0}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {I}}_{H}}$
4. Si está vacía, defina la nueva región de destino como el área de arriba , es decir, tiene alto 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 uno por uno en la esquina superior derecha del área objetivo. Sea el ancho total de estos elementos. Defina una nueva área objetivo con ancho y alto en la esquina superior izquierda. 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 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. Busque 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 estrecho alineado a la izquierda en la parte superior del primero.
3. Defina una nueva área objetivo a la derecha de ambos elementos, de modo que tenga el ancho y el alto . ${\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 tanto como ${\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. Defina dos nuevas áreas de destino rectangulares, una en la esquina inferior izquierda de la original con altura y ancho y la otra a la izquierda 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 objetivo 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 elemento en la esquina inferior izquierda del área objetivo y elimínelo . ${\displaystyle i}$ ${\displaystyle {\mathcal {I}}}$
2. Defina una nueva área objetivo a la derecha de este elemento de modo que tenga el ancho y el alto 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 estar limitado por . ^[8] ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))}$
• Para cada conjunto de artículos produce un embalaje de altura . ^[8] ${\displaystyle {\mathcal {I}}}$ ${\displaystyle ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})}$

Algoritmos de aproximación de tiempo pseudopolinomial

Para mejorar el límite inferior de los algoritmos de tiempo polinomial, se han considerado algoritmos de tiempo pseudopolinomial para el problema de empaquetado en tiras. Al considerar este tipo de algoritmos, todos los tamaños de los elementos y de 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 polinomial 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 pseudopolinomiales que se han desarrollado utilizan en su mayoría el mismo enfoque. Se muestra 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 en su interior mediante programación lineal y dinámica. La mejor proporción lograda hasta el momento es . ^[20] si bien 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 online del embalaje en tiras, los artículos llegan con el 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 colocado el artículo. En el segundo, los artículos podrán ser reembalados cuando llegue otro artículo. Esta variante se llama modelo de migración.

La calidad de un algoritmo en línea se mide por el ratio competitivo (absoluto)

${\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 del ratio competitivo absoluto, se ha estudiado el ratio competitivo asintótico de los algoritmos online. Por ejemplo, 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 modo que . ${\displaystyle h_{\max }(I)\leq 1}$

El marco de Han et al. ^[29] es aplicable en la configuración en línea si el algoritmo de empaquetamiento de contenedores en línea pertenece a la clase Super Armónico. Por lo tanto, el algoritmo de embalaje de contenedores en línea de Seiden, Harmonic++ ^[30], implica un algoritmo para el embalaje de tiras 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 problemas de corte y embalaje". Revista europea de investigación operativa . 183 (3): 1109-1130. doi :10.1016/j.ejor.2005.12.047. ISSN  0377-2217.
2. Hougardy, Stefan; Zondervan, Bart (26 de febrero de 2024), El algoritmo inferior izquierdo para el problema del empaquetado en tiras, arXiv : 2402.16572 , consultado el 11 de abril de 2024
3. Harren, Rolf; Jansen, Klaus; Prädel, Lars; van Stee, Rob (febrero de 2014). "Aproximación (5/3 + épsilon) para embalaje en tiras". Geometría Computacional . 47 (2): 248–267. doi : 10.1016/j.comgeo.2013.08.008 .
4. Neuenfeldt Junior, Álvaro Luiz. "El problema del embalaje en tiras rectangulares bidimensionales" (PDF) . 10820228.
5. Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (2019). "Resultados de complejidad e inaproximabilidad para la programación de tareas paralelas y el embalaje en tiras". Teoría de los Sistemas Computacionales . 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 embalaje en tiras y embalaje en volumen mínimo". Informática 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 embalaje en tiras". Revista INFORMA de Informática . 15 (3): 310–319. doi :10.1287/ijoc.15.3.310.16082. ISSN  1091-9856.
8. Steinberg, A. (marzo de 1997). "Un algoritmo de empaquetado en tiras con rendimiento absoluto limitado a 2". Revista SIAM de Computación . 26 (2): 401–409. doi :10.1137/S0097539793255801.
9. Coffman Jr., Edward G.; Garey, señor; Johnson, David S.; Tarjan, Robert Endre (1980). "Límites de rendimiento para algoritmos de embalaje bidimensionales orientados a niveles". SIAM J. Computación . 9 (4): 808–826. doi :10.1137/0209062.
10. Sleator, Daniel Dominic (1980). "Un algoritmo 2,5 veces óptimo para empaquetar en dos dimensiones". inf. Proceso. 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 embalaje bidimensionales orientados ortogonalmente". Revista SIAM de Computación . 10 (3): 571–582. doi :10.1137/0210042.
12. Panadero, Brenda S; Marrón, Donna J; Katseff, Howard P (diciembre de 1981). "Un algoritmo 5/4 para embalaje bidimensional". Revista de algoritmos . 2 (4): 348–368. doi :10.1016/0196-6774(81)90034-1.
13. Schiermeyer, Ingo (1994). "Ajuste inverso: un algoritmo 2 óptimo para empaquetar rectángulos". Algoritmos - ESA '94 . Apuntes de conferencias sobre informática. vol. 855. Springer Berlín 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). "Ratios de aproximación absoluta mejorados para problemas de embalaje bidimensionales". Aproximación, aleatorización y optimización combinatoria. Algoritmos y Técnicas . Apuntes de conferencias sobre informática. vol. 5687, págs. 177–189. Código Bib : 2009LNCS.5687..177H. doi :10.1007/978-3-642-03685-9_14. ISBN 978-3-642-03684-2.
16. Jansen, Klaus; Solís-Oba, Roberto (agosto de 2009). "Embalaje rectangular con aumento de recursos unidimensional". Optimización discreta . 6 (3): 310–323. doi :10.1016/j.disopt.2009.04.001.
17. Bougeret, Marín; Dutot, Pierre-François; Jansen, Klaus; Robenek, Cristina; Trystram, Denis (5 de abril de 2012). "Algoritmos de aproximación para embalaje de múltiples tiras 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 empaquetado en tiras de Kenyon-Remila". Cartas de Procesamiento de Información . 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 del embalaje de tiras, arXiv : 2402.16572 , consultado el 11 de abril de 2024
20. Jansen, Klaus; Rau, Malin (2019). "Cerrando la brecha para el empaquetamiento en 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. S2CID  24303167.
21. Jansen, Klaus; Thöle, Ralf (enero de 2010). "Algoritmos de aproximación para la programación de trabajos paralelos". Revista SIAM de Computación . 39 (8): 3571–3615. doi : 10.1137/080736491.
22. Nadiradze, Giorgi; Wiese, Andreas (21 de diciembre de 2015). "Al aproximar el embalaje en tiras con una proporción mejor que 3/2". Actas del vigésimo séptimo simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemática Industrial y Aplicada. 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. S2CID  3205478.
24. Jansen, Klaus; Rau, Malin (29 a 31 de marzo de 2017). "Aproximación mejorada para empaquetaduras en tiras bidimensionales con ancho polinomial delimitado". WALCOM: Algoritmos y Computación . Apuntes de conferencias sobre 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. S2CID  15768136.
25. Panadero, Brenda S.; Schwarz, Jerald S. (1 de agosto de 1983). "Algoritmos de estantería para problemas de embalaje bidimensionales". 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 envasado en tiras en línea". Cartas de Procesamiento de 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 paralelos y embalaje de tiras" (PDF) . Aproximación y Algoritmos en Línea . Apuntes de conferencias sobre informática. vol. 4927. Springer Berlín Heidelberg. págs. 67–74. doi :10.1007/978-3-540-77918-6_6. ISBN 978-3-540-77917-9.
28. Sí, Deshi; Han, Xin; Zhang, Guochuan (1 de mayo de 2009). "Una nota sobre el embalaje en tiras 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; Sí, Deshi; Zhang, Guochuan (2007). "Embalaje en tiras frente a embalaje en contenedores". Aspectos Algorítmicos en Información y Gestión . Apuntes de conferencias sobre informática. vol. 4508. Springer Berlín 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 embalaje de contenedores en línea". Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. vol. 2076. Springer Berlín Heidelberg. págs. 237-248. doi :10.1007/3-540-48224-5_20. ISBN 978-3-540-42287-7.
31. Marrón, Donna J.; Panadero, Brenda S.; Katseff, Howard P. (1 de noviembre de 1982). "Límites inferiores para algoritmos de empaquetado bidimensionales en línea". Acta Informática . 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 espacio de trabajo" (PDF) . Diario de programación . 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 competitiva" (PDF) . Cartas de investigación operativa . 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 embalaje en tiras en línea". Cartas de investigación operativa .
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 embalaje de tiras en línea". Revista europea de investigación operativa . 250 (3): 754–759. doi :10.1016/j.ejor.2015.10.012. ISSN  0377-2217.