Transactions of Materials and Heat Treatment

Title：A staged homogeneous block optimal layout method for rectangular part

Authors： Ji Jun Xing Feifei Huang Dunhua Cui Yaodong

Unit： Beijing Polytechnic Guangxi University

KeyWords： homogenous block rectangular part layout pattern material utilization dynamic programming algorithm

ClassificationCode：TP391

year,vol(issue):pagenumber：2021,46(2):46-51

Abstract：

The material utilization and the complexity of cutting process should be considered in generating the layout pattern. Therefore, a algorithm of staged layout scheme was presented for generating the cutting scheme for rectangular part to simplify the cutting process by allowing only one size of blank to appear in a homogenous block, and the optimal layout scheme was determined by the implicit enumeration algorithm and the dynamic programming to maximize the material utilization. Furthermore, the algorithm was compared with the normal T-shaped layout pattern algorithm, the normal two-stage layout pattern algorithm and the compound two-strip layout pattern algorithm by the test problems in the literature. The results show that in all the test problems, the material utilization of algorithm in this paper is higher than those of the above three algorithms, and the average computation time of algorithm in this paper to solve the layout problem of unconstrained two-dimensional cutting is 0.363 s which is reasonable.

Funds：

国家自然科学基金资助项目（71371058, 61363026）；北京市教委科研计划项目（KM201910858004）；北京科技电子职业学院课题（2019Z002-003-KXB）

季君(1979-)，女，博士，副教授，E-mail：ji_jun2000@sina.com

Reference：

[1]宋晓霞. 圆形件优化排样系统研究与开发[D]. 桂林: 广西师范大学, 2005.
Song X X. Research and Development of the Layout System for the Near Optimal Cutting of Circular Banks[D]. Guilin: Guangxi Normal University, 2005.
[2]Cheng C H, Feiring B R. Cutting stock problem-A survey[J]. International Journal of Production Economics, 1994, 36(3), 291-305.
[3]Sweeney P E, Paternoster E R. Cutting and packing problems: A categorized, application-orientated research bibliography[J]. Journal of the Operational Research Society, 1992, 43(7):691-706.
[4]Alvarez Valdes R, Parreo F, Tamarit J M. A tabu search algorithm for a two-dimensional non-guillotine cutting problem[J]. European Journal of Operational Research, 2007, 183(3): 1167-1182.
[5]Baldacci R, Boschett M A. A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem[J]. European Journal of Operational Research, 2007, 183(3): 1136-1149.
[6]Gilmore P C, Gomory R E. Multistage cutting stock problems of two and more dimensions[J]. Operations Research, 1965, 13：94-120.
[7]Gilmore P C, Gomory R E. A linear programming approach to the cutting stock problem-part II[J]. Operations Research, 1963, 11: 863-888.季君.基于同形块的剪切下料布局算法研究[D]. 北京: 北京交通大学，2012.
Ji J. Research on Guillotine Cutting Stock Packing Algorithm Based on Same-shape Block[D]. Beijing: Beijing Jiaotong University, 2012.
[9]季君, 陆一平, 查建中, 等. 生成矩形毛坯最优两段布局方式的确定型算法[J]. 计算机学报, 2012, 35(1):183-191.
Ji J, Lu Y P, Zha J Z, et al. A deterministic algorithm for optimal two-segment cutting patterns of rectangular blanks[J]. Chinese Journal of Computers, 2012, 35(1):183-191.
[10]Valdes R A, Parajon A, Tamarit J M. A tabu search algorithm for large-scale guillotine (un)constrained two dimensional cutting problems[J]. Computers & Operations Research, 2002, 29:925-947.
[11]Hifi M. Exact algorithm for large-scale unconstrained two and three staged cutting problems[J]. Computers Optimization and Applications, 2001, 18(1): 63-88.
[12]Cui Y D. Generating optimal T-shape cutting patterns for rectangular blanks[J]. Journal of Engineering Manufacture, 2004, 218 (B8): 857-866.
[13]Cui Y D, He D L, Song X X. Generating optimal two-section cutting patterns for rectangular blanks[J]. Computers & Operations Research, 2006, 33(6):1505-1520.
[14]薛焕堂，董海芳，管卫利.复合条带两段排样方式的生成算法[J]. 机械设计与制造，2017,(7):124-127.
Xue H T, Dong H F, Guan W L. An algorithm for generating composite strip two-segment cutting patterns[J]. Machinery Design & Manufacturing, 2017,(7):124-127.
[15]季君，邢斐斐，杜钧, 等. 生成同形块最优两阶段布局方式的确定型算法[J]. 计算机应用, 2014, 34(5)：1511-1515.
Ji J, Xing F F, Du J, et al. Deterministic algorithm for optimal two-stage cutting layouts with same-shape block[J]. Journal of Computer Applications, 2014, 34(5)：1511-1515.
[16]李明. 智能优化排样技术研究[D]. 杭州：浙江大学，2006.
Li M. Research of Intelligent Optimal Packing Technology[D]. Hangzhou: Zhejiang University, 2006.
[17]杨玉丽, 孙英, 崔耀东. 矩形毛坯三块排样方式及其算法[J]. 现代制造工程，2006, (10)：67-69.
Yang Y L, Sun Y, Cui Y D. An algorithm for generating three-block cutting patterns of rectangular blanks[J]. Manufacturing Engineering, 2006, (10)：67-69.
[18]陈菲. 基于三块结构的圆形片剪冲排样算法[D]. 桂林: 广西师范大学, 2009.
Chen F. A Cutting and Punching Algorithm of Circle Based on Three Blocks Pattern[D]. Guilin: Guangxi Normal University, 2009.

Service：

【This site has not yet opened Download Service】【Add Favorite】