Hispanopedia Wiki
Articulo de referencia

Problema de empaquetamiento de tiras

El problema de empaquetamiento de tiras es un problema de minimización geométrica bidimensional. Dado un conjunto de rectángulos alineados con los ejes y una tira de ancho limit...

Hispanopedia WikiContenido en espanolLectura gratuita

El problema de empaquetamiento de tiras es un problema de minimización geométrica bidimensional. Dado un conjunto de rectángulos alineados con los ejes y una tira de ancho limitado y altura infinita, se debe determinar un empaquetamiento sin superposición de los rectángulos dentro de la tira, 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 ámbito de la planificación, donde se modelan tareas que requieren una porción contigua de la memoria durante un período de tiempo determinado. Otro ejemplo se encuentra en la fabricación industrial, donde se necesitan cortar piezas rectangulares de una lámina de material (por ejemplo, tela o papel) de ancho fijo pero longitud infinita, y se busca minimizar el desperdicio de material.

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 polinomial con una razón menor que 3/2{\displaystyle 3/2}a menos quePAG=nortePAG{\displaystyle P=NP}Sin embargo, la mejor relación de aproximación lograda hasta ahora (mediante un algoritmo de tiempo polinomial de Harren et al. [ 3 ] ) es(5/3+ε){\displaystyle (5/3+\varepsilon )}, lo que plantea la cuestión abierta de si existe un algoritmo con una relación de aproximación.3/2{\displaystyle 3/2}.

Definición

Un ejemploI=(I,W){\displaystyle I=({\mathcal {I}},W)}del problema de empaquetamiento de tiras consiste en una tira con anchoW=1{\displaystyle W=1}y altura infinita, así como un conjuntoI{\displaystyle {\mathcal {I}}}de artículos rectangulares. Cada artículoi∈I{\displaystyle i\in {\mathcal {I}}}tiene un anchowi∈(0,1]∩Q{\displaystyle w_{i}\in (0,1]\cap \mathbb {Q} }y una altura hi∈(0,1]∩Q{\displaystyle h_{i}\in (0,1]\cap \mathbb {Q} }. Un empaquetado de los elementos es un mapeo que asigna cada esquina inferior izquierda de un elemento.i∈I{\displaystyle i\in {\mathcal {I}}}a una posición (incógnitai,yi)∈([0,1−wi]∩Q)×Q≥0{\displaystyle (x_{i},y_{i})\in ([0,1-w_{i}]\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}}dentro de la tira. Un punto interior de un elemento colocado.i∈I{\displaystyle i\in {\mathcal {I}}}es un punto del conjuntoinortenorte(i)={(incógnita,y)∈Q×Q|incógnitai<incógnita<incógnitai+wi,yi<y<yi+hi}{\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}\}}Dos elementos (colocados) se superponen si comparten un punto interior. La altura del empaque se define comomáximo{yi+hi|i∈I}{\displaystyle \max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}}El objetivo es encontrar una disposición de los elementos dentro de la tira que no se superponga, minimizando al mismo tiempo la altura del empaque.

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, todas las dimensiones que aparecen son números enteros. En particular, el ancho de la franja viene dado por un número entero arbitrario mayor que 1. Cabe destacar que estas dos definiciones son equivalentes.

Variantes

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

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

Dimensión: Salvo que se indique lo contrario, el problema de empaquetamiento de tiras es 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 es abierta en una dimensión y limitada en las restantes.

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

Estructura: En el problema general del empaquetado en tiras, la estructura del empaquetado es irrelevante. Sin embargo, existen aplicaciones con requisitos explícitos sobre la estructura del empaquetado. Uno de estos requisitos es poder cortar los elementos de la tira mediante cortes horizontales o verticales de borde a borde. Los empaquetados que permiten este tipo de corte se denominan empaquetados 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-difícil, y no puede haber ningún algoritmo de aproximación de tiempo polinomial que tenga una razón de aproximación menor que3/2{\displaystyle 3/2}a menos quePAG=nortePAG{\displaystyle P=NP}Además, a menos que...PAG=nortePAG{\displaystyle P=NP}, no puede haber un algoritmo de tiempo pseudopolinomial que tenga una razón de aproximación menor que5/4{\displaystyle 5/4}, [ 5 ] lo cual puede probarse mediante una reducción del problema de 3-particiones fuertemente NP-completo . Nótese que ambos límites inferiores3/2{\displaystyle 3/2}y5/4{\displaystyle 5/4}Esto también se aplica al 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]-difícil cuando se parametriza por la altura del empaquetamiento óptimo.

Propiedades de las soluciones óptimas

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

OPAGT(I)≥hmáximo(I){\displaystyle OPT(I)\geq h_{\max }(I)}.

Otro límite inferior viene dado por el área total de los elementos. DefinirARmiA(I):=∑i∈Ih(i)w(i){\displaystyle \mathrm {ÁREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)}entonces sostiene que

OPAGT(I)≥ARmiA(I)/W{\displaystyle OPT(I)\geq \mathrm {ÁREA} ({\mathcal {I}})/W}.

Los siguientes dos límites inferiores tienen en cuenta el hecho de que ciertos elementos no pueden colocarse uno al lado del otro en la tira y pueden calcularse enO(norteregistro⁡(norte)){\displaystyle {\mathcal {O}}(n\log(n))}. [ 7 ] Para el primer límite inferior, suponga que los elementos están ordenados por altura no creciente. Definak:=máximo{i:∑j=1kw(j)≤W}{\displaystyle k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}}. Para cadal>k{\displaystyle l>k}definiri(l)≤k{\displaystyle i(l)\leq k}el primer índice tal quew(l)+∑j=1i(l)w(j)>W{\displaystyle w(l)+\sum _ {j=1}^{i(l)}w(j)>W}Entonces sostiene que

