빈패킹 문제

덮개/포장-문제 쌍
커버 문제 포장문제 최소 세트 커버 최대세트패킹 최소 에지 커버 최대 일치 최소 꼭지점 커버 최대 독립 집합 빈 커버 빈패킹 폴리곤 피복 직사각형 패킹
v t

빈 패킹 문제는^[1][2][3][4] 크기가 다른 품목을 사용하는 빈의 수를 최소화하는 방식으로 고정된 각 용량으로 한정된 수의 빈 또는 용기에 포장해야 하는 최적화 문제다. 문제는 컨테이너 충만, 중량 용량 제약이 있는 트럭 적재, 미디어에서의 파일 백업 생성, FPGA 반도체 칩 설계에서의 기술 매핑 등 많은 응용 프로그램을 가지고 있다.

계산적으로 문제는 NP-hard이며, 해당 의사결정 문제(항목들이 지정된 수의 빈에 들어갈 수 있는지 여부 결정)는 NP-완전하다. 최악의 경우 경도에도 불구하고, 정교한 알고리즘을 사용하여 문제의 매우 큰 예에 대한 최적의 해결책이 만들어질 수 있다. 또한 많은 근사 알고리즘이 존재한다. 예를 들어, 첫 번째 적합 알고리즘은 각 항목을 첫 번째 적합할 빈에 넣는 것을 포함하여 빠르지만 종종 최적화되지 않는 솔루션을 제공한다. θ(n log n) 시간이 필요하며, 여기서 n은 포장할 항목의 수입니다. 알고리즘은 먼저 항목 목록을 감소 순서에 따라 분류함으로써 훨씬 더 효과적일 수 있다(일명 첫 번째 적합 감소 알고리즘이라고도 함). 비록 이것이 여전히 최적의 해결책을 보장하지는 못하지만, 더 긴 목록을 위해 알고리즘의 실행 시간이 증가할 수 있다. 그러나 퍼스트핏이 최적의 솔루션을 생산할 수 있는 품목 순서는 항상 최소 한 가지 이상 존재하는 것으로 알려져 있다.^[5]

이 문제에는 2D패킹, 선형패킹, 중량별패킹, 비용별패킹 등 많은 변화가 있다. 빈 패킹 문제는 절삭 재고 문제의 특수한 사례로도 볼 수 있다. 빈의 수가 1개로 제한되고 각 품목이 부피와 값으로 특징지어질 때, 빈에 들어갈 수 있는 품목의 가치를 극대화하는 문제를 배낭문제라고 한다.

실제로 발생하는 빈 패킹의 변형은 아이템이 빈에 포장될 때 공간을 공유할 수 있는 경우다. 특히, 한 세트의 물품은 각각의 크기의 합보다 포장을 했을 때 더 적은 공간을 차지할 수 있다. 이 변형은 VM 패킹이라고^[6] 알려져 있는데, 이는 가상 머신(VM)이 서버에 패키징될 때 VM이 한 번만 저장하면 되는 페이지 때문에 총 메모리 요구량이 감소할 수 있기 때문이다. 임의로 공간을 공유할 수 있는 아이템이라면 빈 패킹 문제는 대략적인 것조차 어렵다. 그러나 가상 머신의 메모리 공유와 마찬가지로 공간 공유가 계층에 맞으면 빈 패킹 문제를 효율적으로 근사하게 추정할 수 있다.

실제로 관심을 갖는 또 다른 변종인 빈 패킹은 소위 온라인 빈 패킹이다. 여기에서 서로 다른 부피의 항목들이 순차적으로 도착하도록 되어 있고, 의사 결정자는 현재 관찰된 항목을 선택해서 포장할 것인지, 아니면 통과시킬 것인지 결정해야 한다. 각각의 결정은 회수 불능이다. 이와는 대조적으로 오프라인 빈 패킹은 추가 품목이 도착하면 더 나은 패킹을 달성하고자 품목을 재배열할 수 있다. 물론 이를 위해서는 재배열할 품목을 보관하기 위한 추가 보관이 필요하다.

형식명세서

Computers and Intractability^{[7]: 226} Garey and Johnson에서 참조 [SR1] 아래에 빈 패킹 문제를 나열한다. 그들은 그것의 결정 변형을 다음과 같이 정의한다.

