An Exact Rectangular Two-Segment Layout Algorithm with Optimal Same-Shape Strip Generation

10.6186/IJIMS.201806_29(2).0003

Jun Ji；Wen-Zeng Zhang；Fei-Fei Xing；Yao-Dong Cui

Packing ； cutting ； same-shape strip ； two-segment layout ； dynamic programming

International Journal of Information and Management Sciences

29卷2期（2018 / 06 / 01）

191 - 204

英文

Compared with the general three-stage, the general two-segment, the well-known T-shape and TABU500 algorithms, this paper proposes a novel algorithm to solve large-scale rectangular packing problems efficiently. The algorithm in this paper can generate exactly rectangular optimal same-shape strip two-segment layout. The algorithm not only meets practical guillotine-cutting problems, but also is reasonable in computation time consuming. Firstly, the algorithm uses dynamic programming recursion to generate optimal same-shape strips; secondly, it solves knapsack problems to obtain the optimal same-shape strip two-segment layout. The algorithm is tested on 62 large-scale benchmark problems. Experimental results show that the algorithm is efficient and the solutions of the algorithm are better than conventional algorithms in solving large-scale two-dimensional cutting instances.

1. Ji, J.,Lu, Y.,Cha, J.(2012).An exact algorithm for large-scale unconstrained three staged cutting problems with same-size block requirement.International J. Information and Management Sciences,23,59-78.
   連結：
2. Alvarez, V. R.,Parreo, F.,Tamarit, J. M.(2007).A TABU search algorithm for a two-dirnensional non-guillotine cutting problem.European J. of Operational Research,183,1167-1182.
3. Cui, Y.(2004).Generating optimal T-shape cutting patterns for rectangular blanks.J. of Engineering Manufacture,218,857-866.
4. Cui, Y.(2011).A recursive branch-and-bound algorithm for constrained homogenous T-shape cutting patterns.Applied Mathematical Modelling,54,1320-1333.
5. Cui, Y.,Wang, Z.,Li, J.(2009).Exact and heuristic algorithms for staged cutting problems.J. of Engineering Manufacture,219,201-208.
6. Cui, Y.,Zhang, X.(2007).Two-stage general block patterns for the two-dimensional cutting problem.Computers & Operations Research,34,2882-2893.
7. Fayard, D.,Zissimopoulos, V.(1995).An approrimation algorithm for solving unconstrained tuo-dimensional knapsack problems.European J. of Operational Research,84,618-632.
8. Gilmore, P. C.,Gomory, R. E.(1965).Multistage cutting problems of two and more dimensions.Operations Research,13,94-119.
9. Han, W.,Bennell, J. A.,Zhao, X. Z.(2013).Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints.European J. of Operational Research,230,495-504.
10. Hifi, M.(2001).Exact algorithrn for large-scale unconstrained two and three staged cutting problems.Computers Optimization and Application,18,63-88.
11. Hifi, M.,Saadi, T.(2010).A parallel algorithm for two-staged two-dimensional fixed-orientation cutting problems.Computational Optimization and Applications,7,783-807.
12. Ji, J.,Xing, F. F.,Du, J.,Shi, N.(2014).A deterministic algorithm for generating optimal three-stage layouts of homogenous strip.J. of Industrial Engineering and Management,7,1167-1168.
13. Kellerer, H.,Pferschy, U.,Pisinger, D.(2004).Knapsack Problems.Berlin:Springer.
14. Morabito, R.,Vitria P. R.(2010).A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem.Annals of Operations Research,179,297-315.