1D 자재 절단 최적화

1D 자재 절단 최적화의 원리

1차원 자재 절단 문제(cutting stock problem)는 표준 길이 원자재(봉재, 파이프, 형강, 압출재)에서 필요한 조각들을 가능한 한 적은 수의 원자재로 잘라내는 방법을 찾는 문제입니다. 이 문제는 NP-난해이므로, 실무 도구들은 일반적인 작업장 주문 목록에서 최적해에 매우 근접하는 빠른 휴리스틱을 사용합니다.

First Fit Decreasing(FFD)은 모든 조각을 긴 순서로 정렬한 뒤, 각 조각을 여유 공간이 남아 있는 첫 번째 원자재에 배치합니다. 들어갈 곳이 없으면 새 원자재를 사용합니다. Best Fit Decreasing(BFD)도 조각을 내림차순으로 정렬하지만, 배치 후 남는 공간이 가장 작아지는 원자재에 각 조각을 배치하므로 일부 주문 구성에서는 빈틈없는 조합을 조금 더 잘 채울 수 있습니다.

절단할 때마다 톱날 폭(커프)만큼의 재료가 소모됩니다. 본 계산기는 같은 원자재 위의 연속한 조각 사이에 커프를 적용하므로(조각 n개에는 n − 1회 절단 필요), 보고되는 손실에서 봉 끝의 실제 자투리와 커프 손실이 구분됩니다. FFD의 경우 결과가 11/9 × 최적해 + 6/9 원자재를 절대 초과하지 않음이 이론적으로 보장되며(Dósa, 2007), 실무에서는 대개 최적이거나 최적 대비 원자재 1개 이내입니다.

이 도구를 사용하는 경우

• 표준 6 m 또는 12 m 원자재로 철근, 구조용 강재, 파이프, 알루미늄 압출재 주문 목록을 절단할 때
• 자재 발주 전에 제작 작업에 필요한 원자재 봉의 구매 수량을 산정할 때
• 공급업체가 제시한 두 가지 원자재 길이의 손실을 비교하여 더 경제적인 옵션을 선택할 때
• 봉별로 라벨이 표시된 조각이 포함된 절단 순서표를 톱 작업자에게 제공할 때
• 더 얇은 톱날 도입을 정당화하기 위해 커프 손실을 자투리 손실과 분리하여 정량화할 때

피해야 할 일반적인 실수

• 커프 무시 — 6 m 봉을 20개 조각으로 자를 때 3 mm 커프는 약 57 mm를 소모하며, 이로 인해 마지막 조각이 새 봉으로 밀려날 수 있습니다
• 원자재 길이와 조각 목록 간의 단위 혼용(원자재는 미터로, 조각은 밀리미터로 입력)
• 수량 열을 사용하지 않고 여러 조립품의 총 조각 수를 직접 입력하면 주문 목록의 검증이 어려워집니다
• 휴리스틱 결과를 안전 필수 자재 예산의 보장된 최적해로 취급 — 대규모 산업 생산에서는 열 생성(column-generation) LP 기법이 원자재를 몇 개 더 절약할 수 있습니다
• 재사용 가능한 잔재(긴 자투리)도 여기서는 손실로 집계된다는 점을 간과 — 잔재를 재사용용으로 보관한다면 보고된 손실에서 차감해야 합니다

결과 해석 방법

• 사용 원자재 수가 핵심 지표입니다 — 하한값 ⌈총 조각 길이 ÷ 원자재 길이⌉와 비교하여 배치의 효율 정도를 판단합니다
• 이용률 ~90% 이상이면 혼합 주문 목록으로서 양호하며, 95% 이상은 우수한 수준으로 보통 조각 길이가 원자재 길이와 잘 맞아떨어짐을 의미합니다
• 패턴별 손실은 어느 봉이 자투리를 갖는지 보여줍니다 — 손실 대부분이 한 봉에 몰려 있으면 보통 재사용 가능한 잔재가 생깁니다
• 커프 손실은 조각 길이가 아니라 조각 수에 비례하여 증가합니다 — 짧은 조각이 많을수록 톱날에 의한 재료 손실 비율이 커집니다
• FFD와 BFD가 같은 원자재 수를 산출하면 해당 원자재 길이에서 그 배치는 거의 확실히 최적입니다. 다르면 더 나은 쪽을 채택하면 됩니다

관련 표준 및 참고 문헌

• Gilmore & Gomory (1961) — A Linear Programming Approach to the Cutting-Stock Problem (Operations Research 9:849-859), 정확해 기법의 기초 논문
• Dósa (2007) — First Fit Decreasing의 엄밀한 최악 경우 한계: FFD(I) ≤ 11/9·OPT(I) + 6/9
• Johnson (1973) — Near-optimal bin packing algorithms (MIT), FFD/BFD 계열 휴리스틱의 고전적 분석
• 상용 원자재 길이는 철근 및 구조용 형강의 경우 일반적으로 6000 mm와 12000 mm 압연봉을 따릅니다. 최적화 전에 공급업체 규격을 확인하십시오

자주 묻는 질문

FFD와 BFD 중 어느 것을 선택해야 하나요?

둘 다 조각을 긴 순서로 정렬하며 원자재 선택 방식만 다릅니다. FFD는 공간이 있는 첫 번째 원자재를, BFD는 가장 빈틈없이 맞는 원자재를 선택합니다. 대개 같은 원자재 수가 나오며, 다를 경우 차이는 원자재 1개입니다. 클릭 한 번으로 둘 다 실행해 더 나은 배치를 채택하십시오.

커프는 어떻게 적용되나요?

커프는 같은 원자재 위의 연속한 조각 사이에 추가됩니다 — 조각 n개에는 n − 1회 절단이 필요하며, 끝부분 자투리에는 추가 절단이 필요 없습니다. 커프는 실제 톱날 또는 토치 폭으로 설정하십시오(냉간톱은 일반적으로 2-4 mm, 띠톱은 1-2 mm).

결과가 진짜 최적해보다 나쁠 수 있나요?

예, 다만 증명 가능한 작은 범위 내에서입니다. FFD는 최적 원자재 수의 11/9에 상수를 더한 것보다 많이 필요로 하지 않습니다. 작업장 규모의 주문 목록에서는 거의 항상 최적이며, 수천 개 조각의 압연소 규모 생산에서는 정확한 열 생성 솔버가 원자재를 추가로 절약할 수 있는 경우가 있습니다.