An Algorithm to Optimal Two-Stage Homogenous Strip Patterns of Rectangular Pieces

Jun Ji; Yi Ping Lu; Jian Zhong Cha; Yao Dong Cui; Ling Jun Kong

doi:10.4028/www.scientific.net/AMR.347-353.3189

Paper Titles

Modeling of Energy-Saving Optimization Model by Sub-Sheet Dryness Coordination Based on Muti-Agent
p.3171

Research on the System Decomposition on Papermaking Drying Process Based on Muti-Agent
p.3175

An Analysis of Growth Drag of China’s Urbanization Caused by Energy
p.3179

An Investigation of Behaviours of Bubble in Electric Field
p.3184

An Algorithm to Optimal Two-Stage Homogenous Strip Patterns of Rectangular Pieces
p.3189

Rotary Stirling Engine for Exhaust Energy Recovery
p.3193

Use of Carbon Nanotube and Nanosilica as Reinforcement Nanofillers in NR/SBR Blended Latex
p.3197

Molecular Cloning and Characterization Analysis of 3,8-Divinyl Protochlorophyllide a 8-Vinyl Reductase Gene from Dunaliella parva
p.3203

Numerical Simulations of the Mixing Uniformity of Tracer Gas and Air in 90 Degree Elbow Duct
p.3207

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 347-353An Algorithm to Optimal Two-Stage Homogenous Strip...

An Algorithm to Optimal Two-Stage Homogenous Strip Patterns of Rectangular Pieces

Abstract:

This paper presents an algorithm for two-stage homogenous strip patterns for rectangular pieces. The algorithm is appropriate for the shearing and punching process. It proposes the two-stage homogenous strip patterns that can be cut into homogenous strips in two stages, with another two stages being required to cut the strips into pieces. Firstly vertical cuts divide the stock sheet into segments, and then horizontal cuts divide the segments into homogenous strips. A homogenous strip contains pieces of the same type. The algorithm uses a dynamic programming recursion to determine the strip layout on each segment, solves knapsack problems to obtain the segment layout on the sheet. The algorithm is tested through benchmark problems, and compares with two famous algorithms. The pattern value and the computation speed of this paper’s algorithm are better than that of the classic two-stage algorithm. What’s more, this paper’s algorithm can give solutions very close to optimality.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 347-353)

Pages:

3189-3192

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.347-353.3189

Citation:

Cite this paper

Online since:

October 2011

Authors:

Jun Ji, Yi Ping Lu, Jian Zhong Cha, Yao Dong Cui, Ling Jun Kong

Keywords:

Cutting Stock, Dynamic Programming Recursion, Knapsack Problem, Unconstrained Two-Dimensional Cutting

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] CUI Yao-dong, ZHANG, Xian-quan. Two-stage general block patterns for the two-dimensional cutting problem [J]. Comput.Oper. Res. 34(10): 2882-2893, 2007. [2] SEONG, G.G, KANG, M.K. A best-first branch and bound algorithm for unconstrained two dimensional cutting problems [J]. Oper. Res. Lett. 31(4):301–307. 2003. [3] Hifi M., Zissimopoulos, V.: A recursive exact algorithm for Weighted two-dimensional cutting Euro [J], Oper Res 91,553 C564, 1996. [4] Hifi M. Exact Algorithm for Large-Scale Unconstrained Two and Three Staged Cutting Problems [J]. Computers Optimization and Application, 18: 63-88. 2001, [5] Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin, 2004. [6] CUI Yao-dong. Exact and heuristic algorithms for staged cutting problems [J]. Eng. Manufacture. 219(2):201–208, 2005.

DOI: 10.1287/opre.1040.0154

Google Scholar