OPAGT(I)≥máximo{h(l)+h(i(l))|l>k∧w(l)+∑j=1i(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α∈[1,W/2]∩norte{\displaystyle \alpha \in [1,W/2]\cap \mathbb {N} }y definirI1(α):={i∈I|w(i)>W−α}{\displaystyle {\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}}, I2(α):={i∈I|W−α≥w(i)>W/2}{\displaystyle {\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}}, yI3(α):={i∈I|W/2≥w(i)>α}{\displaystyle {\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}}Entonces sostiene que

OPAGT(I)≥máximoα∈[1,W/2]∩norte{∑i∈I1(α)∪I2(α)h(i)+(∑i∈I3(α)h(i)w(i)−∑i∈I2(α)(W−w(i))h(i)W)+}{\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 )}(Ww(i))h(i)}}{W}}\right)_{+}{\Bigg \}}}, [ 7 ] donde (incógnita)+:=máximo{incógnita,0}{\displaystyle (x)_{+}:=\max\{x,0\}}para cadaincógnita∈R{\displaystyle x\in \mathbb {R} }.

Por otro lado, Steinberg [ 8 ] ha demostrado que la altura de una solución óptima puede ser acotada superiormente por

OPAGT(I)≤2máximo{hmáximo(I),ARmiA(I)/W}.{\displaystyle OPT(I)\leq 2\max\{h_{\max }(I),\mathrm {ÁREA} ({\mathcal {I}})/W\}.}

Más precisamente, demostró que dado unW≥wmáximo(I){\displaystyle W\geq w_{\max }({\mathcal {I}})}y unH≥hmáximo(I){\displaystyle H\geq h_{\max }(I)}luego los artículosI{\displaystyle {\mathcal {I}}}se puede colocar dentro de una caja con anchoW{\displaystyle W}y alturaH{\displaystyle H}si

WH≥2ARmiA(I)+(2wmáximo(I)−W)+(2hmáximo(I)−H)+{\displaystyle WH\geq 2\mathrm {AREA} ({\mathcal {I}})+(2w_{\max }({\mathcal {I}})-W)_{+}(2h_{\max }(I)-H)_{+}}, dónde (incógnita)+:=máximo{incógnita,0}{\displaystyle (x)_{+}:=\max\{x,0\}}.

Algoritmos de aproximación en 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 razón de aproximación entre3{\displaystyle 3}y2{\displaystyle 2}. Encontrar un algoritmo con una relación inferior a2{\displaystyle 2}parece complicado, y la complejidad de los algoritmos correspondientes aumenta en cuanto a su tiempo de ejecución y sus descripciones. La menor relación de aproximación alcanzada hasta ahora es(5/3+ε){\displaystyle (5/3+\varepsilon )}.

Alineación izquierda ascendente (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:

DejarL{\displaystyle L}sea ​​una secuencia de elementos rectangulares. El algoritmo itera la secuencia en el orden dado. Para cada elemento considerador∈L{\displaystyle r\in L}, busca la posición más baja para colocarlo y luego lo desplaza lo más a la izquierda posible. Por lo tanto, lo colocar{\displaystyle r}en la coordenada más baja posible más a la izquierda(incógnita,y){\displaystyle (x,y)}en la tira.

Este algoritmo tiene las siguientes propiedades:

  • La razón de aproximación de este algoritmo no puede ser limitada por una constante. Más precisamente, demostraron que para cadaMETRO>0{\displaystyle M>0}existe una listaL{\displaystyle L} de elementos rectangulares ordenados por ancho creciente de tal manera queBL(L)/OPAGT(L)>METRO{\displaystyle BL(L)/OPT(L)>M}, dóndeBL(L){\displaystyle BL(L)}es la altura del empaque creado por el algoritmo BL yOPAGT(L){\displaystyle OPT(L)}es la altura de la solución óptima paraL{\displaystyle L}. [ 2 ]
  • Si los elementos están ordenados por anchos decrecientes, entoncesBL(L)/OPAGT(L)≤3{\displaystyle BL(L)/OPT(L)\leq 3}. [ 2 ]
  • Si todos los elementos son cuadrados y están ordenados por anchos decrecientes, entoncesBL(L)/OPAGT(L)≤2{\displaystyle BL(L)/OPT(L)\leq 2}. [ 2 ]
  • Para cualquierδ>0{\displaystyle \delta >0}, existe una listaL{\displaystyle L}de rectángulos ordenados por anchos decrecientes de tal manera queBL(L)/OPAGT(L)>3−δ{\displaystyle BL(L)/OPT(L)>3-\delta }. [ 2 ]
  • Para cualquierδ>0{\displaystyle \delta >0}, existe una listaL{\displaystyle L}de cuadrados ordenados por anchos decrecientes de tal manera queBL(L)/OPAGT(L)>2−δ{\displaystyle BL(L)/OPT(L)>2-\delta }. [ 2 ]
  • Para cadaε∈(0,1]{\displaystyle \varepsilon \in (0,1]}, existe una instancia que contiene solo cuadrados donde cada orden de los cuadradosL{\displaystyle L}tiene una proporción deBL(L)/OPAGT(L)>1211+ε{\displaystyle BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}}, es decir, existen casos en los que 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 paraBL(L)/OPAGT(L)>43+ε{\displaystyle BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}}. [ 19 ]
  • En 2025, Hougardy y Zondervan construyeron un ordenamiento de rectángulos (llamado elFQW{\displaystyle {\mathcal {FQW}}}-ordenación), de tal manera queBL(L)/OPAGT(L)≤136{\displaystyle BL(L)/OPT(L)\leq {\frac {13}{6}}}. [ 20 ]

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:

