Problém s balením pásky - Strip packing problem

The problém s balením pásků je problém s 2-dimenzionální geometrickou minimalizací. Vzhledem k sadě osově zarovnaných obdélníků a pásu ohraničené šířky a nekonečné výšky určete balení nepřekrývajících se obdélníků do pásu minimalizující jeho výšku. Tento problém je problémem při řezání a balení a je klasifikován jako Problém s otevřenou dimenzí podle Wäscher et al.^[1]

Tento problém vzniká v oblasti plánování, kde modeluje úlohy, které vyžadují souvislou část paměti v daném časovém období. Dalším příkladem je oblast průmyslové výroby, kde je třeba vyříznout obdélníkové kusy z listu materiálu (např. Látky nebo papíru), který má pevnou šířku, ale nekonečnou délku, a je třeba minimalizovat zbytečný materiál.

Tento problém byl poprvé studován v roce 1980.^[2] Je silně NP tvrdý a neexistuje žádný algoritmus aproximace polynomiálního času s poměrem menším než ${ displaystyle 3/2}$ pokud ${ displaystyle P = NP}$ . Dosud nejlepší dosažený poměr aproximace (pomocí polynomiálního časového algoritmu Harren et al.^[3]) je ${ displaystyle (5/3 + varepsilon)}$ , což vyvolává otevřenou otázku, zda existuje algoritmus s aproximačním poměrem ${ displaystyle 3/2}$ .

Definice

Instance ${ displaystyle I = ({ mathcal {I}}, W)}$ z problém s balením pásků sestává z pruhu o šířce ${ displaystyle W = 1}$ a nekonečná výška, stejně jako sada ${ displaystyle { mathcal {I}}}$ obdélníkových předmětů. Každý předmět ${ displaystyle i in { mathcal {I}}}$ má šířku ${ displaystyle w_ {i} v (0,1] cap mathbb {Q}}$ a výška ${ displaystyle h_ {i} v (0,1] cap mathbb {Q}}$ Balení položek je mapování, které mapuje každý levý dolní roh položky ${ displaystyle i in { mathcal {I}}}$ do polohy ${ displaystyle (x_ {i}, y_ {i}) in ([0,1-w_ {i}] cap mathbb {Q}) times mathbb {Q} _ { geq 0}}$ uvnitř proužku. Vnitřní bod umístěné položky ${ displaystyle i in { mathcal {I}}}$ je bod ze sady ${ displaystyle mathrm {hostinec} (i) = {(x, y) v mathbb {Q} krát mathbb {Q} | x_ {i}$ Dvě (umístěné) položky se překrývají, pokud sdílejí vnitřní bod. Výška balení je definována jako ${ displaystyle max {y_ {i} + h_ {i} | i in { mathcal {I}} }}$ . Cílem je najít nepřekrývající se balení předmětů uvnitř proužku při minimalizaci výšky obalu.

Tato definice se používá pro všechny polynomiální časové algoritmy. Pro pseudo-polynomiální čas a FPT -algoritmy, definice je mírně změněna pro zjednodušení zápisu. V tomto případě jsou všechny zobrazené velikosti nedílnou součástí. Zejména šířka pásu je dána libovolným celým číslem větším než 1. Všimněte si, že tyto dvě definice jsou ekvivalentní.

Varianty

Bylo studováno několik variant problému s balením pásů. Tyto varianty se týkají geometrie objektů, dimenze problému, pokud je povoleno otáčet položkami, a struktury obalu.^[4]

Geometrie položek: Ve standardní variantě tohoto problému sestava daných položek sestává z obdélníků. V často uvažovaném subkase musí být všechny položky čtverce. Tato varianta byla zvažována již v prvním příspěvku o balení pásů.^[2]Dále byly studovány varianty, kde jsou tvary kruhové nebo dokonce nepravidelné. V druhém případě mluvíme o nepravidelné balení proužků.

Dimenze:Pokud není uvedeno jinak, problém s balením pásů je 2-rozměrný problém. Bylo však také studováno ve třech nebo dokonce více dimenzích. V tomto případě jsou to objekty hyperrektangle a pás je otevřený v jedné dimenzi a ohraničený ve zbývajících.

Otáčení: U klasického problému s balením pásů není povoleno otáčet předměty. Byly však studovány varianty, kde je povoleno otáčení o 90 stupňů nebo dokonce libovolný úhel.

Struktura balení:U obecného problému s balením pásu je struktura balení irelevantní. Existují však aplikace, které mají explicitní požadavky na strukturu obalu. Jedním z těchto požadavků je schopnost řezat předměty z pásu vodorovným nebo svislým řezem od okraje k okraji. Balení, která umožňují tento druh řezání, se nazývají gilotinové balení.

Tvrdost

Problém s balením proužků obsahuje problém s balením koše jako speciální případ, kdy všechny položky mají stejnou výšku 1. Z tohoto důvodu je silně NP-tvrdý a nemůže existovat žádný polynomiální čas aproximační algoritmus, který má přibližný poměr menší než ${ displaystyle 3/2}$ pokud ${ displaystyle P = NP}$ . Kromě toho, pokud ${ displaystyle P = NP}$ , nemůže existovat pseudo-polynomiální čas algoritmus, který má aproximační poměr menší než ${ displaystyle 5/4}$ ,^[5] což lze prokázat snížením z silně NP-kompletní Problém se 3 oddíly Pamatujte, že obě dolní meze ${ displaystyle 3/2}$ a ${ displaystyle 5/4}$ také platí pro případ, že je povoleno otáčení položek o 90 stupňů. Navíc to prokázali Ashok et al.^[6] to balení pásu je W [1] - tvrdý při parametrizaci výškou optimálního obalu.

Vlastnosti optimálních řešení

Optimální řešení mají dvě triviální dolní hranice. První je výška největší položky. Definovat ${ displaystyle h _ { max} (I): = max {h (i) | i in { mathcal {I}} }}$ . Pak to platí

${ displaystyle OPT (I) geq h _ { max} (I)}$ .

Další spodní mez je dána celkovou plochou položek. Definovat ${ displaystyle mathrm {AREA} ({ mathcal {I}}): = sum _ {i in { mathcal {I}}} h (i) w (i)}$ pak to platí

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

Následující dvě dolní hranice berou na vědomí skutečnost, že určité položky nelze v pásu umístit vedle sebe a lze je vypočítat v ${ displaystyle { mathcal {O}} (n log (n))}$ .^[7]U první dolní meze předpokládejme, že položky jsou seřazeny podle nezvětšující se výšky. Definovat ${ displaystyle k: = max {i: součet _ {j = 1} ^ {k} w (j) leq W }}$ . Pro každého ${ displaystyle l> k}$ definovat ${ Displaystyle i (l) leq k}$ první index takový, že ${ displaystyle w (l) + součet _ {j = 1} ^ {i (l)} w (j)> W}$ . Pak to platí

${ displaystyle OPT (I) geq max {h (l) + h (já (l)) | l> k klín w (l) + součet _ {j = 1} ^ {i (l) } w (j)> W }}$ .^[7]

U druhé dolní meze rozdělte sadu položek na tři sady. Nechat ${ displaystyle alpha in [1, W / 2] cap mathbb {N}}$ a definovat ${ displaystyle { mathcal {I}} _ {1} ( alfa): = {i v { mathcal {I}} | w (i)> W- alfa }}$ , ${ displaystyle { mathcal {I}} _ {2} ( alpha): = {i v { mathcal {I}} | W- alpha geq w (i)> W / 2 }}$ , a ${ displaystyle { mathcal {I}} _ {3} ( alpha): = {i v { mathcal {I}} | W / 2 geq w (i)> alpha }}$ . Pak to platí

${ 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}} vpravo) _ {+} { Bigg }}}$ ,^[7] kde ${ displaystyle (x) _ {+}: = max {x, 0 }}$ pro každého ${ displaystyle x in mathbb {R}}$ .

