2차원 2단계 길로틴 절단문제에 대한 정수최적화모형 및 열생성 기반 해법

Abstract

본 연구는 제지, 제철, 합판, 필름, 플라스틱, 유리 등 다양한 산업에서 발생하는 2차원 2단계 수직 길로틴 절단 문제(2-dimensional 2-stage orthogonal guillotine cutting stock problem: 이하 2D-2GCSP)에 대한 정수최적화모형과 정수최적화기법에 기초한 해법을 제시하고, 2D-2GCSP의 모형들을 비교 분석한 결과를 제시한다. 이론적으로 강성 NP-hard에 속한다는 사실이 알려져있는 2D-2GCSP는 산업 현장에서의 높은 활용도 및 중요성으로 연구가 활발히 진행되어 왔다. 본 연구는 현재까지 제안된 2D-2GCSP의 최적화 모형들을 이론적/계산적으로 분석하고 상대적으로 연구가 많이 이루어지지 않은 단계패턴모형을 활용한 휴리스틱해법과 최적해법을 제안하고자 한다.

본 논문은 변수의 개수 측면에서 지수개수모형들과 의사-다항개수모형들로 비견할 수 있는 패턴기반모형들(단계패턴모형, 전체패턴모형)과 비패턴기반모형들(호-흐름모형, 원-컷모형, 레벨패킹확장모형) 간 하한강도의 관계를 밝힌다. 모형들의 선형계획완화문제를 통해 계산할 수 있는 하한강도는 모형을 기반으로 하는 알고리즘의 효율에 직접적인 영향을 준다. 하지만 선행 연구에서 2D-2GCSP 모형들의 선형계획완화문제를 이론적으로 비교하고 분석한 사례가 없었다. 따라서 본 연구는 지금까지 제안된 최적화모형들의 하한강도를 이론적으로 분석하고 하한강도 관점에서 모형들 간 관계를 정립한다.

지수개수로 변수가 많은 패턴기반모형들의 선형계획완화문제는 열생성문제를 이용해서 효율적으로 풀 수 있다. 따라서 본 연구는 열생성방법을 사용하는 모형의 경우에는 열생성문제의 계산복잡도도 함께 분석한다. 한편, 한 모형의 선형계획완화문제가 다른 모형의 선형계획완화문제보다 더 강한 하한을 제공하더라도 문제의 계산복잡도로 인해 계산시간이 많이 필요할 수 있으므로 본 연구는 모형들 간 계산 분석을 함께 진행하고, 하한강도와 계산시간 간의 절충점(trade-off)을 다른 연구들에서 사용한 인스턴스들을 기준으로 분석한다. 이를 통해, 본 연구에서는 패턴기반모형들 중에서 제한전체패턴모형과 제한단계패턴모형이 이론적 분석에서는 제한전체패턴모형의 하한강도가 가장 좋았지만 계산 분석 결과에서는 생각보다 두 모형의 하한강도 차이가 크지 않은 반면, 제한단계패턴모형의 선형계획완화문제를 푸는 시간은 다른 모형들 대비 월등히 뛰어남을 확인할 수 있었다.

다음으로 본 연구는 2D-2GCSP의 모형들 간 이론적/계산적 관계를 분석한 결과를 통해 제한시간 동안 다른 모형들에 비해 좋은 하한을 제공한 제한단계패턴모형을 이용해서 정수가능해를 찾는 휴리스틱 알고리즘을 제안한다. 2D-2GCSP의 제한단계패턴모형은 가능한 패턴의 종류가 지수개수로 많기 때문에 이론적으로 모든 패턴을 대상으로 정수해를 구하는 것은 불가능하다. 가장 간단한 휴리스틱 알고리즘은 선형계획완화문제를 풀면서 생성된 제한된 일부의 열들만 이용해서 분지한계법(Land and Doig, 1960)을 통해 정수해를 구하는 방법이다(절단분지한계법). 하지만 선형계획완화문제를 풀면서 생성된 열 개수는 가능한 모든 열 개수에 비해 훨씬 적기 때문에 정수해의 품질을 보장하기 어렵다. 따라서 본 연구는 선형계획완화문제를 최적해까지 푼 뒤에 추가로 가능한 열들을 더 생성하는 방법을 제안한다. 또한 이 방법을 토대로 추가로 생성된 열들을 포함해서 분지한계를 진행하는 알고리즘을 제안하고(다이빙휴리스틱), 구현을 통한 결과를 분석한다. 하지만 다이빙휴리스틱 알고리즘을 진행하는 과정에서 최적해가 될 가능성이 높은 열들만 더 생성된다는 보장이 없으며, 이러한 경우에는 분지한계를 진행해야 하는 경우의 수만 늘어남에 따라 정수해의 품질은 개선되지 않으면서 계산시간만 소모할 수 있다. 따라서 본 연구에서는 추가 열들을 생성한 후, 해를 개선시킬 가능성이 높은 구역으로 탐색범위를 좁혀서 정수해를 찾는 휴리스틱 알고리즘을 함께 제시하고 두 알고리즘의 성능을 비교하고 분석한다. 실험결과를 분석한 결과 단일원자재판과 다형원자재판 모두의 경우에 대해서 두 알고리즘을 통해서 구한 가능해의 품질이 개선됨을 알 수 있었다.

마지막으로, 앞서 제안한 휴리스틱 알고리즘들의 결과값을 상한으로 이용해서 2D-2GCSP의 최적해를 구하는 분지평가 알고리즘을 설계하고 구현한다. 분지평가법은 분지한계를 진행하는 각 마디마다 열생성으로 선형계획완화문제를 푸는 방법으로, 분지된 각 마디에서 선택하는 분지전략에 따라 열생성문제의 구조가 바뀔 수 있고 이는 분지평가 알고리즘의 계산상 효율을 떨어뜨리는 요인이 된다. 따라서 본 연구는 열생성문제의 구조가 바뀌지 않도록 분지하는 전략을 제시하고 이를 바탕으로 최적해를 구하기 위한 분지평가 알고리즘을 제안한다.