论文研究-冲裁件条料最优四块剪切下料方案的生成算法.pdf

所需积分/C币:15 2019-09-10 12:35:37 579KB .PDF

讨论冲裁件条料剪切下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成条料最优四块排样方式的背包算法,然后采用基于列生成的线性规划算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并确定各种冲裁件的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用例题将该排样方式生成算法和文献中多段排样方式生成算法进行比较,实验计算结果表明,该算法得到的排样方式排样价值较高。最后通过文献中实例的下料方案求解,可以看出该算法解决实际下料问题是有效的。
曾兆敏,管卫利,潘卫平:冲裁件条料最优四块剪切下料方案的生成算法 2016,52(20)77 集。故四块排样方式板材利用率不会低于T型和两段3、3计算四块排样方式的价值 排样方式。另外,多段排样方式需要用多刀(大于3刀) 用Vx,V分别表示最优X向四块方式与最优y 将板材切成多个段,而四块排样方式只需川3刀将板材向四块方式的价值,为最终的四块排样方式价值。则 切成四个块(段),刀数的减少能够缩减切割工作量,从有如下公式: 而简化切割工艺"。 Vx= max i, max [F(x,1)+F(r,w-3)l+ 分界线 max IF(L-x,12)+F(L-x, -y2)17 (5 A C max 分 分B max [F(x2,W-1)+F(L-x2,w-y)1? 线 父分界线 父分界线 ↑子分界线 V=max(r, V) (a)X向四块方式 (b)Y向四块方式 式(5)中x为父分界线位置,y1,y2为两条子分界 图2四块排样方式 线位置。其中x,y1·P2均为整数。 图3所示为一X向四块排样方式,其中A块中包含 式(6)中y为父分界线位置,x1,x2为两条子分界 1条3号,1条5号水平条料,B块中包含1条2号、1条19线位置。其中y,x1,x,均为整数 号竖直条料,C块中包含2条13号水平条料,D块中包 式(7)说明选择X向四块方式和Y向四块方式中 含2条9号、1条16号竖直条料。 价值较大的作为最终的四块排样方式。 34四块排样方式生成算法 令Px为最优X向四块排样方式的父分界线位置, 令P1、P2为两条子分界线位置。排样算法首先确定 出父分界线和子分界线位置;然后再求解背包问题,逆 9 向推出各块中所含条料的情况;最终得到最优ⅹ向四 块排样方式图及其排样价值。最优向四块排样方式 可以类似确定。最后选择ⅹ、Y向排样方式的较大者作 为最终的四块排样方式。 图3四块排样方式例图 P1 for(x=0;x≤L/2;x++) 3排样方式生成算法 {for(y1=0;y≤W2;y1++ 3.1计算条料的价值 r,=maxF(x,y), F(r, x)]+ 条料的价值为条料中包含的冲裁件的价值之和 max[F(x, w-), F(-y, x); 设x×w为包含第i种冲裁件的条料(长为x、宽为w,), if(1<){1=;Py1=y n(i,x)为条料中包含的冲裁件个数,s(,x)为条料的价 值(=1,2,…,m)。则有如下公式 for(y2=0;y2≤W2;y,++) (r,=max[F(L-xv,), F(L-y,,x)]+ 1+itx-a)bx≥a max[F(L-x,w-,), F(W-I,, L-x) if(v2<V2){2=2;Py2=y2;} 32计算块的价值 对于块xxy,不妨设块中条料的方向与长度为x 的边的方向相同。记r(x,y)为块的价值,x≤L if(x<Vi+Vx=V+b,, Px=x y≤W。令(,x)为块中包含条料x×w,的个数。则有 如下公式 用背包算法求解四个块中所含条料情况,该问题是 个典型的背包问题,具体解法可以参考文献[1l6],本 )-max∑s(i,x)(,) 节不再赘述 35算法时间复杂度 st.∑(,x)wsy,2(,x)∈N (4) 式(2)~(3)计算条料价值时间复杂度为O(mL)。 模型(3)是背包问题,文献卩16介绍了一个很好的 式(4)计算块价值时间复杂度为O(mWL)。 解法。 式(5)-()确定最优四块排样方式时问复杂度为O(WL)。 016,52(20) Computer Engineering and Applications计算机工程与应用 综:本文排样算法总的时间复杂度为σ(mL+法。由于夲文算法和文献[算法都属亍确定性算法 mW+1),由于m<W,枚算法时间复杂度可写为故只要算法执行完毕,实验条件对算法求得的解没有影 O(mWL),与多段排样算法时间复杂度相等"。 响。首先将本文四块排样方式生成算法与文献[1多段 排样方式生成算法进行比较。然后将本文下料方案生 4下料方案生成算法 成算法与文献「1l下料方案生成算法进行比较。 本文讨论的下料问题的线性松弛数学模型为:5.1与多段排样方式生成算法比较 min S=CX 本节采用文献[中的50道随机测题,板材L∈ st.AX≥D,X≥0 (8)[2000,25001、W≡[10012501,冲裁件初始步距和宽 其中,S=所用板材的总面积;C=c,c2…,cn],c1为单度在区间「100450均匀分布。每道测题包含30种冲裁 张板材面积,其值为xW;X=[x,x2…,xm,x,为按件,后续步距b=in(a),其中∈106,09;冲裁件价 第j种排样方式切割的板材张数,A=m阶方阵,其中值c;=bv,=1.2,…,30。令V、分别为文献[ 元素a表示第j排样方式中包含第i种冲裁作的个算法和本文算法的排样价值,p、n分别为文献[算法 数;D=l,d2,…,dn,d为第i种冲裁件的需求量 和本文算法的板材利用率。 以上模型为线性规划模型,可采用如下步骤求解 求解50道测题文献[1算法和本文算法分别耗时 步骤1确定模型(8)的初娢可行解 4658、461s,平均每道测题计算时间分别为0.093s 令A为单位矩阼,初始可行解Ⅹ=D,即第i种排 0.092s,可见两种算法计算时间近似相等。文献[算法 板材平均利用率为97747%,本文算法板材平均利用 样方式只包含一个第i种冲裁件。 率为981296%。表1为前10道测题的排样方式价值和 步骤2确定冲裁件当前价值向量 Ca= 板材利用率。虽然本文算法板材利用率只比文献[算 法高0.3549%,但是本文算法生成的四块排样方式板材 步骤3寻求可能改善目标函数的排样方式。 切成块(段)最多只需用3刀,而文献[1算法生成的多段 按照冲裁件的当前价值向量调用上节的排样方式排样方式板材切成段需要用多刀(大于3刀)。故在排 生成算法,生成一个新的排样方式P=p1p2…,Dn 样方式的切割工艺方面本文算法比文献[算算法简单。 其中p为排样方式中含第i种冲裁件的个数。依照线 性规划理论,若LM-PP<0则引入排样方式P可能改 表110道测题的实验结果 善目标函数,按照列生成法原理用P替换矩阵A的第k 测题编号 rP y I 1956728196144297.7875980231 列(其中k满足min{xp,>0}=x),然后转步骤步 2604914 97.5996 骤2,否则已不存在能使模型(8)目标函数改善的排样方 260064(2615047 84l83989635 式,当前解即为最优解 2345678 2480330248281498554298.6529 ? 261535297.443597.4023 A构造一个初始可行解 2354048 2956 29155922915946 98.044398.0562 B确定冲裁件当前价值向量 2195421 9 2538090253849797932097.9477 C生成一个新的排样方式 2047314204838197.052397.1029 注:“▲”表示对应值与多段排样方式相等 D引进排样方式P 是否使得日标函数 是E引进排样方式P生 5.2与多段下料方案生成算法比较 得到了改善? 成一个新的下料方案 某车间需要用尺寸为2000×1200的硅钢板材剪 冲出4种冲裁件。冲裁件县体数据如表2所示。本文算 否 法和文献[算法求解下料方案,分别耗时1.31s、1.33s, 输出下料方案 两种算法计算吋间相近。本文算法生成的下料方案如 图4下料方案生成算法的流程图 图5所示,包含4种排样方式,其中图5(a)表示按照排样 方式1剪切162张板材。下料方案总共使用669张板 5实验与结果 材,板材利川率为94.18%。文献[算法下料方案总共 用C语言实现本文算法,在主频为27GHz,内存使用670张板材,板材利用率为94.04%。可见本文下料 为2GB的徵型计算杋上分别运行本文算法和文献[算方案生成算法要优于文献[算法。 曾兆敏,管卫利,潘卫平:冲裁件条料最优四块剪切下料方案的生成算法 2016,52(20)79 表2冲裁件数据 5 Furini F, Malaguti E, Duran R M, et aL.A column gener- 冲裁件编号初始步距后续步距度需求量 ation heuristic for the two-dimensional two-staged guil 144 9720 lotine cutting stock problem with multiple stock size[J] 77 5647 European Journal of Operational Rescarch, 2012, 218(1) 234 185 8725 251-260 348 208 8985 [6 Cui Y Heuristic for the cutting and purchasing decisions of multiple metal coils[J].Omega, 2014, 46: 117-125. 4 [7]季君基于同形块的剪切下料布同算法研究[D]北京:北京 交通大学,2012 [8 Chen Q, Cui Y, Chen Y Sequential valuc correction hcuristic for the two-dimensional cutting stock problem with thre. (a)方式1:为162张 (b)方式2:为221张 staged homogeneous patterns J].Optimization Methods and Software, 2015:1-20 [9 Cui Y Exact algorithm for generating two-segment cutting patterns of punched strip plied Mathematical Modeling 2007,31(9):1865-1873 [IO] Cui YRecursive algorithm for the two-dimensional cutting (c)方式3:为171张 (d)方式4:为115张 problem of punched strips.Engineering Computations 图5本文算法下料方案图 2006,23(6):587-596 6结语 []l李尚芳,崔耀东,王晓庆冲裁条带最优多段排样方式的动 态规划算法[J计算机T稞与应用,2011,47(34):238-241 下料问题厂泛地出现在工业生产中,采用计算机辅 [12] Song X, Benncll A Column generation and sequential 助设计技术(CAD)对下料方案进行优化,可以获得良好 heuristic procedure for solving an irregular shape cutting 的经济效益。本文针对剪切阶段的条料排样问题,设计 stock problemJJJournal of the Operational Research 了基于背包问题思想的排样算法,算法时间复杂度低, Society,2013,65(7):1037-1052 生成的排样方式切割工艺比较简单,板材利用率较高 13 Puemsin S, Tharmmaphornphilas W, Siripongwutikorn P 将该排样算法与线性规划相结合构造的下料算法可以 Solving 2-dimensional multiple length cutting stock problem 有效地解决冲裁件剪冲下料问题。 with MiLPU]Journal of Mathematics, Statistics and Opera tions Research(JMSOR), 2014, 1(1) 参考文献: [14 Nonas S L, Thorstenson A Solving a combined cutting stock and lot-sizing problem with a column generating [1 Cui Y Recursive algorithm for generating two-staged cutting procedure[j.computers&OperationsResearch2008 patterns of punched strips [J]. Mathematical and Computa 35(10):3371-3392 tional Applications, 2007. 12(2):107-115 [15]潘卫平,陈秋莲,崔耀东.考虑切割刀数的最优两段排样 [2 Nye T J Optimal nesting of irregular convex blanks in strip 算法研究[广西大学学报:自然科学版,2014,39(3) via an exact algorithm[J]. International Journal of machine 687-692 Tools and Manufacture. 2001. 41(7):991-1002 16 Keller H, Pferschy U, Pisinger D Knapsack problemsMI [3 Rao R v Evaluation of metal stamping layouts using an Berlin: Springer, 2004 analytic hierarchy process method[J] .Journal of materials17]罗洽洪,唐立新,张悟移钢铁原料物流计划问题的建模 Processing Technology. 2004. 152(1): 71-76 与求解门系绽工程理论与实践,2008,5(5):77-83 14] Peng Y, 7hao 7. evelopment of a practical blank layout [181 Gramani M C N, Franca PM, Arenales MN.A lagrangian optimization system for stamping die design[J].The Inter relaxation approach to a coupled lot-sizing and cutting national Journal of Advanced Manufacturing Technology stock problem. International Journal of Production Eco 2002,20(5):357-362 nomIcs,2009,119(2):219-227

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