Na druhou stranu Steinberg^[8] ukázal, že výška optimálního řešení může být horní hranicí

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

Přesněji ukázal, že vzhledem k ${ displaystyle W geq w _ { max} ({ mathcal {I}})}$ a a ${ displaystyle H geq h _ { max} (I)}$ pak položky ${ displaystyle { mathcal {I}}}$ lze umístit do krabice o šířce ${ displaystyle W}$ a výška ${ displaystyle H}$ -li

${ displaystyle WH geq 2 mathrm {AREA} ({ mathcal {I}}) + (2w _ { max} ({ mathcal {I}}) - W) _ {+} (2h _ { max} (I) -H) _ {+}}$ , kde ${ displaystyle (x) _ {+}: = max {x, 0 }}$ .

Algoritmy polynomiální aproximace času

Jelikož je tento problém NP-těžký, aproximační algoritmy byly pro tento problém studovány. Většina heuristické přístupy mít přibližný poměr mezi ${ displaystyle 3}$ a ${ displaystyle 2}$ . Nalezení algoritmu s níže uvedeným poměrem ${ displaystyle 2}$ se zdá těžké a složitost odpovídajících algoritmů se zvyšuje, pokud jde o jejich dobu běhu a jejich popisy. Dosud dosažený nejmenší poměr přiblížení je ${ displaystyle (5/3 + varepsilon)}$ .

Přehled polynomiálních časových aproximací
Rok	název	Záruka aproximace	Zdroj
1980	Zdola nahoru, zarovnáno doleva (BL)	${ displaystyle 3OPT (I)}$	Baker a kol.^[2]
1980	Snížená výška Next-Fit (NFDH)	${ displaystyle 2OPT (I) + h _ { max} (I) leq 3OPT (I)}$	Coffman a kol.^[9]
	Snížení výšky prvního uložení (FFDH)	${ displaystyle 1.7OPT (I) + h _ { max} (I) leq 2.7OPT (I)}$
	Split-Fit (SF)	${ displaystyle 1.5OPT (I) + 2h _ { max} (I)}$
1980		${ displaystyle 2OPT (I) + h _ { max} (I) / 2 leq 2.5OPT (I)}$	Slaetor^[10]
1981	Split Algorithm (SP)	${ displaystyle 3OPT (I)}$	Golan^[11]
1981	Smíšený algoritmus	${ displaystyle (4/3) OPT (I) +7 { frac {1} {18}} h _ { max} (I)}$	Golan^[11]
1981	Nahoru-dolů (UD)	${ displaystyle (5/4) OPT (I) +6 { frac {7} {8}} h _ { max} (I)}$	Baker a kol.^[12]
1994	Reverse-Fit	${ displaystyle 2OPT (I)}$	Schiermeyer^[13]
1997		${ displaystyle 2OPT (I)}$	Steinberg^[8]
2000		${ displaystyle (1+ varepsilon) OPT (I) + { mathcal {O}} (1 / varepsilon ^ {2}) h _ { max} (I)}$	Kenyon, Rémila^[14]
2009		${ displaystyle 1.9396OPT (I)}$	Harren, van Stee^[15]
2009		${ displaystyle (1+ varepsilon) OPT (I) + h _ { max} (I)}$	Jansen, Solis-Oba^[16]
2011		${ displaystyle (1+ varepsilon) OPT (I) + { mathcal {O}} ( log (1 / varepsilon) / varepsilon) h _ { max} (I)}$	Bougeret a kol.^[17]
2012		${ displaystyle (1+ varepsilon) OPT (I) + { mathcal {O}} ( log (1 / varepsilon) / varepsilon) h _ { max} (I)}$	Sviridenko^[18]
2014		${ displaystyle (5/3 + varepsilon) OPT (I)}$	Harren a kol.^[3]

Zdola nahoru, zarovnáno doleva (BL)

Příklad řešení generovaných algoritmem Bottom-Up Left-Justified.

Tento algoritmus poprvé popsali Baker et al.^[2] Funguje to následovně:

Nechat ${ displaystyle L}$ být posloupností obdélníkových předmětů. Algoritmus iteruje sekvenci v daném pořadí. Pro každou uvažovanou položku ${ displaystyle r v L}$ , hledá nejspodnější pozici pro umístění a poté ji posune co nejvíce doleva. Proto to umisťuje ${ displaystyle r}$ v levé dolní nejvíce možné souřadnici ${ displaystyle (x, y)}$ v pásu.

Tento algoritmus má následující vlastnosti:

Aproximační poměr tohoto algoritmu nelze omezit konstantou. Přesněji to ukázali pro každého ${ displaystyle M> 0}$ existuje seznam ${ displaystyle L}$ obdélníkových položek seřazených zvětšením takové šířky ${ displaystyle BL (L) / OPT (L)> M}$ , kde ${ displaystyle BL (L)}$ je výška obalu vytvořeného algoritmem BL a ${ displaystyle OPT (L)}$ je výška optimálního řešení pro ${ displaystyle L}$ .^[2]
Pokud jsou položky seřazeny podle zmenšujících se šířek, pak ${ displaystyle BL (L) / OPT (L) leq 3}$ .^[2]
Pokud jsou položka všechny čtverce a jsou seřazeny podle zmenšujících se šířek, pak ${ displaystyle BL (L) / OPT (L) leq 2}$ .^[2]
Pro všechny ${ displaystyle delta> 0}$ , existuje seznam ${ displaystyle L}$ obdélníků seřazených podle zmenšení šířky tak, aby ${ displaystyle BL (L) / OPT (L)> 3- delta}$ .^[2]
Pro všechny ${ displaystyle delta> 0}$ , existuje seznam ${ displaystyle L}$ čtverců seřazených podle zmenšení šířky tak, že ${ displaystyle BL (L) / OPT (L)> 2- delta}$ .^[2]
Pro každého ${ displaystyle varepsilon v (0,1]}$ , existuje instance obsahující pouze čtverce, kde je každé pořadí čtverců ${ displaystyle L}$ má poměr ${ displaystyle BL (L) / OPT (L)> { frac {12} {11+ varepsilon}}}$ , tj. existují případy, kdy BL ano ne najít optimální i při iteraci všech možných objednávek položek.^[2]

Next-fit klesající výška (NFDH)

Příklad pro NFDH a FFDH aplikovaný na stejnou instanci

Tento algoritmus poprvé popsali Coffman et al.^[9] v roce 1980 a funguje takto:

Nechat ${ displaystyle { mathcal {I}}}$ být danou sadou obdélníkových předmětů. Nejprve algoritmus seřadí položky podle pořadí nezvyšující se výšky. Poté počínaje pozicí ${ displaystyle (0,0)}$ , algoritmus umístí položky vedle sebe do pruhu, dokud další položka nepřekryje pravý okraj pruhu. V tomto okamžiku algoritmus definuje novou úroveň v horní části nejvyšší položky v aktuální úrovni a umístí položky vedle sebe v této nové úrovni.

Tento algoritmus má následující vlastnosti:

Dobu chodu lze omezit ${ displaystyle { mathcal {O}} (| { mathcal {I}} | log (| { mathcal {I}} |))}$ a pokud jsou položky již seřazeny dokonce podle ${ displaystyle { mathcal {O}} (| { mathcal {I}} |)}$ .
Pro každou sadu položek ${ displaystyle { mathcal {I}}}$ , vytváří obal výšky ${ displaystyle NFDH ({ mathcal {I}}) leq 2OPT ({ mathcal {I}}) + h _ { max} leq 3OPT ({ mathcal {I}})}$ , kde ${ displaystyle h _ { max}}$ je největší výška položky v ${ displaystyle { mathcal {I}}}$ .^[9]
Pro každého ${ displaystyle varepsilon> 0}$ existuje sada obdélníků ${ displaystyle { mathcal {I}}}$ takhle ${ displaystyle NFDH ({ mathcal {I}} |)> (2- varepsilon) OPT ({ mathcal {I}}).}$ ^[9]
Balením je gilotinový obal. To znamená, že položky lze získat posloupností vodorovných nebo svislých řezů od okraje k okraji.

