Transactions of Materials and Heat Treatment

Title：Sequential stacking grouping heuristic algorithms of two-dimensional cutting stock problem

Authors： Xu Yanjie Chen Qiulian Chen Yan Cui Yaodong

Unit： Guangxi University

KeyWords： two-dimensional cutting stock stacking rule group by stacking candidate blank set value correction

ClassificationCode：TP391

year,vol(issue):pagenumber：2020,45(9):45-50

Abstract：

A sequential stacking grouping heuristic (SSGH) algorthms was presented to solve the two-dimensional stacking cutting stock problem and determine the stacking cutting scheme, and the SSGH algorthms sequentially generated the layouts in the cutting stock scheme. For each layout, candidate blank set was formed by selecting the blanks (rectangular pieces) according to the stacking rule, and then the current layout was generated by grouping and nesting the candidate blank set. According to the stacking rule, the usage times of layout was determined, and the generation process of layout was repeated until all the requirements of blanks were met to determine the cutting stock scheme. Each time a layout was generated, the value of blank was corrected by the blank value correction algorithm until the value of blank tended to be reasonable. Furthermore, after many iterations, many different cutting stock schemes were generated, and the one with the lowest total cost was selected as the solution of stacking cutting stock problem. Experimental results show that the SSGH algorthms based on the stacking rule obviously reduces the total cost of two-dimensional stacking cutting stock problem.

Funds：

国家自然科学基金资助项目(71371058，61363026)

许雁杰(1994-)，男，硕士研究生 E-mail：731034843@qq.com 通讯作者：陈秋莲(1974-)，女，博士，副教授 E-mail：chen-ql@foxmail.com

Reference：

［1］崔耀东. 计算机排样技术及其应用
［M］. 北京: 机械工业出版社, 2004.

Cui Y D. Computer Layout Technology and Its Application
［M］. Beijing: China Machine Press, 2004.

［2］Amine B, Maria L, Mohamed A H. Minimization of the wood wastes for an industry of furnishing: A two dimensional cutting stock problem
［J］. Management and Production Engineering Review, 2018, 9(2): 42-51.

［3］张国梁, 侯晓鹏, 苗虎,等. 基于分组降维规则和遗传算法的人造板材矩形件优化下料方法
［J］. 林业科学, 2014, 50(6): 181-186.

Zhang G L, Hou X P, Miao H, et al. Layout method of rectangular wood based panel parts based on grouping and dimension reducing heuristic rule and genetic algorithm
［J］. Scientia Silvae Sinicae, 2014, 50(6): 181-186.

［4］吴电建, 阎春平, 李俊, 等. 面向可加工性的矩形件优化下料方法
［J］. 计算机集成制造系统, 2018, 24(6): 1374-1382.

Wu D J, Yan C P, Li J, et al. Manufacturability-oriented rectangular parts cutting stock method
［J］. Computer Integrated Manufacturing System, 2018, 24(6): 1374-1382.

［5］华中平, 张立. 基于线性规划的角钢优化下料算法研究
［J］. 湖北工业大学学报, 2005，(5): 15-18.

Hua Z P, Zhang L. Research on algorithms of angle iron optimum cutting based on linear programming
［J］. Journal of Hubei University of Technology, 2005，(5): 15-18.

［6］尹震飚, 阎春平, 刘飞,等. 基于零件相似性特征的大规模下料分组优化方法
［J］. 计算机辅助设计与图形学学报, 2007，(11): 1442-1446.

Yin Z B, Yan C P, Liu F, et al. A grouping optimization method for solving large-scale cutting stock problem based on the similarity of parts
［J］. Journal of Computer-aided Design & Computer Graphics, 2007，(11): 1442-1446.

［7］陈燕, 谢琪琦, 刘咏,等. 圆形件下料顺序分组启发式算法的设计与实现
［J］. 图学学报, 2017, 38(1):5-9.

Chen Y, Xie Q Q, Liu Y, et al. The cutting stock problem of circular items based on sequential grouping heuristic algorithm
［J］. Journal of Graphics, 2017, 38 (1): 5-9.

［8］Cui Y, Yang L. Sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction
［J］. Production Economics, 2013, 144(2): 432-439.

［9］季君, 张文增, 邢斐斐, 等. 生成最优同质条带两阶段布局方式的精确算法
［J］. 现代制造工程, 2018(7): 17-22.

Ji J, Zhang W Z, Xing F F, et al. An exact algorithm for generating optimal two stage homogeneous strip layouts
［J］. Modern Manufacturing Engineering, 2018, (7): 17-22.

［10］王严欣, 崔耀东, 李华. 应用精确两阶段排样图的板材下料算法
［J］. 计算机工程与应用, 2017, 53(5): 236-240.

Wang Y X, Cui Y D, Li H. Algorithm for two-dimensional cutting stock problem with exact two-staged patterns
［J］. Computer Engineering and Applications, 2017, 53(5): 236-240.

［11］王婷婷, 崔耀东, 陈燕, 等. 考虑余料生成及利用的圆片下料算法
［J］. 锻压技术, 2019, 44(4): 40-47.

Wang T T, Cui Y D, Chen Y, et al. An algorithm of circular piece cutting stock considering generation and utilization of margin
［J］. Forging & Stamping Technology, 2019,44(4):40-47.

［12］Cui Y D. Fast heuristic for constrained homogenous T-shape cutting patterns
［J］. Applied Mathematical Modelling, 2012, 36(12): 3696-3711.

［13］Belov G, Scheithauer G. Setup and open-stacks minimization in one-dimensional stock cutting
［J］. Informs Journal on Computing,2007, 19(1): 27-35.

［14］Cui Y D, Huang B. Heuristic for constrained T-shape cutting patterns of rectangular pieces
［J］. Computers & Operations Research，2012, 39 (12): 432-439.

Service：

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