Harmonisk binförpackning

Harmonic bin-packing är en familj av onlinealgoritmer för bin-packing . Indata till en sådan algoritm är en lista över objekt av olika storlekar. Utgången är en packning - en uppdelning av föremålen i lådor med fast kapacitet, så att summan av storlekarna på föremålen i varje fack är som mest kapaciteten. Helst skulle vi vilja använda så få papperskorgar som möjligt, men att minimera antalet papperskorgar är ett NP-hårt problem.

De harmoniska bin-packing-algoritmerna är beroende av att dela upp föremålen i kategorier baserat på deras storlekar, efter en harmonisk progression . Det finns flera varianter av denna idé.

Harmonisk- k

Harmonic - k -algoritmen delar upp storleksintervallet $(0,1]$ harmoniskt i $k-1$ bitar $I_{j}:=(1/(j+1),1/j]$ för $1\leq j<k$ och $I_{k}:=(0,1/k]$ så att $\bigcup _{j=1}^{k}I_ {j}=(0,1]$ . Ett objekt $i\in L$ kallas ett $I_{j}$ -objekt, om ${\ displaystyle s(i)\in I_{j}}$ .

Algoritmen delar upp mängden tomma fack i $k$ oändliga klasser $B_{j}$ för ${\displaystyle 1\leq j\leq k} ,$ en facktyp för varje Objekttyp. En fack av typ $B_{j}$ används endast för fack för att packa föremål av typ $j$ . Varje fack av typ $B_{j}$ för $1\leq j<k$ kan innehålla exakt $j$$I_{j}$ - föremål. Algoritmen fungerar nu enligt följande:

• Om nästa objekt $i\in L$ är ett $I_{j}$ -objekt för $1\leq j<k$ placeras objektet i det första (endast öppna) ${\displaystyle B_{j}}-$ facket som innehåller färre än $j$ -bitar eller öppnar ett nytt om det inte finns något sådant.
• Om nästa objekt $i\in L$ är ett $I_{k}$ -objekt, placerar algoritmen det i facket av typ $B_{k}$ med Next-Fit.

Denna algoritm beskrevs först av Lee och Lee. Den har en tidskomplexitet på ${\mathcal {O}}(n\log(n))$ där n är antalet inmatade objekt. Vid varje steg finns det högst $k$ öppna fack som potentiellt kan användas för att placera objekt, dvs det är en k -gränsad rymdalgoritm.

Lee och Lee studerade också det asymptotiska approximationsförhållandet. De definierade en sekvens $\sigma _{1}:=1$ , $\sigma _{i+1}:= \sigma _{i}(\sigma _{i}+1)$ för $i\geq 1$ och bevisade att för $\sigma _{l }<k<\sigma _{l+1}$$R_{Hk }^{\infty }\leq \sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))$ gäller att . För $k\rightarrow \infty$ gäller att $R_{Hk}^{\infty }\approx 1.6910$ . Dessutom presenterade de en familj av värsta exempel på att $R_{Hk}^{ \infty }=\summa _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))$

Raffinerad-harmonisk (RH)

The Refined-Harmonic kombinerar idéer från Harmonic-k-algoritmen med idéer från Refined-First-Fit . Den placerar föremålen större än $1/3$ liknande som i Refined-First-Fit, medan de mindre föremålen placeras med Harmonic- Intuitionen för den här strategin är att minska det enorma avfallet för papperskorgar som innehåller bitar som bara är större än $displaystyle 1/2}$ {

Algoritmen klassificerar objekten med hänsyn till följande intervall: ${\displaystyle I_{1}:=(59/96,1]} ,$ I $a}:=(1/2,59/96]}$$:=$ I , $I_{b}:=(1/3,37/96]$ , ${\displaystyle I_{j}:=(1/(j+1),1/j]} ,$ för $j\in \ {3,\dots ,k-1\}$ och $I_{k}:=(0,1/k]$ . Algoritmen placerar ${\ displaystyle I_{j}}$ -objekt som i Harmonic-k, medan det följer en annan strategi för objekten i $I_{a}$ och $I_{b}$ . Det finns fyra möjligheter att packa $I_{a}$ -objekt och $I_{b}$ -artiklar i papperskorgar.

• En $I_{a}$ -bin innehåller endast ett $I_{a}$ -objekt.
• En $I_{b}$ -bin innehåller endast ett $I_{b}$ -objekt.
• An $I_{a}b$ -bin innehåller ett $I_{a}$ -objekt och ett $I_{b}$ -objekt.
• En $I_{b}b$ -bin innehåller två $I_{b}$ -objekt.

En $I_{b}'$ -bin betecknar en bin som är designad att innehålla ett andra $I_{b}$ -objekt. Algoritmen använder talen N_a, N_b, N_ab, N_bb och N_b' för att räkna antalet motsvarande fack i lösningen. Vidare, N_c= N_b+N_ab

Algoritm Förfinad-Harmonic-k för en lista L = (i_1, \dots i_n): 1. N_a = N_b = N_ab = N_bb = N_b' = N_c = 0 2. Om i_j är en I_k-bit använd då algoritmen Harmonic-k att packa det 3. annars om i_j är ett I_a-objekt då om N_b != 1, packa sedan i_j i valfri J_b-bin; N_b--; N_ab++; annars placera i_j i en ny (tom) papperskorg; N_a++; 4. annars om i_j är ett I_b-objekt så om N_b' = 1, placera då i_j i I_b'-bin; N_b' = 0; N_bb++; 5. annars, om N_bb <= 3N_c, placera i_j i en ny bin och beteckna den som en I_b'-bin; N_b' = 1 annat om N_a != 0 placera sedan i_j i valfri I_a-bin; N_a--; N_ab++;N_c++ annars placera i_j i en ny bin; N_b++;N_c++

Denna algoritm beskrevs först av Lee och Lee. De bevisade att för $k=20$ gäller att $R_{RH}^{\infty }\leq 373/228$ .

Andra varianter

Modifierad harmonisk (MH) har ett asymptotiskt förhållande $R_{MH}^{\infty }\leq 538/33\approx 1,61562$ .

Modifierad harmonisk 2 (MH2) har ett asymptotiskt förhållande ${\displaystyle R_{MH2}^{\infty }\leq 239091/148304\ca. 61217$ .

Harmonisk + 1 (H+1) har ett asymptotiskt förhållande $R_{H+1}^{\infty }\geq 1,59217$ .

Harmonisk ++ (H++) har asymptotiskt förhållande $R_{H++}^{\infty }\leq 1,58889$ och ${\displaystyle}^_{\++ infty }\geq 1.58333}$ .