2D 스트립 패킹

고정 폭의 스트립에 직사각형을 채워 사용 높이를 최소화하기.

다른 이름: 2D Strip Packing · 직사각형 스트립 패킹 · Rectangle strip packing

정의

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

예시

스트립 폭 $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]

주장 & 증거

모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.

A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.

이 항목에서 나가는 관계 9

방법 공유
2D 스트립 패킹에서 2D 불규칙 네스팅로
직사각형 스트립 패킹과 불규칙 네스팅은 배치 휴리스틱(예: 바텀-레프트)을 공유하며 같은 절단·적재 계열에 속한다; 직사각형은 직교 특수 사례다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
사용 방법
2D 스트립 패킹에서 바텀-레프트-필 (Bottom-Left Fill)로
바텀-레프트 및 바텀-레프트-필은 직사각형 스트립/패킹 레이아웃을 위해 도입된 표준 구성적 휴리스틱이다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서On genetic algorithms for the packing of polygons
  서지정보
  Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
직접 벤치마크
2D 스트립 패킹에서 2DPackLib로
2DPackLib은 2차원 직교 스트립 패킹에 직접 관련된 인스턴스를 제공한다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서2DPackLib: a two-dimensional cutting and packing library
  서지정보
  Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
사용 방법
2D 스트립 패킹에서 유전 알고리즘 (Genetic Algorithm)로
직사각형 스트립/패킹은 부품 순서·방향에 대한 유전 알고리즘 탐색으로 다뤄져 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서On genetic algorithms for the packing of polygons
  서지정보
  Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
사용 방법
2D 스트립 패킹에서 감소 우선 적합 (First-Fit Decreasing)로
레벨 기반 감소-우선 적합(FFDH 등)은 스트립 패킹의 고전적 구성적 휴리스틱이다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 스트립 패킹에서 시뮬레이티드 어닐링 (Simulated Annealing)로
스트립 패킹은 시뮬레이티드 어닐링 기반 탐색으로도 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
방법 공유
2D 스트립 패킹에서 2D 배낭 (직사각형)로
스트립 패킹과 2D 배낭은 직교 배치 핵심과 방법론을 공유한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
사용 방법
2D 스트립 패킹에서 타부 서치 (Tabu Search)로
스트립 패킹은 타부 서치 기반 탐색으로도 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 스트립 패킹에서 정수 선형 계획법 (Integer Linear Programming)로
2D 스트립 패킹은 정수 선형 계획 모델로 정식화되어 정확 해법의 기반이 된다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

이 항목에서 나가는 관계
관계	주장	증거	등가	출처
방법 공유 2D 스트립 패킹에서 2D 불규칙 네스팅로	직사각형 스트립 패킹과 불규칙 네스팅은 배치 휴리스틱(예: 바텀-레프트)을 공유하며 같은 절단·적재 계열에 속한다; 직사각형은 직교 특수 사례다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
사용 방법 2D 스트립 패킹에서 바텀-레프트-필 (Bottom-Left Fill)로	바텀-레프트 및 바텀-레프트-필은 직사각형 스트립/패킹 레이아웃을 위해 도입된 표준 구성적 휴리스틱이다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서On genetic algorithms for the packing of polygons 서지정보 Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
직접 벤치마크 2D 스트립 패킹에서 2DPackLib로	2DPackLib은 2차원 직교 스트립 패킹에 직접 관련된 인스턴스를 제공한다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서2DPackLib: a two-dimensional cutting and packing library 서지정보 Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
사용 방법 2D 스트립 패킹에서 유전 알고리즘 (Genetic Algorithm)로	직사각형 스트립/패킹은 부품 순서·방향에 대한 유전 알고리즘 탐색으로 다뤄져 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서On genetic algorithms for the packing of polygons 서지정보 Jakobs, S. (1996). On genetic algorithms for the packing of polygons. EJOR 88(1):165-181. Origin of the bottom-left-fill placement heuristic.
사용 방법 2D 스트립 패킹에서 감소 우선 적합 (First-Fit Decreasing)로	레벨 기반 감소-우선 적합(FFDH 등)은 스트립 패킹의 고전적 구성적 휴리스틱이다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 스트립 패킹에서 시뮬레이티드 어닐링 (Simulated Annealing)로	스트립 패킹은 시뮬레이티드 어닐링 기반 탐색으로도 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
방법 공유 2D 스트립 패킹에서 2D 배낭 (직사각형)로	스트립 패킹과 2D 배낭은 직교 배치 핵심과 방법론을 공유한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
사용 방법 2D 스트립 패킹에서 타부 서치 (Tabu Search)로	스트립 패킹은 타부 서치 기반 탐색으로도 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 스트립 패킹에서 정수 선형 계획법 (Integer Linear Programming)로	2D 스트립 패킹은 정수 선형 계획 모델로 정식화되어 정확 해법의 기반이 된다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

이 항목으로 들어오는 관계 3

방법 공유
2D 빈 패킹에서 2D 스트립 패킹로
2D 빈 패킹과 스트립 패킹은 구성적·정확 방법을 공유하며, 단일 빈을 채울 때 스트립 패킹이 부분문제로 자주 등장한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
일반화
2D 불규칙 네스팅에서 2D 스트립 패킹로
불규칙 네스팅은 직사각형 스트립 패킹을 일반화한다: 직사각형은 임의 다각형의 특수 사례다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유
길로틴 절단에서 2D 스트립 패킹로
길로틴 절단과 스트립 패킹은 직교 배치 방법론을 공유한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
방법 공유 2D 빈 패킹에서 2D 스트립 패킹로	2D 빈 패킹과 스트립 패킹은 구성적·정확 방법을 공유하며, 단일 빈을 채울 때 스트립 패킹이 부분문제로 자주 등장한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
일반화 2D 불규칙 네스팅에서 2D 스트립 패킹로	불규칙 네스팅은 직사각형 스트립 패킹을 일반화한다: 직사각형은 임의 다각형의 특수 사례다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유 길로틴 절단에서 2D 스트립 패킹로	길로틴 절단과 스트립 패킹은 직교 배치 방법론을 공유한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.