가변 크기 빈 패킹 (Variable-Sized Bin Packing)

여러 크기·비용의 빈이 주어질 때 총 빈 비용을 최소화하도록 담기.

다른 이름: Variable-Sized Bin Packing · Variable Sized Bin Packing Problem · VSBPP · 가변 크기 빈 패킹

정의

서로 다른 크기와 비용의 빈 종류가 주어졌을 때, 모든 항목을 겹치지 않게 담되 사용한 빈의 총 비용(또는 총 면적)을 최소화하도록 빈을 고르고 채운다. 표준 빈 패킹이 동일한 빈의 개수 를 줄이는 문제라면, 여기서는 어떤 크기의 빈을 쓸지 까지 고른다.

예시

빈 종류가 둘이라 하자 — A: 용량 10·비용 10, B: 용량 6·비용 7. 무게 합이 14인 항목 집합을 담을 때, A 하나로는 부족하다. A 하나 + B 하나(용량 16, 비용 17)면 충분하고, A 둘(비용 20)보다 싸다. 빈 개수 가 아니라 비용 을 최소화하므로, 큰 빈만 쌓는 것이 늘 최선은 아니다.

계열

2D 빈 패킹의 비용 가중 변형이며, 여러 재고 종류를 고르는 구조 때문에 1D 절단 재고와도 방법론적으로 닿는다.

주장 & 증거

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

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

이 항목에서 나가는 관계 2

변형 관계
가변 크기 빈 패킹 (Variable-Sized Bin Packing)에서 2D 빈 패킹로
가변 크기 빈 패킹은 빈이 여러 크기·비용으로 주어지는 빈 패킹 변형으로, 빈 개수가 아니라 총 빈 비용을 최소화한다 — Wäscher 외 유형론의 '빈 구색' 차원에서 갈린다.
증거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.
방법 공유
가변 크기 빈 패킹 (Variable-Sized Bin Packing)에서 1D 절단 재고로
가변 크기 빈 패킹과 1D 절단 재고는 '여러 종류의 재고/빈을 비용 최소로 고른다'는 구조를 공유하며, 둘 다 패턴/구성 정식화로 다뤄진다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E3 · 구조적 유추
출처
- 출처 등급: 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.

이 항목에서 나가는 관계
관계	주장	증거	등가	출처
변형 관계 가변 크기 빈 패킹 (Variable-Sized Bin Packing)에서 2D 빈 패킹로	가변 크기 빈 패킹은 빈이 여러 크기·비용으로 주어지는 빈 패킹 변형으로, 빈 개수가 아니라 총 빈 비용을 최소화한다 — Wäscher 외 유형론의 '빈 구색' 차원에서 갈린다.	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.
방법 공유 가변 크기 빈 패킹 (Variable-Sized Bin Packing)에서 1D 절단 재고로	가변 크기 빈 패킹과 1D 절단 재고는 '여러 종류의 재고/빈을 비용 최소로 고른다'는 구조를 공유하며, 둘 다 패턴/구성 정식화로 다뤄진다.	B · 서베이 / 튜토리얼 / 커뮤니티	E3 · 구조적 유추	출처 등급: 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.