인스턴스: 항목의 유한$$ 집합 $I{\displaystyle }$ ${\$${\displaystyle \mathrm{displaystyle}}$ $I},$ 각 ${\displaystyle \in }$ $I{\displaystyle }$ ${\displaystyle I}$에 대한$$ $크기{\displaystyle }$ s (${\displaystyle }$)${\displaystyle }$∈ Z${\displaystyle {}^{}}$+ ${\$$$양의 정수 빈 용량 $B{\displaystyle }$ ${\displaystyle B}$및 양의 정수 $K{\displaystyle }$ ${\displaystyty K$

질문:. $각{\displaystyle }$ $I{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$에 있는 항목의 크기 합계가 $B{\displaystyle }$ ${\displaystyle I_$${1$$}$ 이하가 되도록$$$$$$ I ${\$에 분할되어 있는가?

Note that in the literature often an equivalent notation is used, where ${\displaystyle B=1}$ and ${\displaystyle s(i)\in \mathbb {Q} \cap (0,1]}$ for each ${\displaystyle i\in I}$. Furthermore, research is mostly interested in the optimization variant, which asks for the smallest possible value of ${\displaystyle K}$. A solution is optimal if it has minimal ${\displaystyle K}$. The ${\displaystyle K}$-value for an optimal solution for a set of items ${\displaystyle I}$ is denoted by ${\displaystyle \mathrm {OPT} (I)}$ or just ${\displaystyle \mathrm {OPT} }$ if the set of 항목은 맥락에서 명확하다.

문제의 가능한 정수 선형 프로그래밍 공식은 다음과 같다.

최소화 $K{\displaystyle }$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{j}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle j_{}}$ ${\$
의 대상이 되다	$K\geq 1,}$
	${\displaystyle \sum _{i\in I}^{n}s(i)x_{ij}\leq By_{j}}}}$	${\displaystyle \forall j\in \{1,\ldots,n\}}$
	${\displaystyle \sum _{j=1}^{n}x_{ij}=1,}$	$\displaystyle \ for all i\in I}$
	${\displaystyle y_{j}\in \{0,1\}}$	${\displaystyle \forall j\in \{1,\ldots,n\}}$
	${\displaystyle x_{ij}\in \{0,1\}}$	${\displaystyle \forall I\,\forall j\in \{1,\ldots,n\}}$

여기서 ${\displaystyle y_{}}$= 빈 ${\displaystyle \mathrm{j}}$ {\$displaystyle$ j}을$($를) 사용하는 경우 1 ${\displaystyle$ $y_{j$$}=1},$ $항목$ i ${\displaystyle i}$을(를) 빈 j ${\displaystyle j}$에 ${\displaystyle \mathrm{넣는}}$ 경우$$ ${\displaystyle x_{}}$ ${\displaystyle i_{}}$=$$1 ${\displaystystyle$ j$\}.$^[8]

빈 패킹의 경도

빈 패킹 문제는 강하게 NP-완전하다. 이는 강력한 NP-완전 3파티션 문제를 빈 패킹으로 줄임으로써 증명할 수 있다.^[7]

또한 $P{\displaystyle }$= ${\displaystyle N}$ ${\displaystyle P}$ ${\displaystyle P=NP}$이(가) 아닌 한 절대 근사비가 $3{\displaystyle \mathrm{}}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle 3/2}$보다 작은 근사 알고리즘은 있을 수 없다$.$ 이는 파티션 문제를 줄임으로써 증명될 수 있다.^[9] 모든 입력 번호의 합계가 2 T인 파티션의 예를 들어, 빈 크기가 T인 빈 패킹의 인스턴스를 생성한다. 입력에 동일한 파티션이 있는 경우 최적 패킹에는 2개의 빈이 필요하므로, 근사비가 3/2 미만인 모든 알고리즘은 3개의 빈보다 작은 빈을 반환해야 하며, 이는 2개의 빈이어야 한다. 이와는 대조적으로 입력에 동일한 분할이 없는 경우, 최적 패킹은 최소 3개의 빈을 필요로 한다.

반면, 빈 패킹은 고정된 수의 $빈{\displaystyle }$ K ${\displaystyle K$에 대해 의사-폴리놈 시간에서, 고정된 빈 $용량{\displaystyle }$ B ${\displaystyle B}$에 대해서는 다항 시간에서 해결 가능하다$.$^[7]

빈 패킹을 위한 근사 알고리즘

근사 알고리즘의 성능을 측정하기 위해 문헌에서 고려한 두 가지 근사비가 있다. For a given list of items ${\displaystyle L}$ the number ${\displaystyle A(L)}$ denotes the number of bins used when algorithm ${\displaystyle A}$ is applied to list ${\displaystyle L}$, while ${\displaystyle \mathrm {OPT} (L)}$ denotes the optimum number for this list. 알고리즘 $A{\displaystyle }$ ${\displaystyle A}$에 대한 절대 최악의 경우 성능비 ${\displaystyle R_{}}$ A ${\$는 다음과 같이 정의된다$$.

${\displaystyle R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT}(L)\leq r{\text{{}모든 목록에 대해.}$

한편, 점증적 최악의 $경우비{\displaystyle {}_{}^{}}$ R ${\displaystyle A_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$는 다음과 같이 정의된다$$.

${\displaystyle R_{A}^{\infit }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT}(L)\leq r{\text{}}}}}모든 목록에 대해.$

동등하게, ${\displaystyle R_{}^{}}$ A ${\displaystyle {\mathrm{}}_{}^{}}${\$displaystyle R_{A}^{\flotty$}}}은$$(는) 일부 상수 K의 경우 모든 목록 L:^[4]

