第42卷第8期 Vol. 42No. 8
计算机应用
假压技术
FORGING & STAMPING TECHNOLOGY
基于两段方式的圆形片约束排样算法
曾兆敏，张春利
2017年8月 Aug-2017
（1.四川信息职业技术学院信息工程系，四川广元628017；2.河北金融学院实验教学中心，河北保定071051）
摘要：讨论圆形片约束排样问题，提出一种两段排样方式生成算法。两段排样方式用一条分界线将板材划分为两个段，每个段由相同长度和方向的条料组成，每根条料排放同种圆形片。首先确定所有可能尺寸的条料中圆形片的排样方式：然后采用背包算法，生成所有可能尺寸的段中条料的排样方式；最后依据板材排样价值最大原则，确定段的分界线位置，得到整张板材上圆形片的两段排样方式，将本文算法和文献算法进行比较，数值实验结果表明，本文算法排样价值高于文献算法。
关键词：约束排样算法：两段排样方式；背包算法；圆形片；条料 DOI: 10. 13330/j. issn. 1000-3940. 2017. 08. 033
中图分类号：TP391
文献标识码：A
文章编号：1000-3940（2017）08-0180-05
A constrained nesting algorithm of circular pieces based on two-segment patterns
Zeng Zhaomin', Zhang Chunli?
( 1. Department of Information Engineering, Sichuan Institute of Information Technology, Guangyuan 628017, China;
2. Experimental Teaching Center, Hebei Finance University, Baoding 071051 , China)
Abstract : The cireular pieces constrained nesting problen was discussed, and an algorithm generated by two-segment nesting patterns was proposed. The plate was divided into two segments using a line of demarcation by the two-segment patems. Each segment consisted of strips with the same length and direction, and each strip consisted of identical circular pieces. Firstly , the nesting patterns of circular pieces on strip of all possible sizes were determined, then the knapsack algorithm was used to generate the nesting patterns of strips on segment of all possible sizes, Finally, the boundary position of the segments was detemined by the principle of the maximum pattern val-ue, and the two-segment nesting patterns of eireular pieces on the whole plate were obtained. Compared the algorithm with the literature
algorithm, the numerical results show that the pattern value of the proposed algorithm is higher than that of the literature algorithm. Key words : constrained nesting algorithm; two-segment nesting patterns; knapsack algorithm; circular pieces; strip
制造业中经常雷要将金属板材切割成圆形片用来生产各种产品[1-2]。臀如在不锈钢产品制造业中，不锈钢板材被切割成圆形片用来制作家用商品，如水亚、称子、盘子等；在电机制造业中，硅钢板材被切割成圆形片用来生产电机的定子和转子。一般采用剪冲下料工艺将板材分割成圆形片，其包括2 个阶段3。在剪切阶段，用剪切机将板材切成条料；在冲压阶段，用冲压机将条料冲出圆形片。寻求一种好的排样方式，能够提高板材利用率，降低企业生产成本[4-5]
本文讨论圆形片约束排样
(Cireular Pieces Con-
strainedCutting，CPCC）向题：用规格为长L×宽W
收稿日期：20170316；修订日期：20170512 基金项目：四川省教育厅科研项目（GZY15C45）作者简介：曾兆敏（1974-），女，学士，副教投 E-mail: zengzmse@ 163. com
万方数据
的板材切割出m种圆形片，其中，第种圆形片的直径为d；，价值为，允许切割的数量上界为b：， i=1，，m；优化目标为排样价值（板材切割出的圆形片总价值）最大。令P为板材的排样方式， V为板材的排样价值，则CPCC的间题数学模型为：
rmax V=
(1)
s. t.
P为一个合理的排样方式
2,≤6,且z;为自然数,=1,2,--,m
式中：2;为P中包含圆形片i的数量
CPCC间题是圆形片下料（Circular Pieces Cut-tingStock，CPCS）间题的核心子间题。在采用顺序启发式算法（SHP）[6]求解CPCS向题时，SHP按顺序调用CPCC算法逐个生成排样方式，每个排样方式满足部分圆形片需求量，当所有圆形片需求量均得到满足时，终止算法。SHP算法步骤如下。