一维优化下料问题

第24卷第1期桂林工学院学报Vol. 24 No. 12004年1月JOURNAL OF GUILIN INSTITUTE OF TECHNOLOCYJan. 2004文章编号:1006 - 544X(2004)01 -0103 -04一维优化下料问题，张春玲，崔耀东(广西师范大学数学与计算机科学学院，广西桂林541004)摘要:下料问题在生产中普遍存在， 优化下料可以提高原材料利用率，是企业增加经济效益的途径之一，对一维下料问题进行了探讨, 给出- -维下料问题的一些概念和数学模型，讨论解决-维下料问题的常用算法以及算法的适用情况，分析与之相关的一些问题和具体的实际应用.关键词:下料;最优化;整数规划中图分类号: TB114. 1; 0224文献标识码: A随着全球资源的日益匮乏，人们对资源利用Dyckoff{3) 提出下料问题可以根据4种特征来问题的研究愈来愈重视，下料问题就是其中之分类: 维度、分配类型、大物件的分类和小项的-[1-31. 最大限度的节约原材料，提高原材料利 分类. Dycof描述- 维下料问题为I/V/D/M: 1用率是生产中提高效益的- -个重要手段， 在机械指的是- 维问题， v指的是所有的小项必须从一行业、造纸、服装、木材等行业，下料问题都有大物件中产生，D的意思是所有大物件是不同的，广泛的实际应用下 料问题就是研究怎样在客观M是指小项之间不同.条件和可以接受的时间下优化排样得到最优解或如果原材料是同一长度或只有少数的组(组.近似理论最优解.下料问题根据维数- 般可 分为中长度相近)，可得到标准一维下料问题 (SID--维下料和二维下料，本文主要对一维下料问题CSP)，对于S1D- CSP给出切割方案的概念，切进行讨论.割方案是用1根原材料切割各种不同规格的坯料1一维 下料问题的概念和数学模型时，保持坯料规格的种类不变，只改变切割数量.-维下料问题( one-dimensional cutting stock将有效的切割方案集中起来就是最后的下料方式.problem,简称1CSP )是在已知原材料和顾客需S1D- CSP问题可以描述如下:求坯料的情况下优化下料使原材料的使用率达到l;一坯料长度,i = 1,"',n;最大或废料达到最小，根据原材料长度是否相等,d;-每种坯料的需求数量,i = 1,.,n;一维优化下料可以分为单一型材的优化下料和多4k-原材料长度,h = 1,.,P,型材的优化下料.单-- 型材的优化下料很多文献切割方案 c可以用如下一一个向量a来表示:中都已有讨论，而多型材的优化下料在型材类型Clck ,Q2ch.""" ,Anck;(I)比较多的时候，可以将型材按长度相近进行分组，先选组，再从组中选择型材下料，由此引发出分满足Zlauk≤Lz,且alck≥0,是整数. (2)组问题.分组有利于节约原材料，但是如果分组aish 表示l;在特定的切割方案中出现的次数,xak表太细，会导致增加库存管理的负担.示切割方案c在原材料k上使用的次数,表示在原收稿日期: 2003 -05 -12基金项目:广西自然科学基金资助项目(桂科基0236017)作者简介:张春玲(1978-), 女,硕士研究生,研究方向: CAD/CAM.中国煤化工MYHCNMHG104桂林工学院学报2004年材料h上满足(2)式的切割方案的总数，那么将会13 535 cm的原材料上切割5根长度为304 cm的坯有如下的整数规划模型:料，7根长度为319 cm的坯料，10 根长度为397min2 2xaL，(3)cm的坯料，14根长度为415 cm的坯料，不切割长度为366 cm的坯料(为0表示不切割).s.2 ZaxaLx≥d,i=1,,n; (4) .以需求为导向方法得到的切割量会出现比需xek≥0且为整数,c = 1,h;k = 1,.,p. (5)求量少的情况，其方法一般是基于启发式算法;从SID- CSP所对应的数学模型中可知SID -以方案为导向方法得到的切割量则会出现比需求CSP所优化的目标是最小化被切割的原材料数量.量多的情况，其方法- .般是基于线性规划的，两当原材料的长度全都不同时所建立的数学模型与种方法有各自的优缺点，可进行适当的组合得到上述模型是有所不同的如Gradisar等人[4]提出良好的下料效果.-维下料的数学模型早在1939年就已由Kan-的GID-CSP ( gencration one-dimensional cutingtorovich提出下 料问题的求解很大程度上依赖于stock problem)， 其数学模型中优化的目标是最小模型的建立，可根据具体情况进行模型的补充和.化废料，而且这一-模型中原材料的长度全都不同.修改，一维下料问题所建立的数学模型是-一个整Dekof(]) 将优化下料过程分为2类:以需求数规划问题， 求解整数规划问题一般使用分支定项为导向(item-oriented) 和以方案为导向( pat-界法或割平面法、分支定界法是一种隐枚举法，tem- oiemte)的方法，以需求项为导向的方法是效果的好坏取决 于分支的模式和界的确定，但下对顾客的每一-需求项进行单独的处理，直到一需料问题的求解有其自身的特点，下面讨论- -维下求项处理完才处理下-需求项;以方案为导向的料问题的常用算法.方法是把几种坯料组合进行下料，一次切割可得到不同规格的坯料.以方案为导向的方法只能对2 - 维下料问题的常用算法原材料长度是单一的或者原材料分为少数的组时一维下料问题是组合优化中的一个经典问题，有效，对于原材料的长度都不相同的情况只能用从计算的复杂性理论上看，优化下料问题属于NP以需求项为导向的方法(表1).难问题，即至今还不存在多项式界算法. NP 难问表1原材料与坯料[5]题的求解通常使用接近最优解的近似算法实现.Table 1 Stock and ilem求解一维下料问题的算法(1有基于线性规划的方顾客需求坯料原材料法、分支定界法、动态规划法、启发式算法、模需求需求长度需求量原材料长度编号/cm(根/a拟退火算法、演化算法等.304235352. 1基于线性规划的方法3193811 301以方案为导向的方法大多是基于线性规划的39794084159 341方法(LPM). 此类方法可以减少废料，但是会产36生多于需求量的切割量，只适用于单一型材或者是只有少量组的下料。基于线性规划的方法是将以需求项为导向的方法是先选择第1种需求建立的整数规划问题进行松弛，按照线性规划进坏料进行处理，第1种坯料在原材料2上切割6行求解，对得到的解取整、基于线性规划的方法根，在原材料1上切制6根，这样就得到12根可以追 溯到Gilmore和Comory的列生成(column304 cm长的坯料，再选择第2种坯料处理，在原generaion) 方法[6-7]、 当原材料和帶求的坯料的材料4上切割21根，在原材料3切割4根，在原种类相当多或者 是坯料的长度特别短而原材料的材料2上切割6根，在原材料1上切割7根，共得长度特别长时， 将导致切割方案太多，--次性将.到38根长度为319 cm的坯料，其它情况类似.若所有的切割方案 全部枚举出来是不可能的，文献是以方案为导向的方法，首先将坯料进行组合，[6]中国煤化工，进而利用迭代如(5, 7, I0, 14, 0)方案表示在第1种长度为的方YHCNMHG持定的方法和动第24卷第1期张春玲等:一维优化下料问题105态规划求解得到进人基的列，最后对主规划的解得到近似的最优解; 模拟退火算法是基于金属退取整. Hassler [8] 对Gilmore-Gomory 的算法进行火的机理 建立起来的一种全局最优化方法，它能了改进，修改了初始解，利用更强的约束条件控够以随机搜 索技术从概率的意义上找出目标函数制切割方案的产生以减少切割方案的变更，Vale~ 的全局最小点. W augner 12]利用遗传算法解决一riol9]将列生成算法与分支定界法相结合,利用弧维下料问题并考虑了废料、库存使用和最后存货流模型，1种切割方案对应于1条路径，在弧流的等问题. Liang[13])用只使用变异算 子的演化规划同变量上进行分支.分支价值算法( branch-and-时对2个目标进行优化，采用了3PS和SRI两个price)又称整数规划列生成算法，它是在分支定变异算子， 刘道海等[4]从蚁群算法中信息素的概界树的每个结点上使用column gereratin 算法、念得到启示， 将信息素的观点引入道变异算子中，Vanderheck[I0]介绍了- -种基于列生成的算法，对用与适应值联 系在一起的信息素的变化来引导每分支定界法进行扩展，讨论分支模式，提出了一个基因位的变异， 并把这-算法运用到优化下料种伪多项式启发式，并在整数规划列生成算法中中李元香、张进波、徐静雯等115]提出- -种基于应用.变长编码求解- - .维下料问题的演化算法，收到了2.2基于启发式算法的方法比较好的结果，材料平均利用率可达到97%.当原材料的长度都不相同的时候只能用以需3 相关问题求项为导向的方法求解，这有2种可能:用确切的方法(分支定界或动态规划)或者是用形式为研究中发现[16 -18]对于1CSP的很多实例，下SHP (Sequence Heuristic Procedure) 的近似算法.料问题所建 立的整数规划问题的最优解与利用松启发式算法所使用的启发式一般只适用于特定的 弛后线性规 划问题求得的最优解具有一定的性质.问题，无通用性，有效的启发式对问题的求解是这些性质有 利于确定下料实例所属类别，简化计很有用的，但是有时寻找-一个有效的启发式比解算量, 对高维下料问题的研究也有帮助.引用文决问题本身还要困难.启发式算法得到的结果一献[18]中的四元组E= (m, I, b, L)来描述般不会太差，通常也可将启发式进行组合. Gra- - -维下料问题的实例，其中I = (h,12,-lm),bdisar[5]将一种字典 排序的方法应用于多型材下料= (b,2,.",bmn)T ,m是坯料种类,L是原材料长问题，以需求项为导向，用启发式(SHP) 最小度,1和b 分别是每种坯料的长度和对应的需求量，化约束条件的影响，并设置参数Y来调整废料与非负整数向量aj;= (arj,ny,-",am)",a≠0且满下料方案的复杂度之间的权、将基于线性规划的足Zlay≤L,(j= 1,2,-- ,n) ,n是切割方案的总方法和基于启发式的方法相结合["，用2个阶段数,是切割方案a;的使用次数,则所建立的数学求解:首先将问题转换成可用LPM求解的模式，模型如下:然后将切割方案中包含比需求量多的解删除，最后的结果是两部分的解之和: S=SLPM +SsHp，这minz = 2x，s.t.ait;≥bi;,i = 1,,m,样既能减少废料又能得到确切的需求量.x;≥0,j是整数,j = 1,,n.(6)2.3 其它算法与式(6)相应的松驰模型为遗传算法和模拟退火算法用于优化下料问题中效果良好:遗传算法是基于自然选择和基因遗minz =二x，s.a;q;≥b;,i = 1,,m,传的搜索算法，具有很好的鲁棒性，在解决复杂xj≥0j = 1,.,n.(7)问题的优化方面非常适用前面已提到， 当切割设Z* =Z*(E) ,Z。= Z。(E)分别表示(6)和方案特别多时一次性枚举是不可能的，利用遗传(7) 的最佳解, 0(E): =Z"(E) - 2。(E).算法，先随机的生成-些切割方案,形成初始种0(E)