절단 재고 문제, 쉽게 풀어 보기
절단 재고 문제가 무엇인지, 왜 NP-hard인지, 그리고 1D·2D 최적화기(길로틴 vs 트루 네스팅)가 어떻게 빠르게 좋은 해를 찾는지.
절단 재고 문제란
원자재 길이(봉재, 판재, 시트)와 필요한 부재 목록이 주어지면 최소한의 원자재로 모든 부재를 잘라 내는 문제입니다. 사소해 보이지만 수학적으로는 NP-hard입니다. 부재 목록이 길어질수록 조합 수가 폭발합니다.
1D, 2D, 길로틴 절단
1D는 한 방향입니다. 파이프, 프로파일, 스터드. 2D는 폭이 더해집니다. 합판, 유리, 판금. 길로틴 절단은 끝에서 끝까지 통과하고(패널톱의 방식), 트루 네스팅은 임의 회전과 비길로틴 배치를 허용합니다(레이저와 라우터의 방식).
최적해가 드문 이유
작은 인스턴스만 동적계획법이나 정수계획법으로 정확히 풀 수 있습니다. 산업 현장은 휴리스틱에 의존합니다. First Fit Decreasing, Best Fit Decreasing, 셸프 알고리즘 등이 밀리초 단위에 최적해의 몇 퍼센트 이내로 도달합니다.
커프와 그 외 현실의 함정
모든 절단은 재료를 소모합니다. 3 mm 날 커프는 절단당 3 mm이고 50회 절단이면 조용히 150 mm를 잠식합니다. 자투리 재사용, 결 방향, 트림 손실이 포장 자체만큼 중요합니다.
내 절단 목록으로 직접 시험합니다
1D 절단 계산기는 봉재와 프로파일 목록을 최적화하고, 판재 절단 계산기는 회전과 커프를 반영한 길로틴 판재 배치를 처리합니다. 목록을 붙여 넣고 최적화 전후의 총 원자재량을 비교하세요.