DejarI{\displaystyle {\mathcal {I}}}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(0,0){\displaystyle (0,0)}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 ese momento, 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.

Este algoritmo tiene las siguientes propiedades:

  • El tiempo de ejecución puede estar limitado porO(|I|registro⁡(|I|)){\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}y si los elementos ya están ordenados incluso porO(|I|){\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}.
  • Para cada conjunto de artículosI{\displaystyle {\mathcal {I}}}, produce un empaque de alturanorteFDH(I)≤2OPAGT(I)+hmáximo≤3OPAGT(I){\displaystyle NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}, dóndehmáximo{\displaystyle h_{\max }}es la altura máxima de un elemento enI{\displaystyle {\mathcal {I}}}. [ 9 ]
  • Por cadaε>0{\displaystyle \varepsilon >0}Existe un conjunto de rectángulosI{\displaystyle {\mathcal {I}}}de tal manera quenorteFDH(I|)>(2−ε)OPAGT(I).{\displaystyle NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).}[ 9 ]
  • El empaquetado resultante es de tipo guillotina. Esto significa que los artículos se obtienen mediante una secuencia de cortes horizontales o verticales de borde a borde.

Ajuste inicial con altura decreciente (FFDH)

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

Este algoritmo tiene las siguientes propiedades:

  • El tiempo de ejecución puede estar limitado porO(|I|2){\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}, ya que hay como máximo|I|{\displaystyle |{\mathcal {I}}|}niveles.
  • Para cada conjunto de artículosI{\displaystyle {\mathcal {I}}}produce un empaque de alturaFFDH(I)≤1.7OPAGT(I)+hmáximo≤2.7OPAGT(I){\displaystyle FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})}, dóndehmáximo{\displaystyle h_{\max }}es la altura máxima de un elemento enI{\displaystyle {\mathcal {I}}}. [ 9 ]
  • Dejarmetro≥2{\displaystyle m\geq 2}. Para cualquier conjunto de artículosI{\displaystyle {\mathcal {I}}}y tira con anchoW{\displaystyle W}de tal manera quew(i)≤W/metro{\displaystyle w(i)\leq W/m}para cadai∈I{\displaystyle i\in {\mathcal {I}}}, sostiene queFFDH(I)≤(1+1/metro)OPAGT(I)+hmáximo{\displaystyle FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }}. Además, para cadaε>0{\displaystyle \varepsilon >0}, existe tal conjunto de elementosI{\displaystyle {\mathcal {I}}} con FFDH(I)>(1+1/metro−ε)OPAGT(I){\displaystyle FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})}. [ 9 ]
  • Si todos los artículos enI{\displaystyle {\mathcal {I}}}son cuadrados, sostiene queFFDH(I)≤(3/2)OPAGT(I)+hmáximo{\displaystyle FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }}. Además, para cadaε>0{\displaystyle \varepsilon >0}, existe un conjunto de cuadradosI{\displaystyle {\mathcal {I}}} de tal manera que FFDH(I)>(3/2−ε)OPAGT(I){\displaystyle FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})}. [ 9 ]
  • El empaquetado resultante es de tipo guillotina. Esto significa que los artículos se obtienen 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 elementosI{\displaystyle {\mathcal {I}}}y tira con anchoW{\displaystyle W}Funciona de la siguiente manera:

  1. Determinadometro∈norte{\displaystyle m\in \mathbb {N} }, el mayor entero tal que los rectángulos dados tengan anchoW/metro{\displaystyle W/m}o menos.
  2. DividirI{\displaystyle {\mathcal {I}}}en dos conjuntosIwidmi{\displaystyle {\mathcal {I}}_{wide}}yInortearrow{\displaystyle {\mathcal {I}}_{narrow}}, de tal manera queIwidmi{\displaystyle {\mathcal {I}}_{wide}}contiene todos los artículosi∈I{\displaystyle i\in {\mathcal {I}}}con un anchow(i)>W/(metro+1){\displaystyle w(i)>W/(m+1)}mientrasInortearrow{\displaystyle {\mathcal {I}}_{narrow}}contiene todos los artículos conw(i)≤W/(metro+1){\displaystyle w(i)\leq W/(m+1)}.
  3. OrdenIwidmi{\displaystyle {\mathcal {I}}_{wide}}yInortearrow{\displaystyle {\mathcal {I}}_{narrow}}por altura no creciente.
  4. Empaque los artículos enIwidmi{\displaystyle {\mathcal {I}}_{wide}}con el algoritmo FFDH.
  5. Reordenar los niveles/estantes construidos por FFDH de manera que todos los estantes con un ancho total mayor queW(metro+1)/(metro+2){\displaystyle W(m+1)/(m+2)}están debajo de los más estrechos.
  6. Esto deja un área rectangularR{\displaystyle R}de conW/(metro+2){\displaystyle W/(m+2)}, junto a niveles/estantes más estrechos, que no contiene ningún artículo.
  7. Utilice el algoritmo FFDH para empacar los artículos enInortearrow{\displaystyle {\mathcal {I}}_{narrow}}utilizando el áreaR{\displaystyle R}también.

