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

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

《International Journal of Information and Management Sciences》 23:1 (2012/03) Pp. 59-78

https://doi.org/10.6186/IJIMS.2012.23.1.4

並列摘要

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.

並列關鍵字

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

參考文獻

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.

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.

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.

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.

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.