Optimal Two-Section Layouts for the Two-Dimensional Cutting Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
When generating layout schemes, both the material usage and practicality of the cutting process should beconsidered. This paper presents a two-section algorithm for generating guillotine-cutting schemes ofrectangular blanks. It simplifies the cutting process by allowing only one size of blanks to appear in anyrectangular block. The algorithm uses an implicit enumeration and a linear programming optimal cuttingscheme to maximize the material usage. The algorithm was tested on some benchmark problems in theliterature, and compared with the three types of layout scheme algorithm. The experimental results show thatthe algorithm is effective both in computation time and in material usage.
Abstract
When generating layout schemes, both the material usage and practicality of the cutting process should beconsidered. This paper presents a two-section algorithm for generating guillotine-cutting schemes ofrectangular blanks. It simplifies the cutting process by allowing only one size of blanks to appear in anyrectangular block. The algorithm uses an implicit enumeration and a linear programming optimal cuttingscheme to maximize the material usage. The algorithm was tested on some benchmark problems in theliterature, and compared with the three types of layout scheme algorithm. The experimental results show thatthe algorithm is effective both in computation time and in material usage.
참고문헌 (15)
- C. H. Cheng, "The cutting stock problem—a survey", International Journal of Production Economics, 36(3), pp.291~305 (1994)
- P. E. Sweeney, "Cutting and packing problems : a categorized, application-orientated research bibliography", Journal of the Operational Research Society, 43(7), pp.691~706 (1992)
- R. Alvarez-Valdes, "A tabu search algorithm for a two-dimensional nonguillotine cutting problem", European Journal of Operational Research, 183(3), pp.1167~1182 (2007)
- R. Baldacci, "A cutting-plane approach for the two-dimensional orthogonal nonguillotine cutting problem", European Journal of Operational Research, 183(3), pp.1136~1149 (2007)
- P. C. Gilmore, "Multistage cutting stock problems of two and more dimensions", Operations Research, 13(1), pp.94~120 (1965)
- J. Ji, "An exact algorithm for large-scale unconstrained three staged cutting problems with same-size block requirement", International Journal of Information and Management Sciences, 23(1), pp.59~78 (2012)
- M. Hifi, "Exact algorithms for large-scale unconstrained two and three staged cutting problems", Computational Optimization and Applications, 18(1), pp.63~88 (2001)
- Y. Cui, "Generating optimal T-shape cutting patterns for rectangular blanks", Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 218(8), pp.857~866 (2001)
- Y. Cui, "Generating optimal two-section cutting patterns for rectangular blanks", Computers & Operations Research, 33(6), pp.1505~1520 (2006)
- P. C. Gilmore, "A linear programming approach to the cutting stock problem—Part II", Operations Research, 11(6), pp.863~888 (1963)
- J. E. Beasley, "Algorithms for unconstrained two-dimensional guillotine cutting", Journal of the Operational Research Society, 36(4), pp.297~306 (1985)
- J. C. Herz, "Recursive computational procedure for two-dimensional stock cutting", IBM Journal of Research and Development, 16(5), pp.462~469 (1972)
- M. Hifi, "A recursive exact algorithm for weighted two-dimensional cutting", European Journal of Operational Research, 91(3), pp.553~564 (1996)
- G. Young-Gun, "A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems", Operations Research Letters, 31(4), pp.301~307 (2003)
- J. V. De Carvalho, "LP models for bin packing and cutting stock problems", European Journal of Operational Research, 141(2), pp.253~273 (2002)