길로틴 절단

한쪽 끝에서 반대쪽 끝까지 곧게 자르는 제약이 붙은 직교 절단.

다른 이름: Guillotine Cutting · 길로틴 컷 · Guillotine-cut packing

정의

각 절단이 현재 조각의 한 변에서 마주 보는 변까지 곧게 이어져야 한다는 제약 아래 직사각형을 자르거나 배치하는 직교 절단·적재 문제.

예시

패널 $4\times4$ 에서 먼저 한 변에서 마주 보는 변까지 가로로 곧게 자르면 $4\times1$ 과 $4\times3$ 으로 나뉘고, 이어 $4\times3$ 을 세로로 잘라 $2\times3$ 둘로 나눌 수 있다 — 매 절단이 조각의 변에서 변까지 이어지므로 길로틴 제약을 만족한다. 반대로 가운데에 한 조각이 둘러싸이도록 박힌 “바람개비(pinwheel)” 배치는 단 한 번의 직선 절단으로 분리되지 않아 길로틴 방식으로는 만들 수 없다.

왜 중요한가

길로틴 제약은 임의적이지 않다 — 패널 톱, 유리 절단기, 종이 재단기 같은 많은 절단 기계가 변에서 변까지의 직선 절단만 가능하다. 이 재귀적 구조는 동적 계획법과 잘 맞는다.

주장 & 증거

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

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

이 항목에서 나가는 관계 8

변형 관계
길로틴 절단에서 2D 빈 패킹로
길로틴 절단은 절단이 변에서 변까지 직선이어야 한다는 추가 제약이 붙은 2D 직교 절단·적재의 변형이다.
증거A · 동료심사 논문 / 공식 문서
등가E1 · 같은 기반, 다른 부가 제약
출처
- 출처 등급: 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.
사용 방법
길로틴 절단에서 동적 계획법 (Dynamic Programming)로
길로틴 패턴은 재귀적 분할 구조 덕분에 동적 계획법으로 효율적으로 다룰 수 있다(Gilmore–Gomory).
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Multistage Cutting Stock Problems of Two and More Dimensions
  서지정보
  Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
방법 공유
길로틴 절단에서 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.
사용 방법
길로틴 절단에서 열 생성 (Column Generation)로
Gilmore & Gomory는 2차원 길로틴 절단 재고를 위해 열 생성/패턴 생성 접근을 확장했다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Multistage Cutting Stock Problems of Two and More Dimensions
  서지정보
  Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
사용 방법
길로틴 절단에서 유전 알고리즘 (Genetic Algorithm)로
길로틴 절단·패널 재단은 유전 알고리즘 등 메타휴리스틱으로도 다뤄져 왔다.
증거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.
사용 방법
길로틴 절단에서 분기 한정 (Branch and Bound)로
길로틴 절단의 정확 접근은 분기 한정으로 보고되어 왔다.
증거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.
인접 벤치마크
길로틴 절단에서 2DPackLib로
2DPackLib의 직교 인스턴스 중 일부는 길로틴 변형과 관련되어 인접 벤치마크로 볼 수 있다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: 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 빈 패킹로	길로틴 절단은 절단이 변에서 변까지 직선이어야 한다는 추가 제약이 붙은 2D 직교 절단·적재의 변형이다.	A · 동료심사 논문 / 공식 문서	E1 · 같은 기반, 다른 부가 제약	출처 등급: 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.
사용 방법 길로틴 절단에서 동적 계획법 (Dynamic Programming)로	길로틴 패턴은 재귀적 분할 구조 덕분에 동적 계획법으로 효율적으로 다룰 수 있다(Gilmore–Gomory).	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Multistage Cutting Stock Problems of Two and More Dimensions 서지정보 Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
방법 공유 길로틴 절단에서 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.
사용 방법 길로틴 절단에서 열 생성 (Column Generation)로	Gilmore & Gomory는 2차원 길로틴 절단 재고를 위해 열 생성/패턴 생성 접근을 확장했다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Multistage Cutting Stock Problems of Two and More Dimensions 서지정보 Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
사용 방법 길로틴 절단에서 유전 알고리즘 (Genetic Algorithm)로	길로틴 절단·패널 재단은 유전 알고리즘 등 메타휴리스틱으로도 다뤄져 왔다.	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.
사용 방법 길로틴 절단에서 분기 한정 (Branch and Bound)로	길로틴 절단의 정확 접근은 분기 한정으로 보고되어 왔다.	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.
인접 벤치마크 길로틴 절단에서 2DPackLib로	2DPackLib의 직교 인스턴스 중 일부는 길로틴 변형과 관련되어 인접 벤치마크로 볼 수 있다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: 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.

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

산업 사례
목재 패널 절단에서 길로틴 절단로
목재 패널 절단은 패널 톱의 변-대-변 직선 절단 제약 때문에 길로틴 절단의 산업적 사례다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E1 · 같은 기반, 다른 부가 제약
출처
- 출처 등급: 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.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
산업 사례 목재 패널 절단에서 길로틴 절단로	목재 패널 절단은 패널 톱의 변-대-변 직선 절단 제약 때문에 길로틴 절단의 산업적 사례다.	B · 서베이 / 튜토리얼 / 커뮤니티	E1 · 같은 기반, 다른 부가 제약	출처 등급: 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.