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

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

《International Journal of Information and Management Sciences》 29卷2期 (2018/06) Pp. 191-204

https://doi.org/10.6186/IJIMS.201806_29(2).0003

摘要

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.

關鍵字

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

參考文獻

Alvarez, V. R., Parreo, F. and Tamarit, J. M. (2007). A TABU search algorithm for a two- dirnensional non-guillotine cutting problem, European J. of Operational Research, Vol.183, 1167- 1182.

Cui, Y. (2011). A recursive branch-and-bound algorithm for constrained homogenous T-shape cutting patterns, Applied Mathematical Modelling, Vol.54, 1320-1333.

Cui, Y. and Zhang, X. (2007). Two-stage general block patterns for the two-dimensional cutting problem, Computers & Operations Research, Vol.34, 2882-2893.

Cui, Y., Wang, Z. and Li, J. (2009). Exact and heuristic algorithms for staged cutting problems, J. of Engineering Manufacture, Vol.219, 201-208.

Cui, Y. (2004). Generating optimal T-shape cutting patterns for rectangular blanks, J. of Engineering Manufacture, Vol.218, 857-866.