基于4块排样方式的电机用圆形片下料算法

高淑婷,李碧青

(1.河南农业职业学院,郑州451450;2.贺州学院,贺州542899)

0 引 言

电机生产企业,每年需要消耗大量硅钢板材用来制造电机铁心[1]。铁心毛坯一般为圆形。由于硅钢板材比较昂贵,因此优化下料方案来提高硅钢板材下料利用率可降低企业生产成本[2-3]。

一般采用剪切和冲裁工艺下料[4]。首先剪床将硅钢板材剪切成条带,然后冲床将条带冲裁出圆形片。从而存在两个布局问题:条带中的圆形片布局问题和板材中的条带布局问题。圆形片在条带中的布局方式在设计模具时就固定,无法更改;而条带在板材中的布局方式可在下料过程中进行优化[5]。本文主要研究下料过程中条带的优化布局问题。

目前针对矩形毛坯剪冲下料问题研究较多[6-8],针对圆形片剪冲下料问题研究较少。崔耀东[2,9]提出了基于直切排样方式和T型排样方式的下料算法,这两种算法都是基于列生成的线性规划思想,用一个矩阵表征下料方案中的各个排样方式,其中每列表征某个排样方式中各种圆形片的数量。

本文介绍基于4块排样方式的混合下料算法,首先采用线性规划和无约束排样算法生成下料方案的线性解,保留线性解的整数部分;然后用顺序启发式算法和有约束排样算法求解线性解小数部分对应的圆形片的下料问题。数值实验结果表明,本文算法能有效地提高板材下料利用率。

1 下料问题的数学模型及算法

1.1 数学模型

圆形片下料(以下简称CPC)问题:用若干张尺寸为L×W的板材切割出m种圆形片,(di,qi)为第i种圆形片的直径和需求量;下料优化目标为使用最少张数板材切割出所有需要的圆形片。

令G为单张板材上圆形片所有可能的排样方式的数量,aij为第j种排样方式中包含第i种圆形片的数量,yj为按照第j种排样方式切割板材的张数,N为自然数集合。CPC问题的数学模型:

目标函数为最小化板材切割张数;第一行约束条件表示下料方案中每种圆形片的需求量得到满足;第二行约束条件表示每种板材切割的张数为自然数。对于中大规模下料问题,由于所有可能的排样方式数G非常巨大,不可能枚举出所有可能的排样方式,因此式(1)无法直接采用数学规划软件求解。本文采用线性规划和顺序启发式算法近似求解上述模型,用线性规划算法生成下料方案的第一部分解,用顺序启发式算法生成下料方案的第二部分解。

1.2线性规划算法

CPC问题的线性松弛模型:

式(2)中ZR为下料方案总共切割的板材张数,Y=(y1,…,ym)为解向量,其中yj表示按照第j种排样方式切割的板材张数,A为下料方案矩阵,其中aij表示第j种排样方式中包含的第i种圆形片的数量,Q=(q1,…,qm)为圆形片需求量向量。用如下线性规划算法求解式(2)。

步骤1:构造式(2)的初始可行解,解中包含m种排样方式,第i种排样方式中排放1个第i种圆形片;此时A为单位矩阵,下料方案总共切割∑m i=1qi张板材。

步骤2:确定圆形片当前价值向量V=(1,…,1)A-1=(v1,v2,…,vm)。

步骤3:考察可能改善下料方案的排样方式。假设当前考察的排样方式P=(p1,…,pm)T,其中pi为排样方式中包含第i种圆形片的数量。依据线性规划原理,若VP＞1,则引进排样方式P能改善当前下料方案。通过求解如下式(3)构造P。

用P替换矩阵A的第k列,其中k由单纯型法确定[6],转步骤2;若VP≤1,则不存在能使当前下料方案得到改善的排样方式,输出下料方案,算法结束。

1.3 顺序启发式算法

