第24卷 第1期 桂林工学院学报 V ol.24N o.1 2004年1月 JOURNA L OF G UI LI N I NSTIT UTE OF TECH NO LOGY Jan12004文章编号:1006-544X(2004)01-0103-04一维优化下料问题张春玲,崔耀东(广西师范大学数学与计算机科学学院,广西桂林 541004)摘 要:下料问题在生产中普遍存在,优化下料可以提高原材料利用率,是企业增加经济效益的途径之一.对一维下料问题进行了探讨,给出一维下料问题的一些概念和数学模型,讨论解决一维下料问题的常用算法以及算法的适用情况,分析与之相关的一些问题和具体的实际应用.关键词:下料;最优化;整数规划中图分类号:T B11411;O224 文献标识码:A 随着全球资源的日益匮乏,人们对资源利用问题的研究愈来愈重视,下料问题就是其中之一[1-3].最大限度的节约原材料,提高原材料利用率是生产中提高效益的一个重要手段,在机械行业、造纸、服装、木材等行业,下料问题都有广泛的实际应用.下料问题就是研究怎样在客观条件和可以接受的时间下优化排样得到最优解或近似理论最优解.下料问题根据维数一般可分为一维下料和二维下料,本文主要对一维下料问题进行讨论.1 一维下料问题的概念和数学模型 一维下料问题(one2dimensional cutting stock problem,简称1CSP)是在已知原材料和顾客需求坯料的情况下优化下料使原材料的使用率达到最大或废料达到最小.根据原材料长度是否相等,一维优化下料可以分为单一型材的优化下料和多型材的优化下料.单一型材的优化下料很多文献中都已有讨论,而多型材的优化下料在型材类型比较多的时候,可以将型材按长度相近进行分组,先选组,再从组中选择型材下料,由此引发出分组问题.分组有利于节约原材料,但是如果分组太细,会导致增加库存管理的负担. Dyckoff[3]提出下料问题可以根据4种特征来分类:维度、分配类型、大物件的分类和小项的分类.Dyckoff描述一维下料问题为1/V/D/M:1指的是一维问题,V指的是所有的小项必须从一大物件中产生,D的意思是所有大物件是不同的,M 是指小项之间不同. 如果原材料是同一长度或只有少数的组(组中长度相近),可得到标准一维下料问题(S1D-CSP),对于S1D-CSP给出切割方案的概念,切割方案是用1根原材料切割各种不同规格的坯料时,保持坯料规格的种类不变,只改变切割数量.将有效的切割方案集中起来就是最后的下料方式. S1D-CSP问题可以描述如下: l i—坯料长度,i=1,…,n; d i—每种坯料的需求数量,i=1,…,n; L k—原材料长度,k=1,…,P.切割方案c可以用如下一个向量a ck来表示:a1ck,a2ck,…,a nck;(1) 满足∑ni=1l i a ick≤L k,且a1ck≥0,是整数.(2) a ick表示l i在特定的切割方案中出现的次数,x ck表收稿日期:2003-05-12基金项目:广西自然科学基金资助项目(桂科基0236017).作者简介:张春玲(1978-),女,硕士研究生,研究方向:C AD/C AM.示切割方案c 在原材料k 上使用的次数,t k 表示在原材料k 上满足(2)式的切割方案的总数,那么将会有如下的整数规划模型:min∑pk =1∑t kc =1x ck L k ,(3)s 1t 1∑pk =1∑t kc =1a 1ck x ck L k ≥d i ,i =1,…,n ;(4)x ck ≥0且为整数,c =1,…t k ;k =1,…,p.(5) 从S1D -CSP 所对应的数学模型中可知S1D -CSP 所优化的目标是最小化被切割的原材料数量.当原材料的长度全都不同时所建立的数学模型与上述模型是有所不同的.如G radisar 等人[4]提出的G 1D 2CSP (generation one 2dimensional cutting stock prob 2lem ),其数学模型中优化的目标是最小化废料,而且这一模型中原材料的长度全都不同. Dyckoff [3]将优化下料过程分为2类:以需求项为导向(item 2oriented )和以方案为导向(pattern 2oriented )的方法.以需求项为导向的方法是对顾客的每一需求项进行单独的处理,直到一需求项处理完才处理下一需求项;以方案为导向的方法是把几种坯料组合进行下料,一次切割可得到不同规格的坯料.以方案为导向的方法只能对原材料长度是单一的或者原材料分为少数的组时有效,对于原材料的长度都不相同的情况只能用以需求项为导向的方法(表1).表1 原材料与坯料[5]T able 1 S tock and item顾客需求坯料原 材 料需求编号需求长度/cm 需求量/根原材料编号原材料长度/cm 130412113535231938211301339714394084415344934153627 以需求项为导向的方法是先选择第1种需求坯料进行处理,第1种坯料在原材料2上切割6根,在原材料1上切割6根,这样就得到12根304cm 长的坯料,再选择第2种坯料处理,在原材料4上切割21根,在原材料3切割4根,在原材料2上切割6根,在原材料1上切割7根,共得到38根长度为319cm 的坯料,其它情况类似.若是以方案为导向的方法,首先将坯料进行组合,如(5,7,10,14,0)方案表示在第1种长度为13535cm 的原材料上切割5根长度为304cm 的坯料,7根长度为319cm 的坯料,10根长度为397cm 的坯料,14根长度为415cm 的坯料,不切割长度为366cm 的坯料(为0表示不切割). 以需求为导向方法得到的切割量会出现比需求量少的情况,其方法一般是基于启发式算法;以方案为导向方法得到的切割量则会出现比需求量多的情况,其方法一般是基于线性规划的.两种方法有各自的优缺点,可进行适当的组合得到良好的下料效果. 一维下料的数学模型早在1939年就已由K an 2torovich 提出.下料问题的求解很大程度上依赖于模型的建立,可根据具体情况进行模型的补充和修改.一维下料问题所建立的数学模型是一个整数规划问题,求解整数规划问题一般使用分支定界法或割平面法.分支定界法是一种隐枚举法,效果的好坏取决于分支的模式和界的确定,但下料问题的求解有其自身的特点,下面讨论一维下料问题的常用算法.2 一维下料问题的常用算法 一维下料问题是组合优化中的一个经典问题,从计算的复杂性理论上看,优化下料问题属于NP难问题,即至今还不存在多项式界算法.NP 难问题的求解通常使用接近最优解的近似算法实现.求解一维下料问题的算法[1]有基于线性规划的方法、分支定界法、动态规划法、启发式算法、模拟退火算法、演化算法等.211 基于线性规划的方法 以方案为导向的方法大多是基于线性规划的方法(LP M ).此类方法可以减少废料,但是会产生多于需求量的切割量,只适用于单一型材或者是只有少量组的下料.基于线性规划的方法是将建立的整数规划问题进行松弛,按照线性规划进行求解,对得到的解取整.基于线性规划的方法可以追溯到G ilm ore 和G om ory 的列生成(columngeneration )方法[6-7\〗.当原材料和需求的坯料的种类相当多或者是坯料的长度特别短而原材料的长度特别长时,将导致切割方案太多,一次性将所有的切割方案全部枚举出来是不可能的,文献[6]中通过初始化部分切割方案,进而利用迭代401桂 林 工 学 院 学 报 2004年的方式在每一步背包子规划中用特定的方法和动态规划求解得到进入基的列,最后对主规划的解取整.Haessler[8]对G ilm ore2G om ory的算法进行了改进,修改了初始解,利用更强的约束条件控制切割方案的产生以减少切割方案的变更.Valerio[9]将列生成算法与分支定界法相结合,利用弧流模型, 1种切割方案对应于1条路径,在弧流的变量上进行分支.分支价值算法(branch2and2price)又称整数规划列生成算法,它是在分支定界树的每个结点上使用column generation算法.Vanderbeck[10]介绍了一种基于列生成的算法,对分支定界法进行扩展,讨论分支模式,提出了一种伪多项式启发式,并在整数规划列生成算法中应用.212 基于启发式算法的方法 当原材料的长度都不相同的时候只能用以需求项为导向的方法求解,这有2种可能:用确切的方法(分支定界或动态规划)或者是用形式为SHP(Sequence Heuristic Procedure)的近似算法.启发式算法所使用的启发式一般只适用于特定的问题,无通用性,有效的启发式对问题的求解是很有用的,但是有时寻找一个有效的启发式比解决问题本身还要困难.启发式算法得到的结果一般不会太差,通常也可将启发式进行组合.G radis2 ar[5]将一种字典排序的方法应用于多型材下料问题,以需求项为导向,用启发式(SHP)最小化约束条件的影响,并设置参数Y来调整废料与下料方案的复杂度之间的权.将基于线性规划的方法和基于启发式的方法相结合[11],用2个阶段求解:首先将问题转换成可用LP M求解的模式,然后将切割方案中包含比需求量多的解删除,最后的结果是两部分的解之和:S=S LP M+S SHP,这样既能减少废料又能得到确切的需求量.213 其它算法 遗传算法和模拟退火算法用于优化下料问题中效果良好:遗传算法是基于自然选择和基因遗传的搜索算法,具有很好的鲁棒性,在解决复杂问题的优化方面非常适用.前面已提到,当切割方案特别多时一次性枚举是不可能的,利用遗传算法,先随机的生成一些切割方案,形成初始种群,然后经过选择、杂交、变异的遗传操作,计算个体适应度,将适应度高的个体保留到下一代,而适应度低的个体被淘汰,经过个体的优选最终得到近似的最优解;模拟退火算法是基于金属退火的机理建立起来的一种全局最优化方法,它能够以随机搜索技术从概率的意义上找出目标函数的全局最小点.Waugner[12]利用遗传算法解决一维下料问题并考虑了废料、库存使用和最后存货等问题.Liang[13]用只使用变异算子的演化规划同时对2个目标进行优化,采用了3PS和SRI两个变异算子.刘道海等[14]从蚁群算法中信息素的概念得到启示,将信息素的观点引入道变异算子中,用与适应值联系在一起的信息素的变化来引导每个基因位的变异,并把这一算法运用到优化下料中.李元香、张进波、徐静雯等[15]提出一种基于变长编码求解一维下料问题的演化算法,收到了比较好的结果,材料平均利用率可达到97%.3 相关问题 研究中发现[16-18]对于1CSP的很多实例,下料问题所建立的整数规划问题的最优解与利用松弛后线性规划问题求得的最优解具有一定的性质.这些性质有利于确定下料实例所属类别,简化计算量,对高维下料问题的研究也有帮助.引用文献[18]中的四元组E=(m,l,b,L)来描述一维下料问题的实例,其中l=(l1,l2,…,l m),b =(b1,b2,…,b m)T,m是坯料种类,L是原材料长度,l和b分别是每种坯料的长度和对应的需求量,非负整数向量a j=(a1j,a2j,…,a mj)T,a≠0且满足∑mi=1l i a ij≤L,(j=1,2,…,n),n是切割方案的总数,x j是切割方案a j的使用次数,则所建立的数学模型如下: min z=∑nj=1x j, s.t.∑nj=1a ij x j≥b i,i=1,…,m, x j≥0,x j是整数,j=1,…,n.(6) 与式(6)相应的松驰模型为 min z=∑nj=1x j, s.t.∑nj=1a ij x j≥b i,i=1,…,m, x j≥0,j=1,…,n.(7) 设Z3=Z3(E),Z c=Z c(E)分别表示(6)和(7)的最佳解,Δ(E)∶=Z3(E)-Z c(E). Δ(E)<1,实例E具有整数上界取整性质(IRUP,integer round2up property) Δ(E)≥1,实例E具有非整数上界取整性质(non2IRUP)501第24卷 第1期 张春玲等:一维优化下料问题 Δ(E)<2,实例E具有可修改的上界取整性质(MIRUP,modified integer round2up property) 文献[16]中对具有MIRUP的实例的定义为Z3(E)≤[Z c(E)]+1,猜想标准一维下料问题都具有MIRUP.non2IRUP的实例相对出现的较少一些,文献[19]中给出了有效构造non2IRUP实例的方法,对于MIRUP的猜想还未证明.4 结 论 讨论了一维下料问题的概念、模型、算法,而与下料问题类似的问题如装货、背包等问题,其模型和算法与下料问题的模型与算法都有相似之处,两者可以互相借鉴.高维下料问题,特别是二维不规则图形的下料问题是目前研究的热点,也是难度较大的一个问题.研究一维下料为研究高维下料问题提供了一定的理论基础.另外,由于下料问题与生产实践密切相关,这方面的研究结果有助于提高工厂经济效益.参考文献[1]H inxman A I.The trim-loss and ass ortment problems:A survey[J].European Journal of Operational Research,1980,(5):8 -18.[2]Cheng C H,Feiring B R,Cheng T C E.The cutting stock prob2lem2A survey[J].International Journal of Production econom ics, 1994,(36):291-305.[3]Dyck off H.A ty pology of cutting and packing problems[J].EuropeanJournal of O perational Research,1990,(44):145-159.[4]G radisar M,Resinovic G,K ljajic M.Evaluation of alg orithms forone2dimensional cutting[J].C om puters&Operations Research, 2002,(29):1207-1220.[5]G radisar M,K ljajic M,Resinovic G,et al.A sequential heuristicprocedure for one2dimensional cutting[J].European Journal of Op2 erational Research,1999,(114):557-568.[6]G ilm ore P C,G om ory R E.A linear programm ing approach to thecutting2stock problem[J].Operations Research,1961,(9): 849-859.[7]G ilm ore P C,G om ory R E.A linear programm ing approach to thecutting2stock problem:partⅡ[J].Operations Research,1963,(11):863-888.[8]Haessler R W.A note on com putational m odification to theG ilm ore2G om ory cutting stock alg orithm[J].Operations Re2search,1980,28(4):1001-1005.[9]Valerio DE Carvalho J M.Exact s olution of cutting stock problemsusing column generation and branch and bound[J].Int.T rans.Opl Res,1998,5(1):35-44.[10]Vanderbeck F.C om putational study of a column generation alg o2rithm for bin packing and cutting stock problems[J].M ath.Program,1999,(86):565-594.[11]G radisar M,Resinovic G,K ljajic M.A hybrid approach for op2tim ization of one2dimensional cutting[J].European Journal of Operational Research,1999,(119):719-728.[12]W augner Bret J.A genetic alg orithm s olution for one2dimensionalbundled stock cutting[J].European Journal of Operational Re2 search,1999,(117):368-381.[13]Liang K o2Hsin,Y ao X in,Newton C,et al.A new ev olutionaryapproach to cutting stock problems with and without contiguity [J].C om puter&Operations Research,2002,(29):1641-1659.[14]刘道海,方 毅,黄樟灿.一种求解组合优化问题的演化算法[J].武汉大学学报(理学版),2002,48(3):315-318. [15]李元香,张进波,徐静雯,等.基于变长编码求解一维下料问题的演化算法[J].武汉大学学报(理学版), 2001,47(3):289-293.[16]S cheithauer G,T ern o J.T he m odified integer round2up property of theone2dim ensional cutting stock problem[J].E uropean Journal of O per2 ational R esearch,1995,(84):562-571.[17]Nitsche Ch,Scheithauer G,T erno J.New case of the cuttingstock problem having MIRUP[J].M athematical M ethods of Op2 erations Research,1998,(48):105-115.[18]Nitsche Ch,Scheithauer G,T erno J.T ighter relaxations for thecutting stock problem[J].European Journal of Operational Re2 search,1999,(112):654-663.[19]Rietz J,Scheithauer G,T erno J.Fam ilies of non2IRUP instances ofthe one2dimensional cutting stock problem[J].Discrete Applied M athematics,2002,(121):229-245.Optimization of one2dimensional cutting stock problemZHANG Chun2ling,C UI Y ao2dong(Institute o f Mathematics and Computer Science,Guangxi Normal Univer sity,Guilin541004,China)Abstract:Cutting stock problem exits widely in production.Optimizing cutting stock is a method to im prove the using rate of materials and to increase the benefit of industry.It is significant for cutting stock problem research.The survey of one2dimensional cutting stock problem presents the general mathematic m odel of cutting stock problem with the dis2 cussion of the comm on method of one dimensional cutting stock problem and the alg orithm situation used.Related problems and application are als o discussed.K ey w ords:cutting stock;optimization;integer programming601桂 林 工 学 院 学 报 2004年。
![混合遗传算法求解一维优化下料问题[1].](https://img.taocdn.com/s1/m/9fdb2c3e5727a5e9856a619d.png)
