2D 스트립 패킹

정의

축 정렬 직사각형들을, 폭이 고정되고 높이가 무한한 스트립에 겹치지 않게 채워 사용 높이를 최소화한다.

예시

스트립 폭 $W = 4$, 부품이 $4\times1$ 하나와 $2\times3$ 둘이라고 하자. $2\times3$ 두 개를 나란히 놓으면 폭 $2+2=4$를 채우며 높이 3을 쓰고, 그 위에 $4\times1$을 얹으면 사용 높이는 4가 된다. 면적 합 $6+6+4=16$을 폭 4로 나눈 하한과 일치하므로 최적이다.

불규칙 네스팅과의 관계

스트립 패킹은 더 넓은 네스팅 문제의 직교 특수 사례다: 모든 부품이 직사각형이면 불규칙 네스팅이 스트립 패킹으로 환원된다. 구성적 배치 휴리스틱(특히 바텀-레프트)을 공유하므로, 등가가 아니라 E2_method_shared로 기록한다 — 방법론은 겹쳐도 기하는 다르기 때문이다.

벤치마크

불규칙 네스팅(2DPackLib이 인접에 그침)과 달리, 여기서는 2DPackLib이 직접 벤치마크다: 2차원 직교 절단·적재를 대상으로 한다. [등급 A]

관련 노드

아래 깊이 1 그래프를 참고하라.