An Exact Algorithm for Large-Scale Unconstrained Three Staged Cutting Problems with Same-Size Block Requirement

10.6186/IJIMS.2012.23.1.4

Jun Ji；Yi-Ping Lu；Jian-Zhong Cha；Jia-Qing Yu；Yao-Dong Cui

Cutting problems ； dynamic programming ； knapsack problem ； same-size block

International Journal of Information and Management Sciences

23:1（2012 / 03 / 01）

59 - 78

英文

This paper deals with the two-dimensional cutting problem, in which a set of small rectangular pieces are cut from a large rectangle for the purpose of maximizing the total value of the pieces included. The two-dimensional cutting problem is a very hard problem to solve, for which optimal algorithms exist but tackle large-scale problems inefficiently. Cutting patterns usually not only come from real-world production demands, but also can simplify a problem into some sub-problems. The pattern algorithm for each sub-problem can be constituted with much higher running speed, and serve as approximate algorithms to the optimal algorithms. This paper proposes an exact algorithm for generating three staged same-size block cutting pattern. This algorithm uses knapsack approach combined with a dynamic programming recursion. The algorithm is compared with the well-known threestage algorithm and the T-shape homogenous block algorithm through large-scale instances. The experiment results illustrate that the material usage of this paper's algorithm is higher than above algorithms within reasonable computational time.

1. Agrawal, P. K.(1993).Minimizing trim loss in cutting rectangular blanks of a single size form a rectangular sheet using orthogonal guillotine cuts.European Journal of Operational Re-search,64,410-42.
2. Alvarez-Valdés, R.,Rarajón, A.,Tamarit, J. M.(2002).A tabu search algorithm for large-scale guillotine (un)constrained two dimensional cutting problems.Computers & Operations Research,29,925-947.
3. Arslanov, M. Z.(2000).Continued fractions in optimal cutting of a rectangular sheet into equal small rectangles.European Journal of Operational Research,125,239-248.
4. Cintra, G. F.,Miyazawa, F.K.,Wakabayashi, Y.,Xavier, E.C.(2008).Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation.European Journal of Operational Research,191,61-85.
5. Cui, Y.(2005).Dynamic programming algorithms for the optimal cutting of equal rectangles.Applied Mathematical Modelling,29,1040-1053.
6. Cui, Y.(2004).Generating optimal T-shape cutting patterns for rectangular blanks.Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture,218,857-866.
7. Cui, Y.(2005).Exact and heuristic algorithms for staged cutting problems.Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture,219,201-208.
8. Cui, Y.,Liu, Z.(2008).T-shape homogenous block patterns for the two-dimensional cut-ting problem.Journal of Global Optimization,41,267-281.
9. Cui, Y.,Zhao, X.,Yang, Y.,Yu, P.(2009).Uniform block patterns for constrained guillotine cutting of rectangular items.International Journal of Information and Management Sciences,20,89-101.
10. Elsa, S.,Filipe, A.,de Carvalho, J.M. Valerio(2010).An integer programming model for two-and three-stage two-dimensional cutting stock problems.European Journal of Operational Research,205(3),699-708.
11. Gilnore, P.C.,Gomory, R.E.(1965).Multistage cutting problems of two and more dimensions.Computers & Operations Research,13,94-119.
12. Hifi, M.(2001).Exact algorithms for lage-scale unconstrained two and three staged cutting problems.Computational Optimization and Applications,18,63-88.
13. Hifi, M.,Saadi, T.(2010).A cooperative algorithm for constrained two-staged two-dimensional cutting problems.International Journal of Operational Research,9,104-124.
14. Hifi, M.,Zissimopoulos, V.(1996).A recursive exact algorithm for weighted two-dimensional cutting.European Journal of Operational Research,91,553-564.
15. Kellerer, H.,Pferschy, U.,Pisinger, D.(2004).Knapsack Problems.Berlin:Springer.
16. Seong, G.G.,Kang, M.K.(2003).A best-first branch and bound algorithm for unconstrained two dimensional cutting problems.Operations Research Letters,31,301-307.
17. Tarnowski, A.G.,Terno, J.,Scheithauer, G.(1994).Apolynomial time algorithm for the guillotine pallet-loading Problem.Information Systems Research,32,275-287.

1. Zhang, Wen-Zeng,Xing, Fei-FeiCui, Yao-Dong,Ji, Jun(2018).An Exact Rectangular Two-Segment Layout Algorithm with Optimal Same-Shape Strip Generation.International Journal of Information and Management Sciences,29(2),191-204.