Este algoritmo tiene las siguientes propiedades:

  • Para cada conjunto de artículosI{\displaystyle {\mathcal {I}}}y el correspondientemetro{\displaystyle m}, sostiene queSF(I)≤(metro+2)/(metro+1)OPAGT(I)+2hmáximo{\displaystyle SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }}. [ 9 ] Tenga en cuenta que parametro=1{\displaystyle m=1}, sostiene queSF(I)≤(3/2)OPAGT(I)+2hmáximo{\displaystyle SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }}
  • Para cadaε>0{\displaystyle \varepsilon >0}, hay un conjunto de artículosI{\displaystyle {\mathcal {I}}} de tal manera que SF(I)>((metro+2)/(metro+1)−ε)OPAGT(I){\displaystyle SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})}. [ 9 ]

El algoritmo de Sleator

Para un conjunto dado de elementosI{\displaystyle {\mathcal {I}}}y tira con anchoW{\displaystyle W}Funciona de la siguiente manera:

  1. Encuentra todos los artículos con un ancho mayor queW/2{\displaystyle W/2}y apílalos en la parte inferior de la tira (en orden aleatorio). Llama a la altura total de estos elementosh0{\displaystyle h_{0}}Todos los demás elementos se colocarán arriba.h0{\displaystyle h_{0}}.
  2. Ordena todos los elementos restantes en orden descendente según su altura. Los elementos se colocarán en este orden.
  3. Considere la línea horizontal enh0{\displaystyle h_{0}}como un estante. El algoritmo coloca los elementos en este estante en orden descendente de altura hasta que no quede ningún elemento o el siguiente no quepa.
  4. Dibuja una línea vertical enW/2{\displaystyle W/2}, que corta la tira en dos mitades iguales.
  5. Dejarhl{\displaystyle h_{l}}ser el punto más alto cubierto por cualquier elemento en la mitad izquierda yhr{\displaystyle h_{r}}el punto correspondiente en la mitad derecha. Dibuja dos segmentos de línea horizontales de longitudW/2{\displaystyle W/2}enhl{\displaystyle h_{l}}yhr{\displaystyle h_{r}}A lo largo de la mitad izquierda y derecha de la tira. Estas dos líneas crean nuevos estantes donde el algoritmo colocará los elementos, como en el paso 3. Elija la mitad que tenga el estante inferior y coloque los elementos en este estante hasta que no quepa ninguno más. Repita este paso hasta que no quede ningún elemento.

Este algoritmo tiene las siguientes propiedades:

  • El tiempo de ejecución puede estar limitado porO(|I|registro⁡(|I|)){\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}y si los elementos ya están ordenados incluso porO(|I|){\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}.
  • Para cada conjunto de artículosI{\displaystyle {\mathcal {I}}}produce un empaque de alturaA(I)≤2OPAGT(I)+hmáximo/2≤2.5OPAGT(I){\displaystyle A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})}, dóndehmáximo{\displaystyle h_{\max }}es la altura máxima de un elemento enI{\displaystyle {\mathcal {I}}}. [ 10 ]

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.i{\displaystyle i}uno al lado del otro de un elemento ya colocadoj{\displaystyle j}En este caso, divide la subtira correspondiente en dos partes: una que contiene el primer elemento.j{\displaystyle j}y el otro que contiene el elemento actuali{\displaystyle i}. Si esto no es posible, colocai{\displaystyle i}sobre un elemento ya colocado y no divide la subfranja.

Este algoritmo crea un conjuntoSde subtiras. Para cada subtiras ∈ SSabemos que es su esquina inferior izquierda.s.xposiciónys.yposiciónsu anchoancho s, las líneas horizontales paralelas al borde superior e inferior del elemento colocado en último lugar dentro de esta subfranjacenayMás lento, así como su anchuras.itemWidth.

La función Algoritmo de división (SP) es la entrada: elementos I, ancho de la tiraWSalida: Un paquete de los artículos Ordenar I en orden no creciente de anchos; Definir una lista vacía S de subbandas; Defina una nueva subbanda s con s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W; Sumar s a S; Mientras I no esté vacío, ¿puedo hacer 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, 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. Coloca i en la posición (s.xposition, s.upper); 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 al mismo nivel y divida la subtira correspondiente en esta posición. Encuentra s ∈ S_2 con el s más pequeño.lower; Coloca i en la posición (s.xposition + s.itemWidth, s.lower); Quitar la s de S; Defina dos nuevas subbandas 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.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 puede estar limitado porO(|I|2){\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}ya que el número de subbandas está limitado por|I|{\displaystyle |{\mathcal {I}}|}.
  • Para cualquier conjunto de artículosI{\displaystyle {\mathcal {I}}}sostiene queSPAG(I)≤2OPAGT(I)+hmáximo≤3OPAGT(I){\displaystyle SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}. [ 11 ]
  • Para cualquierε>0{\displaystyle \varepsilon >0}, existe un conjunto de elementosI{\displaystyle {\mathcal {I}}}de tal manera queSPAG(I)>(3−ε)OPAGT(I){\displaystyle SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})}. [ 11 ]
  • Para cualquierε>0{\displaystyle \varepsilon >0}ydo>0{\displaystyle C>0}, existe un conjunto de elementosI{\displaystyle {\mathcal {I}}}de tal manera queSPAG(I)>(2−ε)OPAGT(I)+do{\displaystyle SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C}. [ 11 ]

Ajuste inverso (RF)

Este algoritmo fue descrito por primera vez por Schiermeyer. [ 13 ] La descripción de este algoritmo requiere alguna notación adicional. Para un elemento colocadoi∈I{\displaystyle i\in {\mathcal {I}}}, su esquina inferior izquierda está denotada por(ai,doi){\displaystyle (a_{i},c_{i})}y su esquina superior derecha por(bi,di){\displaystyle (b_{i},d_{i})}.