První montáž s klesající výškou (FFDH)

Tento algoritmus, poprvé popsaný Coffmanem a kol.^[9] v roce 1980 funguje podobně jako algoritmus NFDH. Při umisťování další položky však algoritmus skenuje úrovně zdola nahoru a umístí položku do první úrovně, na kterou se vejde. Nová úroveň se otevře, pouze pokud se položka nevejde do žádné předchozí.

Tento algoritmus má následující vlastnosti:

Dobu chodu lze omezit ${ displaystyle { mathcal {O}} (| { mathcal {I}} | ^ {2})}$ , protože jich je nanejvýš ${ displaystyle | { mathcal {I}} |}$ úrovně.
Pro každou sadu položek ${ displaystyle { mathcal {I}}}$ vytváří výplň výšky ${ displaystyle FFDH ({ mathcal {I}}) leq 1,7OPT ({ mathcal {I}}) + h _ { max} leq 2,7OPT ({ mathcal {I}})}$ , kde ${ displaystyle h _ { max}}$ je největší výška položky v ${ displaystyle { mathcal {I}}}$ .^[9]
Nechat ${ displaystyle m geq 2}$ . Pro libovolnou sadu položek ${ displaystyle { mathcal {I}}}$ a pásek o šířce ${ displaystyle W}$ takhle ${ displaystyle w (i) leq W / m}$ pro každého ${ displaystyle i in { mathcal {I}}}$ , to platí ${ displaystyle FFDH ({ mathcal {I}}) leq left (1 + 1 / m right) OPT ({ mathcal {I}}) + h _ { max}}$ . Navíc pro každého ${ displaystyle varepsilon> 0}$ , existuje taková sada položek ${ displaystyle { mathcal {I}}}$ s ${ displaystyle FFDH ({ mathcal {I}})> left (1 + 1 / m- varepsilon right) OPT ({ mathcal {I}})}$ .^[9]
Pokud jsou všechny položky v ${ displaystyle { mathcal {I}}}$ jsou čtverce, to platí ${ displaystyle FFDH ({ mathcal {I}}) leq (3/2) OPT ({ mathcal {I}}) + h _ { max}}$ . Navíc pro každého ${ displaystyle varepsilon> 0}$ , existuje sada čtverců ${ displaystyle { mathcal {I}}}$ takhle ${ displaystyle FFDH ({ mathcal {I}})> left (3 / 2- varepsilon right) OPT ({ mathcal {I}})}$ .^[9]
Balením je gilotinový obal. To znamená, že položky lze získat posloupností vodorovných nebo svislých řezů od okraje k okraji.

Algoritmus split-fit (SF)

Tento algoritmus poprvé popsali Coffman et al.^[9] Pro danou sadu položek ${ displaystyle { mathcal {I}}}$ a pásek o šířce ${ displaystyle W}$ , funguje takto:

Určete ${ displaystyle m in mathbb {N}}$ , největší celé číslo tak, aby dané obdélníky měly šířku ${ displaystyle W / m}$ nebo méně.
Rozdělit ${ displaystyle { mathcal {I}}}$ do dvou sad ${ displaystyle { mathcal {I}} _ {široký}}$ a ${ displaystyle { mathcal {I}} _ {úzký}}$ , takový, že ${ displaystyle { mathcal {I}} _ {široký}}$ obsahuje všechny položky ${ displaystyle i in { mathcal {I}}}$ se šířkou ${ displaystyle w (i)> W / (m + 1)}$ zatímco ${ displaystyle { mathcal {I}} _ {úzký}}$ obsahuje všechny položky s ${ displaystyle w (i) leq W / (m + 1)}$ .
Objednat ${ displaystyle { mathcal {I}} _ {široký}}$ a ${ displaystyle { mathcal {I}} _ {úzký}}$ nezvyšující se výškou.
Zabalte položky ${ displaystyle { mathcal {I}} _ {široký}}$ s algoritmem FFDH.
Změňte pořadí úrovní / polic vytvořených FFDH tak, aby byly všechny police s celkovou šířkou větší než ${ displaystyle W (m + 1) / (m + 2)}$ jsou pod úzkými.
To ponechá obdélníkovou oblast ${ displaystyle R}$ z s ${ displaystyle W / (m + 2)}$ , vedle užších úrovní / polic, které neobsahují žádnou položku.
K zabalení položek použijte algoritmus FFDH ${ displaystyle { mathcal {I}} _ {úzký}}$ pomocí této oblasti ${ displaystyle R}$ také.

Tento algoritmus má následující vlastnosti:

Pro každou sadu položek ${ displaystyle { mathcal {I}}}$ a odpovídající ${ displaystyle m}$ , to platí ${ displaystyle SF ({ mathcal {I}}) leq (m + 2) / (m + 1) OPT ({ mathcal {I}}) + 2 h _ { max}}$ .^[9] Všimněte si, že pro ${ displaystyle m = 1}$ , to platí ${ displaystyle SF ({ mathcal {I}}) leq (3/2) OPT ({ mathcal {I}}) + 2 h _ { max}}$
Pro každého ${ displaystyle varepsilon> 0}$ , existuje sada položek ${ displaystyle { mathcal {I}}}$ takhle ${ displaystyle SF ({ mathcal {I}})> left ((m + 2) / (m + 1) - varepsilon right) OPT ({ mathcal {I}})}$ .^[9]

Sleatorův algoritmus

Pro danou sadu položek ${ displaystyle { mathcal {I}}}$ a pásek o šířce ${ displaystyle W}$ , funguje takto:

Najděte všechny položky o šířce větší než ${ displaystyle W / 2}$ a stohujte je ve spodní části proužku (v náhodném pořadí). Zavolejte celkovou výšku těchto položek ${ displaystyle h_ {0}}$ . Všechny ostatní položky budou umístěny výše ${ displaystyle h_ {0}}$ .
Seřaďte všechny zbývající položky v nezvyšujícím se pořadí podle výšky. Položky budou umístěny v tomto pořadí.
Zvažte vodorovnou čáru v ${ displaystyle h_ {0}}$ jako police. Algoritmus umístí položky na tuto polici v nezvyšujícím se pořadí výšky, dokud nezůstane žádná položka nebo se nevejde další.
Nakreslete svislou čáru na ${ displaystyle W / 2}$ , který rozřízne proužek na dvě stejné poloviny.
Nechat ${ displaystyle h_ {l}}$ být nejvyšším bodem pokrytým jakoukoli položkou v levé polovině a ${ displaystyle h_ {r}}$ odpovídající bod na pravé polovině. Nakreslete dva vodorovné úsečky o délce ${ displaystyle W / 2}$ na ${ displaystyle h_ {l}}$ a ${ displaystyle h_ {r}}$ přes levou a pravou polovinu proužku. Tyto dva řádky vytvářejí nové police, na které algoritmus umístí položky, jako v kroku 3. Vyberte polovinu, která má spodní polici, a položte položky na tuto polici, dokud se na ni nevejde žádná jiná položka. Tento krok opakujte, dokud nezůstane žádná položka.

Tento algoritmus má následující vlastnosti:

Dobu chodu lze omezit ${ displaystyle { mathcal {O}} (| { mathcal {I}} | log (| { mathcal {I}} |))}$ a pokud jsou položky již seřazeny dokonce podle ${ displaystyle { mathcal {O}} (| { mathcal {I}} |)}$ .
Pro každou sadu položek ${ displaystyle { mathcal {I}}}$ vytváří výplň výšky ${ displaystyle A ({ mathcal {I}}) leq 2OPT ({ mathcal {I}}) + h _ { max} / 2 leq 2.5OPT ({ mathcal {I}})}$ , kde ${ displaystyle h _ { max}}$ je největší výška položky v ${ displaystyle { mathcal {I}}}$ .^[10]

Rozdělený algoritmus (SP)

Tento algoritmus je rozšířením přístupu Sleator a byl poprvé popsán Golanem.^[11] Umístí položky v nezvětšujícím se pořadí podle šířky. Intuitivní myšlenkou je rozdělit proužek na dílčí proužky při umístění některých položek. Kdykoli je to možné, algoritmus umístí aktuální položku ${ displaystyle i}$ vedle již umístěné položky ${ displaystyle j}$ . V tomto případě rozděluje odpovídající dílčí pás na dva kusy: jeden obsahující první položku ${ displaystyle j}$ a druhá obsahuje aktuální položku ${ displaystyle i}$ Pokud to není možné, umístí se to ${ displaystyle i}$ na již položenou položku a nerozdělí dílčí proužek.

Tento algoritmus vytváří množinu S dílčích proužků. Pro každý dílčí proužek s ∈ S známe jeho levý dolní roh s.xpozice a s.pozice, jeho šířka Šířka, vodorovné čáry rovnoběžné s horním a dolním okrajem položky umístěné jako poslední uvnitř tohoto dílčího pruhu večeře a s.lower, stejně jako jeho šířka s.itemWidth.

funkce Split Algorithm (SP) je    vstup: položky Já, šířka pásu Ž    výstup: Balení položek    Třídit I v nezvětšujícím se pořadí šířek; Definujte prázdný seznam S dílčích proužků; Definujte nový dílčí proužek s s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W; Přidat s k S; zatímco Nevyprázdním dělat        i: = I.pop (); Odstraní nejširší položku z I Definovat nový seznam S_2 obsahující všechny dílčí proužky se s.width - s.itemWidth ≥ i.width; S_2 obsahuje všechny dílčí proužky, kam se vejde vedle již umístěné položky        -li S_2 je prázdný pak            V takovém případě položte položku na jinou.            Najděte dílčí proužek s v S s nejmenším s.upper; tj. nejméně naplněný dílčí pás            Umístěte i do polohy (s.xpozice, s.vrchu); Aktualizace s: s.lower: = s.upper; s.upper: = s.upper + i.height; s.itemWidth: = i.šířka; jiný             V takovém případě položte položku vedle další na stejné úrovni a rozdělte odpovídající dílčí pás na této pozici.            Najděte s ∈ S_2 s nejmenším s.lower; Umístěte i na pozici (s.xposition + s.itemWidth, s.lower); Odebrat s z S; Definujte dva nové dílčí proužky s1 a s2 s 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 = i.height, s2. itemWidth = i.width; S.add (s1, s2); vrátit se koncová funkce

Tento algoritmus má následující vlastnosti:

Dobu chodu lze omezit ${ displaystyle { mathcal {O}} (| { mathcal {I}} | ^ {2})}$ protože počet dílčích proužků je omezen ${ displaystyle | { mathcal {I}} |}$ .
Pro libovolnou sadu položek ${ displaystyle { mathcal {I}}}$ to platí ${ displaystyle SP ({ mathcal {I}}) leq 2OPT ({ mathcal {I}}) + h _ { max} leq 3OPT ({ mathcal {I}})}$ .^[11]
Pro všechny ${ displaystyle varepsilon> 0}$ , existuje sada položek ${ displaystyle { mathcal {I}}}$ takhle ${ displaystyle SP ({ mathcal {I}})> (3- varepsilon) OPT ({ mathcal {I}})}$ .^[11]
Pro všechny ${ displaystyle varepsilon> 0}$ a ${ displaystyle C> 0}$ , existuje sada položek ${ displaystyle { mathcal {I}}}$ takhle ${ displaystyle SP ({ mathcal {I}})> (2- varepsilon) OPT ({ mathcal {I}}) + C}$ .^[11]

Reverse fit (RF)

Tento algoritmus poprvé popsal Schiermeyer.^[13] Popis tohoto algoritmu vyžaduje nějakou další notaci. Pro vloženou položku ${ displaystyle i in { mathcal {I}}}$ , jeho levý dolní roh je označen ${ displaystyle (a_ {i}, c_ {i})}$ a jeho pravý horní roh o ${ displaystyle (b_ {i}, d_ {i})}$ .

Vzhledem k sadě položek ${ displaystyle { mathcal {I}}}$ a pruh šířky ${ displaystyle W}$ , funguje takto:

Skládejte všechny obdélníky o šířce větší než ${ displaystyle W / 2}$ na sebe (v náhodném pořadí) ve spodní části proužku. Označit podle ${ displaystyle H_ {0}}$ výška tohoto stohu. Všechny ostatní položky budou zabaleny výše ${ displaystyle H_ {0}}$ .
Seřaďte zbývající položky v pořadí nezvyšující se výšky a zvažte položky v tomto pořadí v následujících krocích. Nechat ${ displaystyle h _ { max}}$ být výškou nejvyšší z těchto zbývajících položek.
Položte položky jeden po druhém doleva zarovnané na polici definované pomocí ${ displaystyle H_ {0}}$ dokud se na tuto polici nevejde žádný jiný předmět nebo nezůstane žádný předmět. Říkejte tomu police první úroveň.
Nechat ${ displaystyle h_ {1}}$ být výškou nejvyšší nebalené položky. Definujte novou polici na ${ displaystyle H_ {0} + h _ { max} + h_ {1}}$ . Algoritmus vyplní tuto poličku zprava doleva a zarovná položky doprava, takže se položky dotknou této police svým vrcholem. Říkejte tomu police druhá reverzní úroveň.
Položte předměty do dvou polic díky First-Fit, tj. Položte je do první úrovně tam, kde se vejdou, a do druhé jinak. Pokračujte, dokud nezůstanou žádné položky nebo dokud nebude celková šířka položek ve druhé poličce alespoň ${ displaystyle W / 2}$ .
Posuňte druhou reverzní úroveň dolů, dokud se položka z ní nedotkne položky z první úrovně. Definovat ${ displaystyle H_ {1}}$ jako nová svislá poloha posunuté police. Nechat ${ displaystyle f}$ a ${ displaystyle s}$ být tím správným párem dotýkajících se položek ${ displaystyle f}$ umístěny na první úrovni a ${ displaystyle s}$ na druhé reverzní úrovni. Definovat ${ displaystyle x_ {r}: = max (b_ {f}, b_ {s})}$ .
Li ${ displaystyle x_ {r}$ ${ displaystyle x_ {r} <W / 2}$ pak ${ displaystyle s}$ $s$ je poslední obdélník umístěný ve druhé reverzní úrovni. Posuňte všechny ostatní položky z této úrovně dále dolů (všechny stejné částky), dokud se první nedotkne položky z první úrovně. Algoritmus opět určuje nejpravější dvojici dotykových položek ${ displaystyle f '}$ $F'$ a ${ displaystyle s '}$ $s '$ . Definovat ${ displaystyle h_ {2}}$ $h_ {2}$ jako množství, o které byla police posunuta dolů.
1. Li ${ displaystyle h_ {2} leq h (s)}$ pak posun ${ displaystyle s}$ doleva, dokud se nedotkne jiné položky nebo okraje pruhu. Definujte třetí úroveň v horní části ${ displaystyle s '}$ .
2. Li ${ displaystyle h_ {2}> h (s)}$ pak posun ${ displaystyle s}$ definovat třetí úroveň v horní části ${ displaystyle s '}$ . Místo ${ displaystyle s}$ zarovnáno doleva v této třetí úrovni, takže se dotkne položky z první úrovně nalevo.
Pokračujte v balení položek pomocí heuristiky First-Fit. Každá následující úroveň (počínaje úrovní tři) je definována vodorovnou čarou v horní části největší položky na předchozí úrovni. Všimněte si, že první položka umístěná v další úrovni se nemusí levou stranou dotknout ohraničení pruhu, ale položky z první úrovně nebo položky ${ displaystyle s}$ .

Tento algoritmus má následující vlastnosti:

Dobu chodu lze omezit ${ displaystyle { mathcal {O}} (| { mathcal {I}} | ^ {2})}$ , protože jich je nanejvýš ${ displaystyle | { mathcal {I}} |}$ úrovně.
Pro každou sadu položek ${ displaystyle { mathcal {I}}}$ vytváří výplň výšky ${ displaystyle RF ({ mathcal {I}}) leq 2OPT ({ mathcal {I}})}$ .^[13]

Steinbergův algoritmus (ST)

Steinbergův algoritmus je rekurzivní. Vzhledem k sadě obdélníkových předmětů ${ displaystyle { mathcal {I}}}$ a obdélníkovou cílovou oblast o šířce ${ displaystyle W}$ a výška ${ displaystyle H}$ , navrhuje čtyři pravidla redukce, která umisťují některé položky a ponechávají menší obdélníkovou oblast se stejnými vlastnostmi jako dříve, co se týče zbytkových položek. Zvažte následující zápisy: Vzhledem k sadě položek ${ displaystyle { mathcal {I}}}$ označujeme ${ displaystyle h _ { max} ({ mathcal {I}})}$ nejvyšší výška položky v ${ displaystyle { mathcal {I}}}$ , ${ displaystyle w _ { max} ({ mathcal {I}})}$ největší šířka položky v ${ displaystyle { mathcal {I}}}$ a tím ${ displaystyle mathrm {AREA} ({ mathcal {I}}): = sum _ {i in { mathcal {I}}} w (i) h (i)}$ celková plocha těchto položek. Steinbergs ukazuje, že pokud

${ displaystyle h _ { max} ({ mathcal {I}}) leq H}$ , ${ displaystyle w _ { max} ({ mathcal {I}}) leq W}$ , a ${ displaystyle mathrm {AREA} ({ mathcal {I}}) leq W cdot H- (2h _ { max} ({ mathcal {I}}) - h) _ {+} (2w _ { max} ({ mathcal {I}}) - W) _ {+}}$ , kde ${ displaystyle (a) _ {+}: = max {0, a }}$ ,

pak mohou být všechny položky umístěny uvnitř cílové oblasti velikosti ${ displaystyle W krát H}$ Každé pravidlo redukce vytvoří menší cílovou oblast a podmnožinu položek, které je třeba umístit. Když výše uvedená podmínka platí před zahájením procedury, pak bude mít vytvořený dílčí problém také tuto vlastnost.

Postup 1: Lze použít, pokud ${ displaystyle w _ { max} ({ mathcal {I}} ') geq W / 2}$ .

Najděte všechny položky ${ displaystyle i in { mathcal {I}}}$ se šířkou ${ displaystyle w (i) geq W / 2}$ a odstranit je z ${ displaystyle { mathcal {I}}}$ .
Seřaďte je podle nezvětšující se šířky a umístěte je doleva zarovnané v dolní části cílové oblasti. Nechat ${ displaystyle h_ {0}}$ být jejich celková výška.
Najděte všechny položky ${ displaystyle i in { mathcal {I}}}$ se šířkou ${ displaystyle h (i)> H-h_ {0}}$ . Odeberte je z ${ displaystyle { mathcal {I}}}$ a položte je do nové sady ${ displaystyle { mathcal {I}} _ {H}}$ .
Li ${ displaystyle { mathcal {I}} _ {H}}$ je prázdný, definujte novou cílovou oblast jako oblast výše ${ displaystyle h_ {0}}$ , tj. má výšku ${ displaystyle H-h_ {0}}$ a šířka ${ displaystyle W}$ . Vyřešte problém skládající se z této nové cílové oblasti a redukované sady položek pomocí jednoho z postupů.
Li ${ displaystyle { mathcal {I}} _ {H}}$ není prázdná, seřaďte ji podle nezvyšující se výšky a umístěte položky vpravo po jednom do pravého horního rohu cílové oblasti. Nechat ${ displaystyle w_ {0}}$ být celková šířka těchto položek. Definujte novou cílovou oblast se šířkou ${ displaystyle W-w_ {0}}$ a výška ${ displaystyle H-h_ {0}}$ v levém horním rohu. Vyřešte problém skládající se z této nové cílové oblasti a redukované sady položek pomocí jednoho z postupů.

Postup 2: Lze použít, pokud platí následující podmínky: ${ displaystyle w _ { max} ({ mathcal {I}}) leq W / 2}$ , ${ displaystyle h _ { max} ({ mathcal {I}}) leq H / 2}$ a existují dvě různé položky ${ displaystyle i, i ' in { mathcal {I}}}$ s ${ displaystyle w (i) geq W / 4}$ , ${ displaystyle w (i ') geq W / 4}$ , ${ displaystyle h (i) geq H / 4}$ , ${ displaystyle h (i ') geq H / 4}$ a ${ displaystyle 2 ( mathrm {AREA} ({ mathcal {I}}) - w (i) h (i) -w (i ') h (i')) leq (W- max {w (i), w (i ') }) H}$ .

Nalézt ${ displaystyle i}$ a ${ displaystyle i '}$ a odstranit je z ${ displaystyle { mathcal {I}}}$ .
Umístěte širší do levého dolního rohu cílové oblasti a ten užší zarovnejte doleva do horní části první.
Definujte novou cílovou oblast napravo od těchto obou položek, aby měla šířku ${ displaystyle W- max {w (i), w (i ') }}$ a výška ${ displaystyle H}$ .
Vložte zbytky ${ displaystyle { mathcal {I}}}$ jedním z postupů do nové cílové oblasti.

Postup 3: Lze použít, pokud platí následující podmínky: ${ displaystyle w _ { max} ({ mathcal {I}}) leq W / 2}$ , ${ displaystyle h _ { max} ({ mathcal {I}}) leq H / 2}$ , ${ displaystyle | { mathcal {I}} |> 1}$ a při třídění položek podle zmenšení šířky existuje index ${ displaystyle m}$ takové, že při definování ${ displaystyle { mathcal {já '}}}$ jako první ${ displaystyle m}$ položky, které to drží ${ displaystyle mathrm {AREA} ({ mathcal {I}}) - WH / 4 leq mathrm {AREA} ({ mathcal {I '}}) leq 3WH / 8}$ stejně jako ${ displaystyle w (i_ {m + 1}) leq W / 4}$

Soubor ${ displaystyle W_ {1}: = max {W / 2,2 mathrm {AREA} ({ mathcal {I '}}) / H}}$ .
Definujte dvě nové obdélníkové cílové oblasti, jednu v levém dolním rohu původní s výškou ${ displaystyle H}$ a šířka ${ displaystyle W_ {1}}$ a druhá vlevo s výškou ${ displaystyle H}$ a šířka ${ displaystyle W-W_ {1}}$ .
K umístění položek použijte jeden z postupů ${ displaystyle { mathcal {já '}}}$ do první nové cílové oblasti a položek v ${ displaystyle { mathcal {I}} setminus { mathcal {I '}}}$ do druhého.

Všimněte si, že postupy 1 až 3 mají symetrickou verzi při výměně výšky a šířky položek a cílové oblasti.

Postup 4: Lze použít, pokud platí následující podmínky: ${ displaystyle w _ { max} ({ mathcal {I}}) leq W / 2}$ , ${ displaystyle h _ { max} ({ mathcal {I}}) leq H / 2}$ a existuje položka ${ displaystyle i in { mathcal {I}}}$ takhle ${ displaystyle w (i) h (i) geq mathrm {AREA} ({ mathcal {I}}) - WH / 4}$ .

Umístěte položku ${ displaystyle i}$ v levém dolním rohu cílové oblasti a vyjměte ji z ${ displaystyle { mathcal {I}}}$ .
Definujte novou cílovou oblast vpravo od této položky tak, aby měla šířku ${ displaystyle W-w (i)}$ a výška ${ displaystyle H}$ a umístěte zbytky uvnitř této oblasti pomocí jednoho z postupů.

Tento algoritmus má následující vlastnosti:

Dobu chodu lze omezit ${ displaystyle { mathcal {O}} (| { mathcal {I}} | log (| { mathcal {I}} |) ^ {2} / log ( log (| { mathcal {I }} |)))}$ .^[8]
Pro každou sadu položek ${ displaystyle { mathcal {I}}}$ vytváří výplň výšky ${ displaystyle ST ({ mathcal {I}}) leq 2OPT ({ mathcal {I}})}$ .^[8]

Algoritmy aproximace času pseudo-polynomu

Zlepšit spodní hranici ${ displaystyle 3/2}$ pro polynomiální časové algoritmy byly uvažovány pseudo-polynomiální časové algoritmy pro problém s balením pásů. Při zvažování tohoto typu algoritmů jsou všechny velikosti položek a pásu uvedeny jako integrály. Dále šířka pruhu ${ displaystyle W}$ se může za běhu objevit polynomiálně. Všimněte si, že se to již nepovažuje za dobu běhu polynomu, protože v daném případě šířka pruhu vyžaduje velikost kódování ${ displaystyle log (W)}$ .

Vyvinuté pseudo-polynomiální časové algoritmy většinou používají stejný přístup. Ukazuje se, že každé optimální řešení lze zjednodušit a transformovat do takového, které má jednu ze stálého počtu struktur. Algoritmus poté iteruje všechny tyto struktury a umístí položky dovnitř pomocí lineárního a dynamického programování. Dosud nejlepší dosažený poměr je ${ displaystyle (5/4 + varepsilon) OPT (I)}$ .^[19] zatímco nemůže existovat algoritmus pseudo-polynomiálního času s poměrem lepším než ${ displaystyle 5/4}$ pokud ${ displaystyle P = NP}$ ^[5]

Přehled pseudo-polynomiálních časových aproximací
Rok	Aproximační poměr	Zdroj	Komentář
2010	${ displaystyle (3/2 + varepsilon)}$	Jansen, Thöle^[20]
2016	${ displaystyle (7/5 + varepsilon)}$	Nadiradze, Wiese^[21]
2016	${ displaystyle (4/3 + varepsilon)}$	Gálvez, Grandoni, Ingala, Khan^[22]	také pro 90 stupňové rotace
2017	${ displaystyle (4/3 + varepsilon)}$	Jansen, Rau^[23]
2019	${ displaystyle (5/4 + varepsilon)}$	Jansen, Rau^[19]	také pro rotace o 90 stupňů a souvislé tvarovatelné úlohy

Online algoritmy

V online varianta balení pásky, zboží dorazí v průběhu času. Když položka dorazí, musí být umístěna bezprostředně předtím, než je známa další položka. Zvažovány jsou dva typy online algoritmů. In the first variant, it is not allowed to alter the packing once an item is placed. In the second, items may be repacked when another item arrives. This variant is called the migration model.

The quality of an online algorithm is measured by the (absolute) competitive ratio

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

kde ${displaystyle A(I)}$ corresponds to the solution generated by the online algorithm and ${displaystyle OPT(I)}$ corresponds to the size of the optimal solution. In addition to the absolute competitive ratio, the asymptotic competitive ratio of online algorithms has been studied. For instances ${ displaystyle I}$ s ${displaystyle h_{max }(I)leq 1}$ it is defined as

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

Note that all the instances can be scaled such that ${displaystyle h_{max }(I)leq 1}$ .

Overview of online algorithms without migration
Rok	Competitive Ratio	Asymptotic Competitive Ratio	Zdroj
1983	6.99	${displaystyle approx 1.7}$	Baker and Schwarz^[24]
1997		${displaystyle 1.69+varepsilon }$	Csirik and Woeginger^[25]
2007	6.6623		Hurink and Paulus^[26]
2009	6.6623		Ye, Han, and Zhang^[27]
2007		${displaystyle 1.58889}$	Han et al.^[28] + Seiden^[29]

The framework of Han et al.^[28] is applicable in the online setting if the online bin packingalgorithm belongs to the class Super Harmonic. Thus, Seiden's online bin packing algorithmHarmonic++^[29] implies an algorithm for online strip packing with asymptotic ratio 1.58889.

Overview of lower bounds for online algorithms without migration
Rok	Competitive Ratio	Asymptotic Competitive Ratio	Zdroj	Komentář
1982	${ displaystyle 2}$		Brown, Baker, and Katseff^[30]
2006	2.25		Johannes^[31]	also holds for the parallel task scheduling problem
2007	2.43		Hurink and Paulus^[32]	also holds for the parallel task scheduling problem
2009	2.457		Kern and Paulus ^[33]
2012		${displaystyle 1.5404}$	Balogh and Békési^[34]	lower bound due to the underlying bin packing problem
2016	2.618		Yu, Mao, and Xiao^[35]

Reference

^ Wäscher, Gerhard; Haußner, Heike; Schumann, Holger (16 December 2007). "An improved typology of cutting and packing problems". Evropský žurnál operačního výzkumu. 183 (3): 1109–1130. doi:10.1016/j.ejor.2005.12.047. ISSN 0377-2217.
^ ^A ^b ^C ^d ^E ^F ^G ^h ⁱ ^j Baker, Brenda S.; Coffman Jr., Edward G.; Rivest, Ronald L. (1980). "Orthogonal Packings in Two Dimensions". SIAM J. Comput. 9 (4): 846–855. doi:10.1137/0209064.
^ ^A ^b Harren, Rolf; Jansen, Klaus; Prädel, Lars; van Stee, Rob (February 2014). "A (5/3 + epsilon)-approximation for strip packing". Výpočetní geometrie. 47 (2): 248–267. doi:10.1016/j.comgeo.2013.08.008.
^ Neuenfeldt Junior, Alvaro Luiz. "The Two-Dimensional Rectangular Strip Packing Problem" (PDF). 10820228.
^ ^A ^b Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (2019). "Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing". Teorie výpočetních systémů. 64: 120–140. arXiv:1705.04587. doi:10.1007/s00224-019-09910-6. S2CID 67168004.
^ Ashok, Pradeesha; Kolay, Sudeshna; Meesum, S.M.; Saurabh, Saket (January 2017). "Parameterized complexity of Strip Packing and Minimum Volume Packing". Teoretická informatika. 661: 56–64. doi:10.1016/j.tcs.2016.11.034.
^ ^A ^b ^C Martello, Silvano; Monaci, Michele; Vigo, Daniele (1 August 2003). "An Exact Approach to the Strip-Packing Problem". INFORMS Journal o práci na počítači. 15 (3): 310–319. doi:10.1287/ijoc.15.3.310.16082. ISSN 1091-9856.
^ ^A ^b ^C ^d Steinberg, A. (March 1997). "A Strip-Packing Algorithm with Absolute Performance Bound 2". SIAM Journal on Computing. 26 (2): 401–409. doi:10.1137/S0097539793255801.
^ ^A ^b ^C ^d ^E ^F ^G ^h ⁱ ^j ^k Coffman Jr., Edward G.; Garey, M. R.; Johnson, David S.; Tarjan, Robert Endre (1980). "Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms". SIAM J. Comput. 9 (4): 808–826. doi:10.1137/0209062.
^ ^A ^b Sleator, Daniel Dominic (1980). "A 2.5 Times Optimal Algorithm for Packing in Two Dimensions". Inf. Process. Lett. 10: 37–40. doi:10.1016/0020-0190(80)90121-0.
^ ^A ^b ^C ^d ^E Golan, Igal (August 1981). "Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms". SIAM Journal on Computing. 10 (3): 571–582. doi:10.1137/0210042.
^ Baker, Brenda S; Brown, Donna J; Katseff, Howard P (December 1981). "A 5/4 algorithm for two-dimensional packing". Journal of Algorithms. 2 (4): 348–368. doi:10.1016/0196-6774(81)90034-1.
^ ^A ^b ^C Schiermeyer, Ingo (1994). "Reverse-Fit: A 2-optimal algorithm for packing rectangles". Algorithms — ESA '94. Přednášky z informatiky. 855. Springer Berlin Heidelberg. pp. 290–299. doi:10.1007/bfb0049416. ISBN 978-3-540-58434-6.
^ Kenyon, Claire; Rémila, Eric (November 2000). "A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem". Matematika operačního výzkumu. 25 (4): 645–656. doi:10.1287/moor.25.4.645.12118. S2CID 5361969.
^ Harren, Rolf; van Stee, Rob (2009). "Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, {APPROX} 2009, and 13th International Workshop, {RANDOM} 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. 5687: 177–189. Bibcode:2009LNCS.5687..177H. doi:10.1007/978-3-642-03685-9\_14 (inactive 2020-11-26).CS1 maint: DOI neaktivní od listopadu 2020 (odkaz)
^ Jansen, Klaus; Solis-Oba, Roberto (August 2009). "Rectangle packing with one-dimensional resource augmentation". Diskrétní optimalizace. 6 (3): 310–323. doi:10.1016/j.disopt.2009.04.001.
^ Bougeret, Marin; Dutot, Pierre-Francois; Jansen, Klaus; Robenek, Christina; Trystram, Denis (5 April 2012). "Approximation Algorithms for Multiple Strip Packing and Scheduking Parallel Jobs in Platforms". Discrete Mathematics, Algorithms and Applications. 03 (4): 553–586. doi:10.1142/S1793830911001413.
^ Sviridenko, Maxim (January 2012). "A note on the Kenyon–Remila strip-packing algorithm". Dopisy o zpracování informací. 112 (1–2): 10–12. doi:10.1016/j.ipl.2011.10.003.
^ ^A ^b Jansen, Klaus; Rau, Malin (2019). "Closing the Gap for Pseudo-Polynomial Strip Packing". 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 144: 62:1–62:14. doi:10.4230/LIPIcs.ESA.2019.62. S2CID 24303167.
^ Jansen, Klaus; Thöle, Ralf (January 2010). "Approximation Algorithms for Scheduling Parallel Jobs". SIAM Journal on Computing. 39 (8): 3571–3615. doi:10.1137/080736491.
^ Nadiradze, Giorgi; Wiese, Andreas (21 December 2015). "On approximating strip packing with a better ratio than 3/2". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics: 1491–1510. doi:10.1137/1.9781611974331.ch102. ISBN 978-1-61197-433-1.
^ Gálvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Khan, Arindam (2016). "Improved Pseudo-Polynomial-Time Approximation for Strip Packing". 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 65: 9:1–9:14. doi:10.4230/LIPIcs.FSTTCS.2016.9. S2CID 3205478.
^ Jansen, Klaus; Rau, Malin (29–31 March 2017). "Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width". {WALCOM:} Algorithms and Computation, 11th International Conference and Workshops, {WALCOM} 2017, Hsinchu, Taiwan: 409–420. doi:10.1007/978-3-319-53925-6\_32 (inactive 2020-11-26).CS1 maint: DOI neaktivní od listopadu 2020 (odkaz)
^ 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.
^ Csirik, János; Woeginger, Gerhard J. (28 August 1997). "Shelf algorithms for on-line strip packing". Dopisy o zpracování informací. 63 (4): 171–175. doi:10.1016/S0020-0190(97)00120-8. ISSN 0020-0190.
^ Hurink, Johann L.; Paulus, Jacob Jan (2007). "Online Algorithm for Parallel Job Scheduling and Strip Packing". WAOA 2007 - Approximation and Online Algorithms. Přednášky z informatiky. Springer Berlin Heidelberg. 4927: 67–74. doi:10.1007/978-3-540-77918-6_6. ISBN 978-3-540-77917-9.
^ 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.
^ ^A ^b Han, Xin; Iwama, Kazuo; Ye, Deshi; Zhang, Guochuan (2007). "Strip Packing vs. Bin Packing". Algorithmic Aspects in Information and Management. Přednášky z informatiky. Springer Berlin Heidelberg. 4508: 358–367. arXiv:cs/0607046. doi:10.1007/978-3-540-72870-2_34. ISBN 978-3-540-72868-9. S2CID 580.
^ ^A ^b Seiden, Steven S. (2001). "On the Online Bin Packing Problem". Automata, Languages and Programming. Přednášky z informatiky. Springer Berlin Heidelberg. 2076: 237–248. doi:10.1007/3-540-48224-5_20. ISBN 978-3-540-42287-7.
^ Brown, Donna J.; Baker, Brenda S.; Katseff, Howard P. (1 November 1982). "Lower bounds for on-line two-dimensional packing algorithms". Acta Informatica. 18 (2): 207–225. doi:10.1007/BF00264439. hdl:2142/74223. ISSN 1432-0525. S2CID 21170278.
^ Johannes, Berit (1 October 2006). "Scheduling parallel jobs to minimize the makespan" (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.
^ Hurink, J. L.; Paulus, J. J. (1 January 2008). "Online scheduling of parallel jobs on two machines is 2-competitive". Dopisy o operačním výzkumu. 36 (1): 51–56. doi:10.1016/j.orl.2007.06.001. ISSN 0167-6377.
^ Kern, Walter; Paulus, Jacob Jan (2009). "A note on the lower bound for online strip packing". Dopisy o operačním výzkumu.
^ Balogh, János; Békési, József; Galambos, Gábor (6 July 2012). "New lower bounds for certain classes of bin packing algorithms". Teoretická informatika. 440-441: 1–13. doi:10.1016/j.tcs.2012.04.017. ISSN 0304-3975.
^ Yu, Guosong; Mao, Yanling; Xiao, Jiaoliao (1 May 2016). "A new lower bound for online strip packing". Evropský žurnál operačního výzkumu. 250 (3): 754–759. doi:10.1016/j.ejor.2015.10.012. ISSN 0377-2217.

[1] Wäscher, Gerhard; Haußner, Heike; Schumann, Holger (16 December 2007). "An improved typology of cutting and packing problems". Evropský žurnál operačního výzkumu. 183 (3): 1109–1130. doi:10.1016/j.ejor.2005.12.047. ISSN 0377-2217.

[Baker1980-2] A ^b ^C ^d ^E ^F ^G ^h ⁱ ^j Baker, Brenda S.; Coffman Jr., Edward G.; Rivest, Ronald L. (1980). "Orthogonal Packings in Two Dimensions". SIAM J. Comput. 9 (4): 846–855. doi:10.1137/0209064.

[Harren-3] A ^b Harren, Rolf; Jansen, Klaus; Prädel, Lars; van Stee, Rob (February 2014). "A (5/3 + epsilon)-approximation for strip packing". Výpočetní geometrie. 47 (2): 248–267. doi:10.1016/j.comgeo.2013.08.008.

[4] Neuenfeldt Junior, Alvaro Luiz. "The Two-Dimensional Rectangular Strip Packing Problem" (PDF). 10820228.

[Henning-5] A ^b Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (2019). "Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing". Teorie výpočetních systémů. 64: 120–140. arXiv:1705.04587. doi:10.1007/s00224-019-09910-6. S2CID 67168004.

[6] Ashok, Pradeesha; Kolay, Sudeshna; Meesum, S.M.; Saurabh, Saket (January 2017). "Parameterized complexity of Strip Packing and Minimum Volume Packing". Teoretická informatika. 661: 56–64. doi:10.1016/j.tcs.2016.11.034.

[MartelloExact-7] A ^b ^C Martello, Silvano; Monaci, Michele; Vigo, Daniele (1 August 2003). "An Exact Approach to the Strip-Packing Problem". INFORMS Journal o práci na počítači. 15 (3): 310–319. doi:10.1287/ijoc.15.3.310.16082. ISSN 1091-9856.

[Steinberg-8] A ^b ^C ^d Steinberg, A. (March 1997). "A Strip-Packing Algorithm with Absolute Performance Bound 2". SIAM Journal on Computing. 26 (2): 401–409. doi:10.1137/S0097539793255801.

[Coffman1980-9] A ^b ^C ^d ^E ^F ^G ^h ⁱ ^j ^k Coffman Jr., Edward G.; Garey, M. R.; Johnson, David S.; Tarjan, Robert Endre (1980). "Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms". SIAM J. Comput. 9 (4): 808–826. doi:10.1137/0209062.

[Sleator-10] A ^b Sleator, Daniel Dominic (1980). "A 2.5 Times Optimal Algorithm for Packing in Two Dimensions". Inf. Process. Lett. 10: 37–40. doi:10.1016/0020-0190(80)90121-0.

[Golan-11] A ^b ^C ^d ^E Golan, Igal (August 1981). "Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms". SIAM Journal on Computing. 10 (3): 571–582. doi:10.1137/0210042.

[12] Baker, Brenda S; Brown, Donna J; Katseff, Howard P (December 1981). "A 5/4 algorithm for two-dimensional packing". Journal of Algorithms. 2 (4): 348–368. doi:10.1016/0196-6774(81)90034-1.

[Schiermeyer-13] A ^b ^C Schiermeyer, Ingo (1994). "Reverse-Fit: A 2-optimal algorithm for packing rectangles". Algorithms — ESA '94. Přednášky z informatiky. 855. Springer Berlin Heidelberg. pp. 290–299. doi:10.1007/bfb0049416. ISBN 978-3-540-58434-6.

[KenyonRémila-14] Kenyon, Claire; Rémila, Eric (November 2000). "A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem". Matematika operačního výzkumu. 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". Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, {APPROX} 2009, and 13th International Workshop, {RANDOM} 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. 5687: 177–189. Bibcode:2009LNCS.5687..177H. doi:10.1007/978-3-642-03685-9\_14 (inactive 2020-11-26).CS1 maint: DOI neaktivní od listopadu 2020 (odkaz)

[16] Jansen, Klaus; Solis-Oba, Roberto (August 2009). "Rectangle packing with one-dimensional resource augmentation". Diskrétní optimalizace. 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 April 2012). "Approximation Algorithms for Multiple Strip Packing and Scheduking Parallel Jobs in Platforms". Discrete Mathematics, Algorithms and Applications. 03 (4): 553–586. doi:10.1142/S1793830911001413.

[18] Sviridenko, Maxim (January 2012). "A note on the Kenyon–Remila strip-packing algorithm". Dopisy o zpracování informací. 112 (1–2): 10–12. doi:10.1016/j.ipl.2011.10.003.

[JansenRau2019-19] A ^b Jansen, Klaus; Rau, Malin (2019). "Closing the Gap for Pseudo-Polynomial Strip Packing". 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 144: 62:1–62:14. doi:10.4230/LIPIcs.ESA.2019.62. S2CID 24303167.

[20] Jansen, Klaus; Thöle, Ralf (January 2010). "Approximation Algorithms for Scheduling Parallel Jobs". SIAM Journal on Computing. 39 (8): 3571–3615. doi:10.1137/080736491.

[21] Nadiradze, Giorgi; Wiese, Andreas (21 December 2015). "On approximating strip packing with a better ratio than 3/2". Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics: 1491–1510. doi:10.1137/1.9781611974331.ch102. ISBN 978-1-61197-433-1.

[22] Gálvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Khan, Arindam (2016). "Improved Pseudo-Polynomial-Time Approximation for Strip Packing". 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 65: 9:1–9:14. doi:10.4230/LIPIcs.FSTTCS.2016.9. S2CID 3205478.

[23] Jansen, Klaus; Rau, Malin (29–31 March 2017). "Improved Approximation for Two Dimensional Strip Packing with Polynomial Bounded Width". {WALCOM:} Algorithms and Computation, 11th International Conference and Workshops, {WALCOM} 2017, Hsinchu, Taiwan: 409–420. doi:10.1007/978-3-319-53925-6\_32 (inactive 2020-11-26).CS1 maint: DOI neaktivní od listopadu 2020 (odkaz)

[BakerOnline1-24] 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.

[25] Csirik, János; Woeginger, Gerhard J. (28 August 1997). "Shelf algorithms for on-line strip packing". Dopisy o zpracování informací. 63 (4): 171–175. doi:10.1016/S0020-0190(97)00120-8. ISSN 0020-0190.

[26] Hurink, Johann L.; Paulus, Jacob Jan (2007). "Online Algorithm for Parallel Job Scheduling and Strip Packing". WAOA 2007 - Approximation and Online Algorithms. Přednášky z informatiky. Springer Berlin Heidelberg. 4927: 67–74. doi:10.1007/978-3-540-77918-6_6. ISBN 978-3-540-77917-9.

[27] 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.

[HanOnline-28] A ^b Han, Xin; Iwama, Kazuo; Ye, Deshi; Zhang, Guochuan (2007). "Strip Packing vs. Bin Packing". Algorithmic Aspects in Information and Management. Přednášky z informatiky. Springer Berlin Heidelberg. 4508: 358–367. arXiv:cs/0607046. doi:10.1007/978-3-540-72870-2_34. ISBN 978-3-540-72868-9. S2CID 580.

[SeidenOnline-29] A ^b Seiden, Steven S. (2001). "On the Online Bin Packing Problem". Automata, Languages and Programming. Přednášky z informatiky. Springer Berlin Heidelberg. 2076: 237–248. doi:10.1007/3-540-48224-5_20. ISBN 978-3-540-42287-7.

[30] Brown, Donna J.; Baker, Brenda S.; Katseff, Howard P. (1 November 1982). "Lower bounds for on-line two-dimensional packing algorithms". Acta Informatica. 18 (2): 207–225. doi:10.1007/BF00264439. hdl:2142/74223. ISSN 1432-0525. S2CID 21170278.

[31] Johannes, Berit (1 October 2006). "Scheduling parallel jobs to minimize the makespan" (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.

[32] Hurink, J. L.; Paulus, J. J. (1 January 2008). "Online scheduling of parallel jobs on two machines is 2-competitive". Dopisy o operačním výzkumu. 36 (1): 51–56. doi:10.1016/j.orl.2007.06.001. ISSN 0167-6377.

[33] Kern, Walter; Paulus, Jacob Jan (2009). "A note on the lower bound for online strip packing". Dopisy o operačním výzkumu.

[34] Balogh, János; Békési, József; Galambos, Gábor (6 July 2012). "New lower bounds for certain classes of bin packing algorithms". Teoretická informatika. 440-441: 1–13. doi:10.1016/j.tcs.2012.04.017. ISSN 0304-3975.

[35] Yu, Guosong; Mao, Yanling; Xiao, Jiaoliao (1 May 2016). "A new lower bound for online strip packing". Evropský žurnál operačního výzkumu. 250 (3): 754–759. doi:10.1016/j.ejor.2015.10.012. ISSN 0377-2217.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]