${\displaystyle A}$( ${\displaystyle L}$) ${\displaystyle \le }$ R ${\displaystyle A_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle O}$ ${\displaystyle P}$ ${\displaystyle T}$( L${\displaystyle }$)${\displaystyle }$+ ${\displaystyle K}$ ${\displaystyle A(L)\leq R_{A}^{\infit }\cdot OPT(L)+K$ .

Additionally, one can restrict the lists to those for which all items have a size of at most ${\displaystyle \alpha }$. For such lists, the bounded size performance ratios are denoted as ${\displaystyle R_{A}({\text{size}}\leq \alpha )}$ and ${\displaystyle R_{A}^{\infty }({\text$${size}\leq \cHB$ $)\}.$

빈 패킹을 위한 근사 알고리즘은 다음 두 가지 범주로 분류할 수 있다.

1. 정해진 순서대로 항목을 고려하여 쓰레기통 안에 하나씩 넣는 온라인 휴리스틱스. 이러한 휴리스틱스는 이 문제의 온라인 버전에도 적용된다.
2. 예를 들어 항목을 크기별로 정렬하여 지정된 항목 목록을 수정하는 오프라인 휴리스틱스. 이러한 알고리즘은 더 이상 이 문제의 온라인 변종에는 적용되지 않는다. 그러나, 그들은 작은 시간 복잡성의 이점을 유지하면서 향상된 근사 보증을 가지고 있다. 오프라인 휴리스틱스의 하위 범주는 점근법이다. These algorithms have an approximation guarantee of the form ${\displaystyle (1+\varepsilon )\mathrm {OPT} (L)+C}$ for some constant that may depend on ${\displaystyle 1/\varepsilon }$. For an arbitrarily large ${\displaystyle \mathrm {OPT} (L)}$ these algorithms get arbitrarily c$O{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{P}}$ ${\displaystyle \mathrm{T}}$( ${\displaystyle L}$) ${\displaystyle \mathrm {OPT} (L)}$에 손실$.$ 그러나 이는 (주변적으로) 휴리스틱 접근법에 비해 시간 복잡성이 증가하면서 발생하는 비용이다.

온라인 휴리스틱스

온라인 버전의 빈 패킹 문제에서는 아이템이 속속 도착하고, 다음 아이템을 알기 전에 아이템을 어디에 배치할 것인지, 아니면 다른 아이템이 있을지라도 (불가역) 결정을 내린다. 빈 패킹을 위한 다양한 오프라인 및 온라인 휴리스틱스 세트가 데이비드 S. 존슨의 박사 논문에서 연구되었다.^[10]

단일 클래스 알고리즘

다음과 같은 일반적인 체계를 사용하는 많은 간단한 알고리즘이 있다.

• 입력 목록의 각 항목에 대해:
  1. 항목이 현재 열려 있는 빈 중 하나에 맞으면 다음 빈 중 하나에 넣으십시오.
  2. 그렇지 않으면 새 통을 열고 새 물건을 넣는다.

알고리즘은 1단계에서 새 항목에 대해 열린 빈을 선택하는 기준에 따라 다르다(자세한 내용은 링크된 페이지 참조).

• NF(Next Fit)는 항상 하나의 열린 빈을 유지한다. 새 품목이 들어가지 않으면 현재 보관함을 닫고 새 보관함을 연다. 하나의 열린 빈만 메모리에 보관하면 되기 때문에 경계 공간 알고리즘이라는 게 장점이다. 단점은 점근사비가 2라는 점이다. In particular, ${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$, and for each ${\displaystyle N\in \mathbb {N} }$ there exists a list ${\displaystyle L}$ such that ${\displaystyle \mathrm {OPT} (L)=N}$ and ${\displayst$$yle NF(L)=2\cdot \mathrm {OPT}(L)-2$^[10] 항목 크기에 따라 점증적 근사비를 다소 개선할 수 있다: $R{\displaystyle {}_{}^{}}$ ${\displaystyle N_{}^{}}$ F${\displaystyle {}_{}^{}}$ (${\displaystyle \text{크기}\alpha }$ )${\displaystyle 2}$ 2$${\$displaystyle R_{$$NF}^{\inful }({\text{size}}\leq \alpha )\leq 2$$}$ 모든$$ $\alpha {\displaystyle }$α ${\displaystyle 1}$/ ${\displaystyle 2\mathrm{}}$ {\$displaystyle$\alpha $\geq$1/$2$$}$ ${\displaystyle {및}_{}^{}}$ R ${\displaystyle N_{}^{}}$ F${\displaystyle {\mathrm{}}_{}^{}}$ (${\displaystyle \text{크기}\alpha }$) ${\displaystyle 1}$/${\displaystyle }$(${\displaystyle 1}$ -${\displaystyle \alpha }$) ${\displaystystyleq R_{{{{}$$NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}$ for all ${\displaystyle \alpha \leq 1/2}$. For each algorithm ${\displaystyle A}$ that is an AnyFit-algorithm it holds that ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{$$NF}^{\inful }({\text{size}}\leq \alpha$ $)\}\}.$
• 넥스트-k-핏(NkF)은 넥스트-핏의 변종이지만, 하나의 빈만 열어두는 대신 알고리즘은 $마지막{\displaystyle }$ k ${\displaystyle k}$ 빈을$$ 열어두고 항목이 맞는 첫 번째 빈을 선택한다. 따라서 k-경계 공간 알고리즘이라고 한다.^[11] $k{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 2}$ ${\displaystyle k\geq$ 2$}$의 경우 NkF는 NF 결과와 비교하여 개선된 결과를 제공하지만, $k{\displaystyle }$ ${\displaystyle k}$을(를$)$ $2{\displaystyle \mathrm{}}$ {\$displaystyle$ 2$}$보다 큰 상수 값으로$$ 증가시키면 알고리즘이 최악의 동작에서 더 이상 개선되지$$ 않는다. If algorithm ${\displaystyle A}$ is an AlmostAnyFit-algorithm and ${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$ then ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/$$m}$ $.$^[10]
• 퍼스트핏(FF)은 모든 빈을 개봉한 순서대로 열어둔다. 그것은 각각의 새로운 아이템을 그것이 맞는 첫 번째 쓰레기통에 넣으려고 시도한다. Its approximation ratio is ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$, and there is a family of input lists ${\displaystyle L}$ for which ${\displaystyle FF(L)}$ matches this bound.^[12]
• BF(Best-Fit) 역시 모든 빈을 열어두지만, 각각의 새로운 아이템을 맞는 최대 부하로 빈에 넣으려고 시도한다. Its approximation ratio is idenetical to that of FF, that is: ${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$, and there is a family of input lists ${\displaystyle L}$ for which ${\displaystyle BF(L)}$ matches this bound.^[13]
• WF(Worst-Fit)는 최소 부하로 각 새 항목을 빈에 넣으려고 시도한다. It can behave as badly as Next-Fit, and will do so on the worst-case list for that ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$. Furthermore, it holds that ${\displaystyle R_{$$WF}^{\inful }({\text{size}}\leq \alpha )=R_{$$NF}^{\infit }({\text{size}}\leq \alpha$ $)\}.$ WF는 AnyFit-algorithm이기 때문에 R ${\displaystyle A_{\mathrm{}}^{}}$∞${\displaystyle {}_{}^{}}$(${\displaystyle \alpha }$)${\displaystyle }$= ${\displaystyle {}_{}^{}}$ N ${\displaystyle F_{}^{}}$ ${\displaystyle {}_{}^{}}$($){\displaysty R_{\$displaysty R_{}.$AF}^{\ft }(\alpha )=R_{$$NF}^{\ft }(\alpha )}$^[10].
• 거의 Worst-Fit(AWF)는 두 번째로 가장 빈 빈 빈 빈 빈 빈칸(또는 그러한 빈 빈 칸이 두 개 있는 경우 가장 빈 빈 빈 빈 빈 칸) 안에 각각의 새 항목을 넣으려고 시도한다. 맞지 않으면 가장 빈 것을 시도한다. 그것은 $[\$디스플레이 $스타일 17/10}$의 점증상 최악의 경우 비율을 가지고 있다$.$^[10]

존슨은 이러한 결과를 일반화하기 위해 애니핏 알고리즘과 거의 모든 적합 알고리즘이라는 두 가지 등급의 온라인 휴리스틱스를 도입했다.^{[4]: 470}

• AnyFit(AF) 알고리즘에서 현재 비어 있지 않은 빈이₁ B,...,B인_j 경우 현재 항목이₁ B,...,B_j 중 하나에 맞지 않는 한 B로_j+1 포장되지 않는다. FF, WF, BF 및 AWF 알고리즘은 이 조건을 만족시킨다. Johnson은 AnyFit 알고리즘 A와 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$에 대해 다음과 같이 증명했다$.$

${\displaystyle R_{$$FF}^{\infit }(\alpha )\leq R_{A}^{\infit }(\alpha )\leq R_{{}}{\infit }}{\infitty }(\alpha )\leq R_{{}$$WF}^{\ft }(\alpha )}$.

• BearAnyFit(AAF) 알고리즘에서 현재 비어 있지 않은 빈이 B₁,..., B_j, 그리고 이러한 빈 중 B가_k 가장 작은 부하를 가진 고유 빈이라면, 현재 항목은 왼쪽의 빈에 맞지 않는 한 B로_k 포장되지 않을 것이다. FF, BF, AWF 알고리즘은 이 조건을 만족시키지만 WF는 만족하지 못한다. Johnson은 AAF 알고리즘 A와 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$에 대해 다음과 같이 증명했다$.$

${\displaystyle R_{A}^{\infit }(\alpha )=R_{{}$$FF}^{\ft }}(\alpha )}$특히$$: ${\displaystyle R_{}^{}}$ A ${\displaystyle {}_{}^{}}$= 1${\displaystyle .7}$ ${\displaystyle R_{A}^{\fty }=1.7}$.

정제된 알고리즘

AnyFit가 아닌 휴리스틱스를 사용하면 더 나은 근사비가 가능하다. 이러한 휴리스틱스는 보통 서로 다른 크기의 항목에 전용으로 여러 클래스의 열린 빈을 보관한다(자세한 내용은 링크된 페이지 참조).

• Refined-first-fit bin packing (RFF) partitions the item sizes into four ranges: ${\displaystyle (1/2,1]}$, ${\displaystyle (2/5,1/2]}$, ${\displaystyle (1/3,2/5]}$, and ${\displaystyle (0,1/3]}$. Similarly, the bins are categorized into four classes. 다음 항목 $i{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle L}$ ${\displaystyle i\in L}$은(는) 해당 클래스에 먼저 할당된다$$. 그 클래스 안에서는 퍼스트핏을 사용하여 빈에 할당된다. 이 알고리즘은 현재 항목이 열린 빈 안에 들어 있음에도 불구하고 새로운 빈을 열 수 있으므로 Any-Fit 알고리즘이 아니라는 점에 유의하십시오. 이 알고리즘은 먼저 앤드류 Chi-Chih Yao,[14]에 의해 그것이 OPT⋅≤(5/3)(L)RFF에 대한 근사치 보증 기간이(L)+5{\displaystyle RFF(L)\leq(5/3)\cdot \mathrm{오피티}(L)+5}과 RFF(나는 km그리고 4.9초 만)과 목록의 가족은 나는 k{\displaystyle L_{km그리고 4.9초 만}}을 증명했다)(5/3)OPT(선 보였습니다. l${\displaystyle k_{}}$)${\displaystyle }$+ ${\displaystyle 1}$/ ${\displaystyle 3\mathrm{}}$ ${\displaystyle RFF(L_{k}}=(5/3)\mathrm {OPT}(L_{k})+3}$ for$$ ${\displaystyle \mathrm{OPT}(L}$)${\displaystyle }$= ${\displaystyle \mathrm{6k}}$+ ${\displaystyle 1}$ ${\displaystyle \mathrmatrm {OPT}(L)=6k+1$
• 크기의 간격,(0,1]{(0,1]}나는 j k− 1{\displaystyle k-1}는 조화 수열에 따라=(1/(j+1\displaystyle)Harmonic-k 파티션 1≤ j<>1/j]{\displaystyle I_{j}:=(1/(j+1),1/j 해결};k{\displaystyle 1\leq j<, k}과 나는 k:=(0,1/k]{\displayst.I_ yle${$${\displaystyle \underset{}{\overset{}{k}}}$$:=(0$$,1/k])$ $\bigcup {\displaystyle \underset{}{\overset{}{}}}$ j${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle I_{}}$ j${\displaystyle {}_{}}$=${\displaystyle }$( 0${\displaystyle ,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle \bigcup _{j=$1}^{$k}.$$I_{j}=$ ($0,1$ 이 알고리즘은 리와 리에 의해 처음 설명되었다.^[15] $O{\displaystyle \mathcal{}(L}$ ${\displaystyle log}$ ${\displaystyle }$( L$)){\displaystyle${\$mathcal{O}(L \log(L ))}$의 시간 복잡성을 가지며$$, 각 단계마다 잠재적으로 항목을 배치하는 데 사용할 수 있는 $최대{\displaystyle }$ k$${\$displaystyle$$k$$}$ 오픈$$ 빈이 있다. $즉{\displaystyle }$, k$${\$styled$ 공간$$ 알고리즘이다. $k{\displaystyle }$→ ${\displaystyle \mathrm{\infty }}$ ${\displaystyle k\rightarrow \infit }$의 경우$$근사비는 $R{\displaystyle {}_{}^{}}$ ${\displaystyle H_{}^{}}$ ${\displaystyle k_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle 1.6910}$ ${\displaysty R_{Hk}^{\infty }\약 1.6910$을 만족하며, 증상이 없을 정도로 팽팽하다.
• 정제-화합성은 하모니-k의 아이디어와 정제-퍼스트-핏의 아이디어를 결합한다. $1{\displaystyle \mathrm{}}$/ ${\displaystyle 3\mathrm{}}$ ${\displaystyle 1/3}$보다 큰 항목은 정제-퍼스트핏과 유사하게$$ 배치하고, 작은 항목은 하모닉-k를 사용하여 배치한다. 이 전략의 직관은 $단지{\displaystyle \mathrm{}}$1/$[\디스플레이 스타일$ 1/$2]$보다 큰 조각이 들어 있는 쓰레기통을 위한 거대한 낭비를 줄이는 것이다$.$ 이 알고리즘은 처음에 이씨와 이씨가 기술한 것이다.^[15] $그들$은 k${\displaystyle }$= ${\displaystyle 20}$ ${\displaystyle k=20}$에 대해 $R{\displaystyle {}_{}^{}}$ ${\displaystyle R_{}^{}}$ R ${\displaystyle H_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle 373}$/ ${\displaystyle 228}$ ${\displaystyle R_{}$를 보유한다는 것을 증명했다.$RH}^{\npty }\leq 373/228}$.

온라인 알고리즘에 대한 일반 하한

야오밍은^[14] $1980년{\displaystyle \mathrm{}}$ 3$[\displaystyle 3/2}$보다 작은 점증적 경쟁률을 가진 온라인 알고리즘이 없다는 것을 증명했다$.$ 브라운과^[16] 량은^[17] 이것을${\displaystyle \mathrm{}}1$.$[\displaystyle$ 1.53635$]$로 개선했고$,$ 이후 $블리에트$의 1.$[\displaysty1.54014]$로 개선되었다.^[18] 2012년 베케시와 갈람보스에^[19] 의해 이 하한선이 다시 ${\displaystyle 248/161\mathrm{}\approx }$ 1.$[\displaystyle 248/161\$ 약$1.54037]$로 개선되었다$.$

비교표

알고리즘.	근사보증	최악의 경우 $목록{\displaystyle }$ L ${\displaystyle L}$	시간 복합성
넥스트핏(NF)	${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT}(L)-1}$[10]	${\displaystyle NF(L)=2\cdot \mathrm {OPT}(L)-2}$[10]	${\displaystyle {\mathcal{O}(L )}$
퍼스트핏(FF)	${\displaystyle FF(L)\leq \lploor 1.7\mathrm {OPT}(L)\rfloor }$[12]	${\displaystyle FF(L)=\lfloor 1.7\mathrm {OPT}(L)\rfloor }$[12]	${\displaystyle {\mathcal{O}(L \log(L )})}$[10]
베스트핏(BF)	${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT}(L)\rfloor }$[13]	${\displaystyle BF(L)=\lploor 1.7\mathrm {OPT}(L)\rfloor }$[13]	${\displaystyle {\mathcal{O}(L \log(L )})}$[10]
WF(Worst-Fit	${\displaystyle WF(L)\leq 2\cdot \mathrm {OPT}(L)-1}$[10]	${\displaystyle WF(L)=2\cdot \mathrm {OPT}(L)-2}$[10]	${\displaystyle {\mathcal{O}(L \log(L )})}$[10]
거의 와스트핏(AWF)	${\displaystyle R_{AWF}^{\infully }\leq 17/10}$[10]	${\displaystyle R_{AWF}^{\inful }=17/10}$[10]	${\displaystyle {\mathcal{O}(L \log(L )})}$[10]
정제-퍼스트핏(RFF)	${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT}(L)+5}$[14]	${\displaystyle RFF(L)=(5/3)\mathrm {OPT} (L)+1/3}$ (for ${\displaystyle \mathrm {OPT} (L)=6k+1}$)[14]	${\displaystyle {\mathcal{O}(L \log(L )})}$[14]
하모니-k (Hk)	${\displaystyle {}_{}^{}}$$R$ ${\displaystyle H_{}^{}}$ ${\displaystyle k_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle 1.69103}$ ${\displaystyle R_{Hk}^{\\nft }\leq 1.69103}$ k →$$ $displaysty$ k$\rightarrow \inft}$	${\displaystyle R_{Hk}^{\nft }\geq 1.69103}$[15]	${\displaystyle {\mathcal{O}(L \log(L )})$[15]
정제 고조파(RH)	${\displaystyle R_{RH}^{\npty }\leq 373/228\약 1.63597}$[15]		${\displaystyle {\mathcal{O}(L )}$[15]
수정된 고조파(MH)	${\displaystyle R_{MH}^{\inful }\leq 538/33\약 1.61562}$[20]
수정된 고조파 2(MH2)	${\displaystyle R_{MH2}^{\\ft }\leq 239091/148304\약 1.61217}$[20]
고조파 + 1(H+1)		${\displaystyle R_{H+1}^{\nft }\geq 1.59217}$[21]
고조파 ++(H++)	${\displaystyle R_{H++}^{\\nft }\leq 1.5889}$[21]	${\displaystyle R_{H++}^{\\infit }\geq 1.58333}$[21]

오프라인 알고리즘

오프라인 버전의 빈 패킹에서 알고리즘은 모든 항목을 빈에 넣기 전에 볼 수 있다. 이를 통해 개선된 근사 비율을 달성할 수 있다.

곱셈 근사

오프라인 알고리즘에서 사용되는 가장 간단한 기술은 다음과 같다.

• 내림차순으로 입력 목록 정렬
• 순서 목록에서 온라인 알고리즘을 실행하십시오.

Johnson은^[10] 내림차순으로 정렬된 목록에서 실행되는 AnyFit 알고리즘 A의 점증적 근사비가

${\displaystyle 1.22}$ ${\displaystyle \approx }$ ${\displaystyle \frac{11}{}}$ 9 ${\displaystyle \le }$ ${\displaystyle R\frac{\mathrm{}}{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle \frac{5}{}}$ = 1${\displaystyle .25}${\$displaystyle$1$.22\$약 {\$frac {11}{9}}\leq R_{A}^{\$flq {$5}{4}}=1.25$ .

이 제품군의 일부 알고리즘은 다음과 같다(자세한 내용은 링크된 페이지 참조):

• First-Fit-decreaking(FFD) - 내림차순으로 항목을 주문한 다음 First-Fit을 호출하십시오. 근사비는 $F{\displaystyle }$ ${\displaystyle F}$ ${\displaystyle D}$( ${\displaystyle I}$)${\displaystyle }$= ${\displaystyle 11}$/ 9 ${\displaystyle \mathrm{O}}$ ${\displaystyle P\mathrm{}}$ ${\displaystyle \mathrm{T}}$( ${\displaystyle I}$)${\displaystyle }$+ 6${\displaystyle }$/ ${\displaystyle 9\mathrm{}}$ ${\displaystyle FFD(I)=11/9\mathrm {OPT} (I$)+6$/9$이며, 이것은 타이트하다.^[22]
• NFD(Next-Fit-Decreaming) - 내림차순으로 항목을 주문하고 Next-Fit을 호출한다. 대략적인 비율은 최악의 경우 1.7에 약간 못 미친다.^[23] 그것은 또한 확률적으로 분석되었다.^[24] 넥스트핏은 리스트를 같은 수의 빈에 역순으로 포장한다. 따라서 Next-Fit-Accepting은 Next-Fit-Accepting과 동일한 성능을 갖는다.^[25]
• 수정된 퍼스트핏-감소(MFFD)^[26] - 크기가 1/2빈 이하, 크기가 1/3빈 이하, 크기가 1/6빈 이하, 크기가 작은 품목에 해당하는 대, 중, 소, 소의 4가지 등급으로 분류하여 빈 반 이상 품목의 FFD 개선 근사보장은 $M{\displaystyle }$ ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle D}$( ${\displaystyle I}$) ${\displaystyle \le }$( ${\displaystyle 71}$/ ${\displaystyle 60}$) ${\displaystyle \mathrm{O}}$ ${\displaystyle \mathrm{P}}$ ${\displaystyle \mathrm{T}}$( ${\displaystyle I}$)${\displaystyle }$+ 1 ${\displaystyle MFFD(I)\leq (71/60)\mathrm {OPT} (I)+1}$ 입니다$.$^[27]

페르난데스 데 라 베가와 루에커는^[28] 빈 패킹을 위한 PTAS를 제시했다. 모든 ε<>를 사용하여 들어 0{\displaystyle \varepsilon>0}, 그들의 알고리즘 대부분의(1+ε)OPT+}와 시간에)O(n로그 ⁡(1/ε)를 운영한다. 크기를 해결책 1{\displaystyle(1+\varepsilon)\mathrm{오피티}+1+Oε({\displaystyle{{O\mathcal}}(n\log(1/\varepsilon))+{{O\mathcal}}_{\varepsilon}(1을 찾았다.)}, 여기서 $O{\displaystyle {\mathcal{}}_{}}$ ${\displaystyle {\epsilon }_{}}$( $){\displaystyle {\mathcal {O}_{\barepsilon }(1)$은 $오직{\displaystyle \mathrm{}}$1/${\displaystyle \epsilon }$ ${\displaystyle$ 1$/\barepsilon }$에만 의존하는 함수를 의미한다$.$ 이 알고리즘은 적응형 입력 반올림 방법을 발명했다. 입력 번호는 그룹화하여 각 그룹의 최대값으로 반올림한다. 이것은 적은 수의 서로 다른 크기의 인스턴스를 산출하는데, 이것은 정확히 구성 선형 프로그램을 사용하여 해결할 수 있다.^[29]

첨가제 근사치

The Karmarkar-Karp bin packing algorithm finds a solution with size at most ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(OPT))}$, and runs in time polynomial in ${\displaystyle n}$ (the polynomial has a high degree - at least 8).

Rothvoss는^[30] 최대 ${\displaystyle \mathrm{OP}}$ ${\displaystyle \mathrm{T}}$+ ${\displaystyle O}$(${\displaystyle \mathrm{로그}}$ ${\displaystyle }$( ${\displaystyle O\mathrm{}}$ P ${\displaystyle \mathrm{T}}$) ${\displaystyle \cdot }$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ (${\displaystyle O\mathrm{}}$ P ${\displaystyle \mathrm{T}}$) ${\displaystyle \mathrm {OPT} +O(\mathrm {OPT} )\cdot \log \log(\mathrmatrm {OPT}$)를$$ 사용하여 솔루션을 생성하는 알고리즘을 제시했다.

Hobberg와 Rothvoss는^[31] 이 알고리즘을 ${\displaystyle \mathrm{개선}}$하여 최대 O${\displaystyle \mathrm{P}}$ ${\displaystyle T}$+ O ( ${\displaystyle 로그\mathrm{}}$ ${\displaystyle }$( ${\displaystyle \mathrm{O}\mathrm{P}}$ T )${\displaystyle \mathrm {OPT} +O(\log(\mathrm {OPT} ))}$개의$$ 빈이 있는 솔루션을 생성했다. 알고리즘은 랜덤화되며, $실행{\displaystyle }$ 시간은 n ${\displaystyle$ n$}$에서 다항식이다$.$

비교표

알고리즘.	근사보증	최악의 경우
퍼스트핏-감소(FFD)	${\displaystyle FFD(I)\leq 11/9\mathrm {OPT}(I)+6/9}$[22]	${\displaystyle FFD(I)=11/9\mathrm {OPT}(I)+6/9}$[22]
수정된 첫 번째 적합치 감소(MFFD)	${\displaystyle MFFD(I)\leq(71/60)\mathrm {OPT}(I)+1}$[27]	${\displaystyle R_{MFFD}^{\\infit }\geq 71/60}$[26]
카르마르카르와 카르프[32]	${\displaystyle KK(I)\leq OPT(I)+O(\log ^{2}{OPT(I)}}$
로스보스[30]	${\displaystyle HB(I)\leq OPT(I)+O(\log {OPT(I)}\log \log {OPT(I)}}$
호베르그와 로스보스[31]	${\displaystyle HB(I)\leq OPT(I)+O(\log {OPT(I)}}$

정확한 알고리즘

마르텔로와 토스는^[33] MTP라 불리는 1차원 빈패킹 문제에 대한 정확한 알고리즘을 개발했다. 더 빠른 대안은 2002년^[34] Korf가 제안한 빈완성 알고리즘이다. 그리고 이후 개선되었다.^[35]

슈라이버와 코프는 2013년 추가 개선안을 제시했다.^[36] 새로운 개선된 빈 완성 알고리즘은 100개 항목의 비종속적인 문제에서 빈 완결보다 최대 5배 이상 빠른 것으로 나타났으며, 최적의 해결책으로 빈이 20개 미만인 문제에서 벨로프, 셰이타우어의 BCP(Branch-and-Cut-and-Price) 알고리즘을 능가한다. 어떤 알고리즘이 가장 잘 수행되느냐에 따라 항목의 수, 최적의 빈 수, 최적 솔루션에서 사용되지 않는 공간, 가치 정밀도와 같은 문제 속성에 따라 달라진다.

크기가 서로 다른 소수

bin packing의 특별한 경우는 품목 크기가 다른 d가 적은 경우다. 사이즈별로 여러 가지 품목이 있을 수 있다. 이 경우는 고다중성 빈 패킹이라고도 하며, 일반적인 문제보다 더 효율적인 알고리즘을 인정하고 있다.

빈의 카디널리티 제약 조건

빈에 카디널리티 제약이 있는 빈 패킹의 변종이 있는데, 각 빈은 일부 고정 정수 k에 대해 최대 k개의 항목을 포함할 수 있다.

• Krause, Shen, Schwetman은^[37] 이 문제를 최적의 작업 스케줄링의 변형이라고 소개한다: 컴퓨터에는 약간의 k 프로세서가 있다. 단위 시간(1)이 걸리지만 메모리 요구 사항은 다른 n개의 작업이 있다. 각 시간 단위는 단일 빈으로 간주된다. 목표는 가능한 적은 수의 빈(=시간 단위)을 사용하는 동시에 각 빈에서 최대 k개의 작업이 실행되도록 하는 것이다. 이들은 최대 2 ${\displaystyle O}$ ${\displaystyle P}$ T ${\displaystyle 2OPT}$개의$$ 빈이 있는 솔루션을 찾는 몇 가지 경험적 알고리즘을 제시한다.
• Kelerer와 Perschy는^[38] 런타임 $O{\displaystyle }$(${\displaystyle {n\mathrm{}}^{}}$ 2 ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle$ O$(n^{2}\log {n}}}}$을(를) 사용하여 알고리즘을 제시하며$,$ 이 알고리즘은 최대 ⌈ ${\displaystyle 3\frac{\mathrm{}}{}}$ ${\displaystyle O\mathrm{}}$ ${\displaystyle \mathrm{P}}$ ${\displaystyle \rceil }$ ${\displaystyle \lceil {3}{3}}{$2}}\$mathRM {rceil }$bins$$} b} bins. 그들의 알고리즘은 OPT에 대한 이진 검색을 수행한다. 검색된 모든 값 m에 대해 3m/2 bin으로 항목을 포장하려고 시도한다.

비첨가함수

bin-packing 모델을 보다 일반적인 비용 및 부하 기능으로 확장하는 다양한 방법이 있다.

• 아닐리, 브라멜리, 심치레비는^[39] 쓰레기통에 있는 물건의 수의 오목함수인 세팅을 연구한다. 빈의 수보다는 총비용을 최소화하는 것이 목적이다. 그들은 다음 맞춤을 증가시키는 빈 패킹이 최대 7/4의 절대 최악의 경우 근사비를 달성하고 오목 및 단조로운 비용 함수에 대해 점증적 최악의 경우비 1.691을 달성한다는 것을 보여준다.
• 코헨, 켈러, 미로키, 자디모그하담은^[40] 사전에 아이템의 크기를 알 수 없는 설정을 연구하지만, 무작위 변수다. 이는 특히 클라우드 컴퓨팅 환경에서 일반적이다. 특정 사용자가 필요로 하는 자원의 양에 상한선이 있지만, 대부분의 사용자는 용량보다 훨씬 적게 사용한다. 따라서 클라우드 관리자는 약간의 오버 커밋을 통해 많은 이점을 얻을 수 있다. 이것은 우연 제약조건이 있는 빈 패킹의 변형을 유도한다: 각 빈의 크기 합계가 최대 B일 확률은 최소한 p여야 한다. 여기서 p는 고정 상수(표준 빈 패킹은 p=1에 해당한다) 그들은, 가벼운 가정 하에서, 이 문제는 각 빈의 "부하"가 항목의 합이 아니라 그것의 특정 하위 함수에 해당하는 서브모듈러 빈 패킹 문제와 동등하다는 것을 보여준다.

관련 문제

빈 패킹 문제에서는 빈의 크기가 고정되어 있으며, 그 수를 확대할 수 있다(그러나 가능한 한 작아야 한다).

이와는 대조적으로, 다방향 번호 분할 문제에서는 빈의 수가 고정되어 있고 그 크기가 커질 수 있다. 목표는 빈 크기가 가능한 거의 동일한 파티션을 찾는 것이다(다중 프로세서 스케줄링 문제 또는 최소 제조 공정 문제라는 변종에서 목표는 특히 가장 큰 빈의 크기를 최소화하는 것이다).

역빈패킹 문제에서는 빈의 수와 크기가 모두 고정되어 있지만, 품목의 크기는 변경할 수 있다.^[41] 목표는 품목 크기 벡터에 대한 최소 동요를 달성하여 모든 품목이 규정된 수의 빈에 포장될 수 있도록 하는 것이다.

최대 자원 빈 포장 문제에서 목표는 사용된 빈의 수를 최대화하는 것이다.^[42] 즉, 빈의 일부 주문의 경우, 더 늦은 빈의 어떤 항목도 이전 빈에 들어맞지 않는다. 이중 문제에서는 빈의 개수가 고정되어 있으며, 나머지 항목이 채워지지 않는 빈에 들어가지 않도록 빈의 총 개수나 총 크기를 최소화하는 것이 목표다.

빈 덮개 문제에서 빈 크기는 아래에서 경계한다. 목표는 각 빈의 총 크기가 최소한 주어진 임계값으로 되도록 사용된 빈의 수를 최대화하는 것이다.

공평하게 분리할 수 없는 안건배분의 문제(공정품목배분의 변종)에서 항목은 잡일을 나타내며, 각각의 안건에 다른 난이도를 귀속시키는 사람들이 있다. 목표는 각 개인에게 총 난이도를 상회하는 일련의 집안일을 할당하는 것이다(즉, 각 사람은 쓰레기통에 해당한다. 이 문제에도 빈 패킹의 많은 기법이 사용된다.^[43]

단두대 절단 문제에서 품목과 '빈'은 모두 1차원 숫자가 아닌 2차원 사각형이며, 종단간 절단을 이용해 해당 품목을 쓰레기통에서 잘라내야 한다.

이기적인 빈 패킹 문제에서 각 아이템은 비용을 최소화하고자 하는 선수다.^[44]

또한 최소로 해야 할 비용이 빈의 수가 아니라 각 빈의 항목 수의 특정한 오목함수인 빈 패킹의 변종도 있다.^[45]

다른 변형으로는 2차원 빈 패킹,^[46] 3차원 빈 패킹,^[47] 배달이 가능한 빈 패킹,^[48]

구현

• 온라인: 1D 및 2D 빈 패킹에 대한 경험적 접근 시각화
• 파이톤: 빈패킹 패키지는 (i)항목을 일정한 수의 빈으로 포장하고, (ii)항목을 일정한 크기의 낮은 수의 빈으로 포장하는 두 가지 전형적인 빈패킹 문제를 해결하기 위한 탐욕스러운 알고리즘을 포함하고 있다.^[49]
• C++: 빈패킹 패키지에는 테스트 데이터뿐만 아니라 다양한 탐욕 알고리즘이 포함되어 있다.
• OR-tools 패키지에는 Python, C#, Java의 래퍼와 함께 C++의 빈 패킹 알고리즘이 포함되어 있다.
• C: 결과 및 이미지와 함께 C에서 대략적인 7가지 빈 패킹 알고리즘 구현
• PHP: 지정된 크기 제한을 초과하지 않고 파일을 포장하는 PHP 클래스
• Haskell: FFD와 MFFD를 포함한 여러 빈 패킹 휴리스틱스의 구현.
• C: Fpart : 파일 팩을 위한 오픈 소스 명령줄 도구(C, BSD 라이센스)
• C#: Bin Packing and Cutting Stock Solver
• Java: 카파프 - 절단 및 패킹 알고리즘 연구 프레임워크(다수의 빈 패킹 알고리즘 및 테스트 데이터 포함)

참조