Dado un conjunto de elementosI{\displaystyle {\mathcal {I}}}y una franja de anchoW{\displaystyle W}Funciona de la siguiente manera:

  1. Apila todos los rectángulos de ancho mayor queW/2{\displaystyle W/2}uno encima del otro (en orden aleatorio) en la parte inferior de la tira. Denotemos porH0{\displaystyle H_{0}}la altura de esta pila. Todos los demás artículos se empaquetarán encima.H0{\displaystyle H_{0}}.
  2. Ordena los elementos restantes en orden descendente de altura y considera los elementos en este orden en los siguientes pasos.hmáximo{\displaystyle h_{\max }}sea ​​la altura del más alto de estos elementos restantes.
  3. Coloque los artículos uno por uno alineados a la izquierda en un estante definido porH0{\displaystyle H_{0}}hasta que no quepa ningún otro artículo en este estante o no quede ningún artículo. Llama a este estante el primer nivel .
  4. Dejarh1{\displaystyle h_{1}}sea ​​la altura del artículo desempaquetado más alto. Defina un nuevo estante enH0+hmáximo+h1{\displaystyle H_{0}+h_{\max }+h_{1}}. El algoritmo llenará este estante de derecha a izquierda, alineando los elementos a la derecha, de manera que los elementos toquen este estante con su parte superior. Llamemos a este estante el segundo nivel inverso .
  5. Coloca los artículos en los dos estantes según el principio de "Primer ajuste", es decir, coloca los artículos en el primer nivel donde quepan y en el segundo en caso contrario. Continúa hasta que no queden artículos o el ancho total de los artículos en el segundo estante sea al menosW/2{\displaystyle W/2}.
  6. Desplaza el segundo nivel inverso hacia abajo hasta que un elemento de este toque un elemento del primer nivel. DefinirH1{\displaystyle H_{1}}como la nueva posición vertical del estante desplazado. DejeF{\displaystyle f}ys{\displaystyle s}ser el par de objetos más adecuados para tocar conF{\displaystyle f}colocado en el primer nivel ys{\displaystyle s}en el segundo nivel inverso. Definirincógnitar:=máximo(bF,bs){\displaystyle x_{r}:=\max(b_{f},b_{s})}.
  7. Siincógnitar<W/2{\displaystyle x_{r}<W/2}entoncess{\displaystyle s}es el último rectángulo colocado en el segundo nivel inverso. Desplaza todos los demás elementos de este nivel hacia abajo (todos 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.F′{\displaystyle f'}ys′{\displaystyle s'}. Definirh2{\displaystyle h_{2}}como la cantidad en que se desplazó el estante hacia abajo.
    1. Sih2≤h(s){\displaystyle h_{2}\leq h(s)}luego cambias{\displaystyle s}hacia la izquierda hasta que toque otro elemento o el borde de la tira. Defina el tercer nivel en la parte superior des′{\displaystyle s'}.
    2. Sih2>h(s){\displaystyle h_{2}>h(s)}luego cambias{\displaystyle s}definir el tercer nivel en la parte superior des′{\displaystyle s'}. Lugars{\displaystyle s}Alineado a la izquierda en este tercer nivel, de manera que toca un elemento del primer nivel que se encuentra a su izquierda.
  8. Continúe colocando los artículos utilizando la heurística First-Fit. Cada nivel siguiente (a partir del nivel tres) se define mediante una línea horizontal que pasa por la parte superior del artículo más grande del nivel anterior. Tenga en cuenta que el primer artículo colocado en el siguiente nivel podría no tocar el borde de la tira con su lado izquierdo, pero un artículo del primer nivel o el artículos{\displaystyle s}.

Este algoritmo tiene las siguientes propiedades:

  • El tiempo de ejecución puede estar limitado porO(|I|2){\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}, ya que hay como máximo|I|{\displaystyle |{\mathcal {I}}|}niveles.
  • Para cada conjunto de artículosI{\displaystyle {\mathcal {I}}}produce un empaque de alturaRF(I)≤2OPAGT(I){\displaystyle RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})}. [ 13 ]

Algoritmo de Steinberg (ST)

El algoritmo de Steinberg es recursivo. Dado un conjunto de elementos rectangularesI{\displaystyle {\mathcal {I}}}y una región objetivo rectangular con anchoW{\displaystyle W}y alturaH{\displaystyle H}, 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 elementosI{\displaystyle {\mathcal {I}}}denotamos porhmáximo(I){\displaystyle h_{\max }({\mathcal {I}})}la altura del objeto más alto en I{\displaystyle {\mathcal {I}}},wmáximo(I){\displaystyle w_{\max }({\mathcal {I}})}el ancho de elemento más grande que aparece en I{\displaystyle {\mathcal {I}}}y porARmiA(I):=∑i∈Iw(i)h(i){\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)}el área total de estos elementos. Steinbergs muestra que si

hmáximo(I)≤H{\displaystyle h_{\max }({\mathcal {I}})\leq H},wmáximo(I)≤W{\displaystyle w_{\max }({\mathcal {I}})\leq W}, yARmiA(I)≤W⋅H−(2hmáximo(I)−h)+(2wmáximo(I)−W)+{\displaystyle \mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}}, dónde(a)+:=máximo{0,a}{\displaystyle (a)_{+}:=\max\{0,a\}},

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

