第43卷第2期 Vol. 43No. 2
叙压技木
FORGING & STAMPING TECHNOLOGY
基于顺序价值修正算法的矩形件二维优化下料
售？
李荣科’，王
2018年2月 Feb.2018
（1.广西职业技术学院计算机与电子信息工程系，广西南宁530226；2.河北金融学院实验教学中心，河北保定071051）摘要：针对矩形件二维下料问题，提出一种顺序价值修正下料算法。构造了四块排样算法，生成矩形件数量有上界约束的四块排样方式；这种排样方式将板材划分为4个块，每个块包含方向相同的条带，每条条带包含同种矩形件。采用顺序启发式算法调用上述四块排样算法逐个生成排样方式，按照不产生多余矩形件原则，确定每个排样方式的最大使用次数；在生成每个排样方式后修正该种排样方式中矩形件的价值。将上述顺序启发式算法送代执行多次，生成多个下料方案，选择板材使用张数最小的一个作为最终解。采用文献例题进行计算比较，数值实验结果表明本文算法比文献算法更能节省板材。
关键词：二维下料问题；四块排样方式；顺序价值修正；矩形件；递归算法 DOI: 10. 13330/j. issn. 1000-3940. 2018. 02. 031
中图分类号：TP391
文献标识码：A
文章编号：1000-3940（2018）02-0186-05
Two-dimensionaloptimumblankingofrectangularpartsbasedon
sequential value correction algorithm
Li Rongke', Wang Jia
( 1. Department of Computer and Electronic Information Engineering, Guangxi Vocational & Technical College, Nanming 530226, China;
2. Experimental Teaching Center, Hebei Finance University, Baoding 071051, China)
Abstract : For the problem of two-dimensional blanking of rectangular part, a sequential value correction blanking algorithm was pro-posed. Then, four-block nesting algorithm was constructed, and four-block nesting mode with upper bound on the number of rectangular parts was generated. Based on this pattern, the plate was divided into four blocks with each block eontained strips of the same direction and each strip contained identical rectangular parts. Therefore, the four-block nesting algorithm was applied by the sequential heuristic al-gorithm to generate the nesting one by one, Under the conxlition of avoiding redundant rectangular parts, the maximum using times of each nesting mode were determined, and the value of rectangle in this nesting method was corrected after each nesting method was generated. Furthermore, the above sequential heuristic algorithm was iteratively executed multiple times to generate multiple blanking schemes, and the one with the least number of blanks was chosen as the final solution. Compared with the literature example, the results of numerical experiments show that the above algorithm saves blanks more than the literature algorithms.
Key words : two-dimensional blanking problem; four-block nesting; sequential value correction; rectangular part; recursive algorithm
在钣金制造领域，经常需要将金属板材切判成
矩形件用来生成各种产品，优良的下料方案可以促进材料节约，降低企业生产成本[1-3]。
矩形件二维下料间题（Two Dimensional Cuting Stock Problem of Rectangular parts，TDCSR）可描述为：用长L、宽W的板材切割出m种矩形件，第i 种矩形件的长、宽、需求量分别为}，"；、d；；确定下料方案使得板材使用张数最小。设下料方案由n
收稿日期：20170825；修订日期：20171220
基金项目：广西高校中青年教师基础能力提升资助项目(2017KY0980, KY2016LX495, KY2016YB610)
作者简介：李荣科（1977-），男，土，高级工程师万方整据il：nkgz2009@163.0m
个排样方式组成，其中第了个排样方式包含P。个矩形件i。TDCSR间题数学模型为：
minz
= d,,i = 1,.-,m
(1)
e
式中：Z为下料方案总共使用的板材张数；x；为下料方案包含排样方式的个数；N"为正整数集合。
针对TDCSR问题，文献[4］提出了基于T型排样方式的下料算法，首先构造动态规划算法生成矩形件在单张板材上的T型排样方式，然后采用线性规划算法调用T型排样算法生成下料方案。文献