비가중 무제한 2차원 절단문제에 대한 최적-우선 분지한계 해법
A Best-First Branch and Bound Algorithm for Unweighted Unconstrained Two-Dimensional Cutting Problems
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (11)
- 김종수, "유비쿼터스 경영과학", pp.145~146 (2005), 박영사
- 윤기섭, "무제한 2차원 절단문제에 대해 개선된 최적-우선 분지한계 해법", 한국경영과학회지, 30(4), pp.61~70 (2005), 한국경영과학회
- Christofides, N., "An algorithm for two-dimensional cutting problems", Operations Research, 26, pp.30~44 (1977)
- Cung, V. D., "Constrained twodimensional cutting stock problems a best-first branchand-bound algorithm", International Transactions in Operational Research, 7, pp.185~210 (2000)
- G., Y. G., "A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems", Journal of the Operational Research Society, 53, pp.587~591 (2002)
- Gilmore, P. C., "A linear programming approach to the cutting-stock problem", Operations Research, 9, pp.849~859 (1961)
- Hifi, M., "The DH", KD algorithm：a hybrid approach for unconstrained two-dimensional cutting problems, 1997, pp.97, 41~52
- [URL]
- Hifi, M., "A recursive exact algorithm for weighted two-dimensional cutting", European Journal of Operational Research, 91, pp.553~564 (1996)
- Viswanathan, K. V., "Best-first search methods for constrained two-dimensional cutting stock problems", Operations Research, 41, pp.768~776 (1993)
- Wang, P. Y., "Two algorithms for constrained two-dimensional cutting stock problems", Operations Research, 31, pp.573~586 (1983)