Procedimiento 1 : Se puede aplicar siwmáximo(I′)≥W/2{\displaystyle w_{\max }({\mathcal {I}}')\geq W/2}.

  1. Encuentra todos los artículosi∈I{\displaystyle i\in {\mathcal {I}}}con anchow(i)≥W/2{\displaystyle w(i)\geq W/2}y eliminarlos deI{\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 objetivo.h0{\displaystyle h_{0}}sea ​​su altura total.
  3. Encuentra todos los artículosi∈I{\displaystyle i\in {\mathcal {I}}}con anchoh(i)>H−h0{\displaystyle h(i)>H-h_{0}}. Retíralos deI{\displaystyle {\mathcal {I}}}y colóquelos en un nuevo conjuntoIH{\displaystyle {\mathcal {I}}_{H}}.
  4. SiIH{\displaystyle {\mathcal {I}}_{H}}está vacío, defina la nueva región objetivo como el área superiorh0{\displaystyle h_{0}}, es decir, tiene alturaH−h0{\displaystyle H-h_{0}}y anchoW{\displaystyle W}. Resuelva el problema que consiste en esta nueva región objetivo y el conjunto reducido de elementos con uno de los procedimientos.
  5. SiIH{\displaystyle {\mathcal {I}}_{H}}No está vacío, ordénelo por altura no creciente y coloque los elementos alineados correctamente uno por uno en la esquina superior derecha del área objetivo.w0{\displaystyle w_{0}}sea ​​el ancho total de estos elementos. Defina una nueva área objetivo con anchoW−w0{\displaystyle W-w_{0}}y alturaH−h0{\displaystyle H-h_{0}}en la esquina superior izquierda. Resuelva el problema que consta de esta nueva región objetivo y el conjunto reducido de elementos con uno de los procedimientos.

Procedimiento 2 : Se puede aplicar si se cumplen las siguientes condiciones:wmáximo(I)≤W/2{\displaystyle w_{\max }({\mathcal {I}})\leq W/2},hmáximo(I)≤H/2{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}y existen dos elementos diferentesi,i′∈I{\displaystyle i,i'\in {\mathcal {I}}}conw(i)≥W/4{\displaystyle w(i)\geq W/4},w(i′)≥W/4{\displaystyle w(i')\geq W/4},h(i)≥H/4{\displaystyle h(i)\geq H/4},h(i′)≥H/4{\displaystyle h(i')\geq H/4}y2(ARmiA(I)−w(i)h(i)−w(i′)h(i′))≤(W−máximo{w(i),w(i′)})H{\displaystyle 2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H}.

  1. Encontrari{\displaystyle i}yi′{\displaystyle i'}y eliminarlos deI{\displaystyle {\mathcal {I}}}.
  2. Coloca 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 estos dos elementos, de manera que tenga el anchoW−máximo{w(i),w(i′)}{\displaystyle W-\max\{w(i),w(i')\}}y alturaH{\displaystyle H}.
  4. Coloque los artículos restantes enI{\displaystyle {\mathcal {I}}}en la nueva zona objetivo utilizando uno de los procedimientos.

Procedimiento 3 : Se puede aplicar si se cumplen las siguientes condiciones:wmáximo(I)≤W/2{\displaystyle w_{\max }({\mathcal {I}})\leq W/2},hmáximo(I)≤H/2{\displaystyle h_{\max }({\mathcal {I}})\leq H/2},|I|>1{\displaystyle |{\mathcal {I}}|>1}y al ordenar los elementos por ancho decreciente existe un índicemetro{\displaystyle m}de tal manera que al definirI′{\displaystyle {\mathcal {I'}}}como el primerometro{\displaystyle m}artículos que contiene que ARmiA(I)−WH/4≤ARmiA(I′)≤3WH/8{\displaystyle \mathrm {AREA} ({\mathcal {I}})-WH/4\leq \mathrm {AREA} ({\mathcal {I'}})\leq 3WH/8}así comow(imetro+1)≤W/4{\displaystyle w(i_{m+1})\leq W/4}

  1. ColocarW1:=máximoW/2,2ARmiA(I′)/H{\displaystyle W_{1}:=\max {W/2,2\mathrm {AREA} ({\mathcal {I'}})/H}}.
  2. Defina dos nuevas áreas objetivo rectangulares, una en la esquina inferior izquierda de la original con alturaH{\displaystyle H}y anchoW1{\displaystyle W_{1}}y el otro a su izquierda con alturaH{\displaystyle H}y anchoW−W1{\displaystyle W-W_{1}}.
  3. Utilice uno de los procedimientos para colocar los elementos enI′{\displaystyle {\mathcal {I'}}}en la primera nueva área objetivo y los elementos enI∖I′{\displaystyle {\mathcal {I}}\setminus {\mathcal {I'}}}en el segundo.

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

Procedimiento 4 : Se puede aplicar si se cumplen las siguientes condiciones:wmáximo(I)≤W/2{\displaystyle w_{\max }({\mathcal {I}})\leq W/2},hmáximo(I)≤H/2{\displaystyle h_{\max }({\mathcal {I}})\leq H/2}y existe un artículoi∈I{\displaystyle i\in {\mathcal {I}}}de tal manera quew(i)h(i)≥ARmiA(I)−WH/4{\displaystyle w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4}.

  1. Coloca el artículoi{\displaystyle i}en la esquina inferior izquierda del área objetivo y retírela deI{\displaystyle {\mathcal {I}}}.
  2. Defina una nueva área objetivo a la derecha de este elemento de manera que tenga el anchoW−w(i){\displaystyle W-w(i)}y alturaH{\displaystyle H}y coloque los elementos restantes dentro de esta área utilizando uno de los procedimientos.

Este algoritmo tiene las siguientes propiedades:

  • El tiempo de ejecución puede estar limitado porO(|I|registro⁡(|I|)2/registro⁡(registro⁡(|I|))){\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))}. [ 8 ]
  • Para cada conjunto de artículosI{\displaystyle {\mathcal {I}}}produce un empaque de alturaST(I)≤2OPAGT(I){\displaystyle ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})}. [ 8 ]

Algoritmos de aproximación de tiempo pseudopolinomial

Para mejorar el límite inferior de3/2{\displaystyle 3/2}Para algoritmos de tiempo polinomial, se han considerado algoritmos de tiempo pseudopolinomial para el problema de empaquetamiento de tiras. Al considerar este tipo de algoritmos, todos los tamaños de los elementos y de la tira se dan como integrales. Además, el ancho de la tiraW{\displaystyle W}Se permite que 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 deregistro⁡(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 puede simplificarse y transformarse en una que tiene una de un número constante de estructuras. El algoritmo luego itera todas estas estructuras y coloca los elementos dentro utilizando programación lineal y dinámica . La mejor proporción lograda hasta ahora es(5/4+ε)OPAGT(I){\displaystyle (5/4+\varepsilon )OPT(I)}. [ 21 ] mientras que no puede haber un algoritmo de tiempo pseudopolinomial con una relación mejor que5/4{\displaystyle 5/4}a menos quePAG=nortePAG{\displaystyle P=NP}[ 5 ]

Algoritmos en línea

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

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

stúpagIA(I)/OPAGT(I){\displaystyle \mathrm {sup} _{I}A(I)/OPT(I)},

dóndeA(I){\displaystyle A(I)}corresponde a la solución generada por el algoritmo en línea yOPAGT(I){\displaystyle OPT(I)}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. Por ejemploI{\displaystyle I}conhmáximo(I)≤1{\displaystyle h_{\max }(I)\leq 1}se define como

límitestúpagOPAGT(I)→∞A(I)/OPAGT(I){\displaystyle \lim \mathrm {sup} _{OPT(I)\rightarrow \infty }A(I)/OPT(I)}.

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

El marco de Han et al. [ 30 ] es aplicable en el entorno 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 empaquetamiento de contenedores en línea Harmonic++ de Seiden [ 31 ] implica un algoritmo para el empaquetamiento 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 empaquetado". European Journal of Operational Research . 183 (3): 1109– 1130. doi : 10.1016/j.ejor.2005.12.047 . ISSN 0377-2217 . 
  2. 1 2 3 4 5 6 7 8 9 10 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. 1 2 Harren, Rolf; Jansen, Klaus; Prädel, Lars; van Stee, Rob (febrero de 2014). "Una aproximación (5/3 + épsilon) para el empaquetamiento de tiras" . Geometría Computacional . 47 (2): 248– 267. doi : 10.1016/j.comgeo.2013.08.008 .
  4. ↑ Neuenfeldt Junior, Álvaro Luiz. "El problema del empaquetamiento de tiras rectangulares bidimensionales" (PDF) . 10820228.
  5. 1 2 Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (2019). "Resultados de complejidad e inaproximabilidad para la planificación de tareas paralelas y el empaquetamiento de franjas". Theory of Computing Systems . 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 en tiras y el empaquetamiento de volumen mínimo" . Theoretical Computer Science . 661 : 56–64 . doi : 10.1016/j.tcs.2016.11.034 .
  7. 1 2 3 Martello, Silvano; Monaci, Michele; Vigo, Daniele (1 de agosto de 2003). "Un enfoque exacto al problema del empaquetamiento de tiras". INFORMS Journal on Computing . 15 (3): 310– 319. doi : 10.1287/ijoc.15.3.310.16082 . ISSN 1091-9856 . 
  8. 1 2 3 4 Steinberg, A. (marzo de 1997). "Un algoritmo de empaquetamiento de tiras con límite de rendimiento absoluto 2". SIAM Journal on Computing . 26 (2): 401– 409. doi : 10.1137/S0097539793255801 .
  9. 1 2 3 4 5 6 7 8 9 10 11 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. 1 2 Sleator, Daniel Dominic (1980). "Un algoritmo 2,5 veces óptimo para el empaquetado en dos dimensiones". Inf. Process. Lett . 10 : 37–40 . doi : 10.1016/0020-0190(80)90121-0 .
  11. 1 2 3 4 5 Golan, Igal (agosto de 1981). "Límites de rendimiento para algoritmos de empaquetamiento bidimensional orientados ortogonalmente". SIAM Journal on Computing . 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 el empaquetamiento bidimensional". Journal of Algorithms . 2 (4): 348– 368. doi : 10.1016/0196-6774(81)90034-1 .
  13. 1 2 3 Schiermeyer, Ingo (1994). "Reverse-Fit: Un algoritmo 2-óptimo para el empaquetado de rectángulos". Algorithms — ESA '94 . Lecture Notes in Computer Science. Vol. 855. Springer Berlin Heidelberg. pp. 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 a un problema de corte de material bidimensional". Mathematics of Operations Research . 25 (4): 645– 656. doi : 10.1287/moor.25.4.645.12118 . S2CID 5361969 . 
  15. ↑ Harren, Rolf; van Stee, Rob (2009). "Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems". Aproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques . Lecture Notes in Computer Science. Vol. 5687. pp. 177–189 . Bibcode : 2009LNCS.5687..177H . doi : 10.1007/978-3-642-03685-9_14 . ISBN   978-3-642-03684-2.
  16. ↑ Jansen, Klaus; Solis-Oba, Roberto (agosto de 2009). "Empaquetamiento de rectángulos con aumento de recursos unidimensionales". 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 el empaquetado de múltiples franjas y la 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 tiras de 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 de la parte inferior izquierda para el problema de empaquetamiento de tiras , arXiv : 2402.16572
  20. ↑ Hougardy, Stefan; Zondervan, Bart (2026). "Una aproximación 13/6 para el empaquetamiento de tiras mediante el algoritmo inferior izquierdo". 43.º Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2026) . Actas Internacionales Leibniz en Informática (LIPIcs). Vol. 364. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 54:1–54:17. doi : 10.4230/LIPIcs.STACS.2026.54 .  
  21. ^ 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 . 
  22. ↑ Jansen, Klaus; Thöle, Ralf (enero de 2010). "Algoritmos de aproximación para la planificación de trabajos paralelos". SIAM Journal on Computing . 39 (8): 3571– 3615. doi : 10.1137/080736491 .
  23. ↑ Nadiradze, Giorgi; Wiese, Andreas (21 de diciembre de 2015). «Sobre la aproximación del empaquetamiento 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áticas Industriales y Aplicadas. págs. 1491–1510 . doi : 10.1137/1.9781611974331.ch102 . ISBN  978-1-61197-433-1.
  24. ^ 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 . 
  25. ↑ Jansen, Klaus; Rau, Malin (29–31 de marzo de 2017). «Aproximación mejorada para el empaquetamiento de tiras bidimensional con ancho acotado polinomial». WALCOM: Algoritmos y computación . Notas de clase en ciencias de la computación. 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 . 
  26. ↑Baker, Brenda S.; Schwarz, Jerald S. (1 August 1983). "Shelf Algorithms for Two-Dimensional Packing Problems". SIAM Journal on Computing. 12 (3): 508–525. doi:10.1137/0212033. ISSN 0097-5397.
  27. ↑Csirik, János; Woeginger, Gerhard J. (28 August 1997). "Shelf algorithms for on-line strip packing". Information Processing Letters. 63 (4): 171–175. doi:10.1016/S0020-0190(97)00120-8. ISSN 0020-0190.
  28. ↑Hurink, Johann L.; Paulus, Jacob Jan (2007). "Online Algorithm for Parallel Job Scheduling and Strip Packing"(PDF). Approximation and Online Algorithms. Lecture Notes in Computer Science. Vol. 4927. Springer Berlin Heidelberg. pp. 67–74. doi:10.1007/978-3-540-77918-6_6. ISBN 978-3-540-77917-9.
  29. ↑Ye, Deshi; Han, Xin; Zhang, Guochuan (1 May 2009). "A note on online strip packing". Journal of Combinatorial Optimization. 17 (4): 417–423. doi:10.1007/s10878-007-9125-x. ISSN 1573-2886. S2CID 37635252.
  30. 12Han, Xin; Iwama, Kazuo; Ye, Deshi; Zhang, Guochuan (2007). "Strip Packing vs. Bin Packing". Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science. Vol. 4508. Springer Berlin Heidelberg. pp. 358–367. arXiv:cs/0607046. doi:10.1007/978-3-540-72870-2_34. ISBN 978-3-540-72868-9. S2CID 580.
  31. 12Seiden, Steven S. (2001). "On the Online Bin Packing Problem". Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 2076. Springer Berlin Heidelberg. pp. 237–248. doi:10.1007/3-540-48224-5_20. ISBN 978-3-540-42287-7.
  32. ↑ 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 .  
  33. ↑ Johannes, Berit (1 de octubre de 2006). "Programación de trabajos paralelos para minimizar el tiempo de finalizació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 .  
  34. ↑ 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 .  
  35. ↑ Kern, Walter; Paulus, Jacob Jan (2009). "Una nota sobre el límite inferior para el empaquetamiento de tiras en línea" . Operations Research Letters .
  36. ^ 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 empaquetado de contenedores" . Informática Teórica . 440– 441: 1– 13. doi : 10.1016/j.tcs.2012.04.017 . ISSN 0304-3975 . 
  37. ↑ Yu, Guosong; Mao, Yanling; Xiao, Jiaoliao (1 de mayo de 2016). "Un nuevo límite inferior para el empaquetado en tiras en línea". European Journal of Operational Research . 250 (3): 754– 759. doi : 10.1016/j.ejor.2015.10.012 . ISSN 0377-2217 . 
Lecturas relacionadas
6 articulos
{\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}Tiempo pseudopolinomialEn la teoría de la complejidad computacional , un algoritmo numérico se ejecuta en tiempo pseudopolinomial si su tiempo de ejecución está acotado s...{\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }Complejidad parametrizadaEn informática , la complejidad parametrizada es una rama de la teoría de la complejidad computacional que se centra en la clasificación de los pro...EnteroLos números enteros dispuestos en una línea numérica Un número entero es el número cero ( 0 ), un número natural positivo (1, 2, 3, . . .), o la ne...Corte con guillotinaCorte con guillotinaEl corte con guillotina es el proceso de producir pequeños elementos rectangulares de dimensiones fijas a partir de una hoja rectangular grande det...{\displaystyle I}Problema de embalaje del contenedorEl problema del empaquetamiento de contenedores [1] [2] [3] [4] es un problema de optimización en el que se deben empaquetar elementos de diferente...Algoritmo de aproximaciónEn informática e investigación de operaciones , los algoritmos de aproximación son algoritmos eficientes que encuentran soluciones aproximadas a pr...