제지산업에서 트리검색을 사용한 2차원 자재절단문제의 발견적 해법

Abstract

제지산업에서 2차원 자재절단문제는 길이가 무한한 롤 자재에서 여러 크기의 작은 직사각형 제품을 절단하는 문제이다. 2차원 자재절단문제의 목적은 롤 자재를 절단할 때 발생하는 비용을 최소화하고 제품의 요구 수량을 만족하는 것이다. 이 연구에서 다루는 2차원 자재절단문제는 자재의 방향과 제품의 방향이 일치해야 하는 방향성이 있는 문제이다. 절단 방법은 한쪽 모서리에서 반대쪽 모서리까지 수직으로 절단하는 길로틴 절단이다. 이 연구는 롤 자재에서 제품을 절단할 때 버려지는 부분에 대한 비용을 고려할 뿐만 아니라 절단하는 모양을 변경할 때 설비를 재설정하는 비용을 고려한다. 기존 연구는 대부분 버려지는 부분에 대한 비용만을 고려하기 때문에 현실적이지 않다. 사용된 절단패턴의 수가 많아지면 절단패턴을 변경하려고 빈번하게 설비를 멈추어야 하기 때문에 생산성이 떨어진다. 사용된 절단패턴의 수는 적을수록 좋기 때문에 이러한 점이 해법에 반영되어야 한다. 2차원 자재절단문제는 최적해를 구하는 다항식 앨고리듬이 발견되지 않은 NP-complete문제이기 때문에 문제의 크기가 커지면 최적해를 찾는 것이 어렵다. 이 연구는 깊이-우선 트리검색을 사용한 2차원 자재절단문제의 발견적 해법을 제안한다. 제안하는 해법은 사용된 절단패턴의 수를 줄이는 것을 기본으로 하기 때문에 사용된 절단패턴의 수가 제품 종류의 수를 넘지 않는다. 또한 해를 수정하여 사용된 절단 패턴의 수를 더욱 줄이는 방법을 제안한다. 이 해법은 트리검색을 사용하기 때문에 기존의 해법에 비해 버려지는 부분에 대한 비용과 절단패턴의 수에 대한 비용을 고려하여 더 나은 해를 찾을 수 있다. 문제의 크기에 따라 탐색시간이 길어질 수도 있지만 다양한 탐색 전략을 제안하여 해의 질과 계산 속도를 절충할 수 있어 현실적이다.