上节的线性规划算法求得的下料方案解中可能存在为小数,传统下料算法一般对解取上整操作,即将(作为最终解,其中为向上取整数符号。取上整操作会使得下料方案板材利用率不高。本文对线性规划解进行取下整操作,即将作为下料方案的第一部分解。 由于取下整操作而剩余的圆形片构成第二部分下料问题,采用如下顺序启发式算法求解:

Step1:初始化圆形片的剩余需求量Q=Q-AY-。

Step2:用圆形片当前剩余需求量调用有约束排样算法生成一个有约束4块排样方式P,其中对任意i∈{1,…,m}有pi≤qi。 通过求解如下式(4)构造P。

Step3:确定按照排样方式P切割的板材张数λ=,更新圆形片剩余需求量λpi;如果对任意均有qi=0,则算法结束,输出下料方案,否则,转Step2。

2 排样方式生成算法

4块排样方式的相关概念可参见文献[5]。如图1所示(图中的数字为圆形片的编号),用一条父分界线和两条子分界线将板材划分为4个块,每个块中排放方向和长度均相同的条带。条带中可排放一行或多行圆形片(一般不超过3行)。按照是否能约束排样方式中每种圆形片的数量,相应的排样算法可分为无约束排样算法和有约束排样算法;无约束排样算法对排样方式中圆形片数量没有约束,有约束排样算法限定排样方式中每种圆形片的数量不超过其上界。

图1 4块排样方式

下面设计有约束排样算法。假设第i种圆形片的数量上界为bi,i∈{1,…,m}。当bi取足够大的数时,有约束排样算法即可变形为无约束排样算法。

由于条带中最多包含3行圆形片,因此对于m种圆形片,条带共有3m种不同的宽度,其中第i种,第(i+m)种和第(i+2m)种宽度对应第i种圆形片,即第j种条带对应第j%m种圆形片,其中“%”为取余数符号。令s(j,x)为条带x×wj(长为x,宽为wj)的价值,n(j%m,x)为条带x×wj中包含第j%m种圆形片的数量。则有:

其中n(j%m,x)的求解可参见参考文献[9]。

对于块x×y(长为x,宽为y),设块的价值为F(x,y),x≤L,y≤W,令块中包含条带x×wj的数量为g(j,x)。则有:

式(6)为有界背包问题,具体算法可参考文献[10]。求解式(6)后统计块x×y中包含各种圆形片的数量,记第i种圆形片形数量为n(i,x,y)。

设4块排样方式的父分界线位置为x,两条子分界线位置分别为y1,y2,其中x,y1,y2均为整数。令4块排样方式价值为V。则有:

目标函数为最大化排样方式价值,约束条件为排样方式中每种圆形片的数量不超过其上界。

3 实验计算

用Java语言实现本文算法,所用实验环境为E-clipse IDE for Java Developers4.5.2 和 LINGO 16.0。实验所用计算机主频2.7 GHz,内存2 GB。

采用文献[2]实例,某电机厂制造电机铁芯需要10种圆形片,具体数据见文献[2]表1,所有圆形片剪冲工艺余量均为5 mm。

3.1 实验一

市场上有3种不同尺寸的板材可供选购,分别为2 m×1 m,2.2 m×1.1 m,2.4 m×1.2 m。 对于 3种板材,本文算法和文献[2]算法下料方案使用板材情况如表1所示。可见对于3种不同尺寸的板材本文算法下料利用率分别比文献[2]算法高4.65%,5.35%和 4.97%。 另外文献[2]算法采购两种板材时下料利用率最高为72.02%,采购3种板材时下料利用率最高为73.76%,均低于本文算法采购一种板材时的下料利用率。由于板材种数越多,下料工艺越复杂,因此本文算法不仅可以提高下

表1 3种板材的下料情况

料方案的板材利用率,还可以简化下料工艺。图2为本文算法使用2.4 m×1.2 m板材时的下料方案,共包含10种排样方式,其中,“26张”表示按照排样方式图2(a)切割板材26张。

图2 采用板材2.4 m×1.2 m时的下料方案

3.2 实验二

已知板材长度、宽度分别在区间[1.5 m,2 m],[0.75 m,1 m]取值,确定板材最优尺寸使得下料方案板材利用率最高。按照文献[2]表5对板材尺寸进行离散取值,共考察36种不同尺寸的板材。文献[2]算法最优板材尺寸为1.7 m×0.95 m,相应下料利用率为73.14%;本文算法最优板材尺寸为1.9m×1 m,相应下料利用率为75.34%,具体的下料方案如图3所示。

图3 采用板材1.9 m×1 m时的下料方案

4 结 语

本文针对电机铁心用圆形片下料问题,介绍了一种基于线性规划和顺序启发式的确定性下料算法。构造了有约束4块排样方式生成算法和无约束四块排样方式生成算法,分别供线性规划和顺序启发式算法调用。数值计算结果表明,本文下料算法能够较大地提高硅钢板材下料利用率,节约企业生产成本。

[1]邓卫国,赵威,巫书豪,等.铁心叠铆转动工艺及模具设计[J].微特电机,2016,44(10):94-96.

[2]季君,崔耀东,刘丽娜.电机用硅钢板材尺寸合理选用[J].微特电机,2005,33(3):40-42.

[3]崔柏伟,邓卫国.电机定转子铁心双排无废料级进模设计[J].微特电机,2013,41(5):71-74.

[4]苏兰.冲裁条带三块排样方式的动态规划算法[J].河南师范大学学报(自然版),2014(6):143-147.

[5]曾兆敏,管卫利,潘卫平,等.冲裁件条料最优四块剪切下料方案的生成算法[J].计算机工程与应用,2016,52(20):75-79.

[6]季君.基于同形块的剪切下料布局算法研究[D].北京:北京交通大学,2012.

[7]MACEDOR,ALVESC,DECARVALHO JM V D.Arc-flow model for the two-dimensional guillotine cutting stock problem[J].Computers&Operations Research,2010,37(6):991-1001.

[8]SILVA E,ALVELOSF,DE CARVALHO JM V D.An integer programmingmodel for two-and three-stage two-dimensional cutting stock problems[J].Europe Journal of Operational Research,2010,205(3):699-708.

[9]CUIY D.Generating optimal T-shape cutting patterns for circular blanks[J].Computers&Operations Research,2005,32(1):143-152.

[10]KELLERER H,PFERSCHY U,PISINGER D.Knapsack problems[M].Berlin:Springer,2004.