锻压技术

二维下料问题的顺序按叠分组启发式算法

英文标题：Sequential stacking grouping heuristic algorithms of two-dimensional cutting stock problem

作者：许雁杰陈秋莲陈燕崔耀东

单位：广西大学

分类号：TP391

出版年,卷(期):页码：2020,45(9):45-50

摘要：

提出顺序按叠分组启发式算法求解二维按叠下料问题，确定按叠下料方案。顺序按叠分组启发式算法按顺序生成组成下料方案的布局图，对于每一个布局图，先根据整叠规则选择毛坯（矩形件）形成的候选毛坯集，再按候选毛坯集分组排样生成当前布局图，并根据整叠规则确定该布局图的使用次数；重复此布局图的生成过程，直至所有毛坯的需求均得到满足，从而确定下料方案。每次生成一个布局图后，通过毛坯价值修正算法对毛坯价值进行修正，使毛坯价值趋于合理。经多次迭代，生成多个不同的下料方案，从中选择总成本最低者作为按叠下料问题的解。实验结果表明，基于整叠规则的顺序分组启发式算法可明显降低二维按叠下料的总成本。

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.

基金项目：

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

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

参考文献：

［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.

服务与反馈：

【文章下载】【加入收藏】