비가중 무제한 2차원 절단문제에 대한 최적-우선 분지한계 해법

• 영문명: A Best-First Branch and Bound Algorithm for Unweighted Unconstrained Two-Dimensional Cutting Problems
• 발행기관: 한국산업경영시스템학회
• 저자명: 윤기섭(Ki-Seop Yoon) 윤희권(Hee-Kwon Yoon) 강맹규(Maing-Kyu Kang)
• 간행물 정보: 『산업경영시스템학회지』제32권 제1호, 79~84쪽, 전체 6쪽
• 주제분류: 공학 > 산업공학
• 파일형태: PDF
• 발행일자: 2009.03.31

영문 초록

In this paper, a best-first branch and bound algorithm based upon the bottom-up approach for the unweighted unconstrained two-dimensional cutting problem is proposed to find the optimal solution to the problem. The algorithm uses simple and effective methods to prevent constructing duplicated patterns and reduces the searching space by dividing the branched node set. It also uses a efficient bounding strategy to fathom the set of patterns. Computational results are compared with well-known exact algorithms and demonstrate the efficiency of the proposed algorithm.

키워드

Two-Dimensional Cutting Branch And Bound Optimization