第24卷第1期桂林工學(xué)院學(xué)報Vol. 24 No. 12004年1月JOURNAL OF GUILIN INSTITUTE OF TECHNOLOCYJan. 2004文章編號:1006 - 544X(2004)01 -0103 -04一維優(yōu)化下料問題，張春玲，崔耀東(廣西師范大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，廣西桂林541004)摘要:下料問題在生產(chǎn)中普遍存在， 優(yōu)化下料可以提高原材料利用率，是企業(yè)增加經(jīng)濟效益的途徑之一，對一維下料問題進行了探討, 給出- -維下料問題的一些概念和數(shù)學(xué)模型，討論解決-維下料問題的常用算法以及算法的適用情況，分析與之相關(guān)的一些問題和具體的實際應(yīng)用.關(guān)鍵詞:下料;最優(yōu)化;整數(shù)規(guī)劃中圖分類號: TB114. 1; 0224文獻標(biāo)識碼: A隨著全球資源的日益匱乏，人們對資源利用Dyckoff{3) 提出下料問題可以根據(jù)4種特征來問題的研究愈來愈重視，下料問題就是其中之分類: 維度、分配類型、大物件的分類和小項的-[1-31. 最大限度的節(jié)約原材料，提高原材料利 分類. Dycof描述- 維下料問題為I/V/D/M: 1用率是生產(chǎn)中提高效益的- -個重要手段， 在機械指的是- 維問題， v指的是所有的小項必須從一行業(yè)、造紙、服裝、木材等行業(yè)，下料問題都有大物件中產(chǎn)生，D的意思是所有大物件是不同的，廣泛的實際應(yīng)用下 料問題就是研究怎樣在客觀M是指小項之間不同.條件和可以接受的時間下優(yōu)化排樣得到最優(yōu)解或如果原材料是同一長度或只有少數(shù)的組(組.近似理論最優(yōu)解.下料問題根據(jù)維數(shù)- 般可 分為中長度相近)，可得到標(biāo)準(zhǔn)一維下料問題 (SID--維下料和二維下料，本文主要對一維下料問題CSP)，對于S1D- CSP給出切割方案的概念，切進行討論.割方案是用1根原材料切割各種不同規(guī)格的坯料1一維 下料問題的概念和數(shù)學(xué)模型時，保持坯料規(guī)格的種類不變，只改變切割數(shù)量.-維下料問題( one-dimensional cutting stock將有效的切割方案集中起來就是最后的下料方式.problem,簡稱1CSP )是在已知原材料和顧客需S1D- CSP問題可以描述如下:求坯料的情況下優(yōu)化下料使原材料的使用率達(dá)到l;一坯料長度,i = 1,"',n;最大或廢料達(dá)到最小，根據(jù)原材料長度是否相等,d;-每種坯料的需求數(shù)量,i = 1,.,n;一維優(yōu)化下料可以分為單一型材的優(yōu)化下料和多4k-原材料長度,h = 1,.,P,型材的優(yōu)化下料.單-- 型材的優(yōu)化下料很多文獻切割方案 c可以用如下一一個向量a來表示:中都已有討論，而多型材的優(yōu)化下料在型材類型Clck ,Q2ch.""" ,Anck;(I)比較多的時候，可以將型材按長度相近進行分組，先選組，再從組中選擇型材下料，由此引發(fā)出分滿足Zlauk≤Lz,且alck≥0,是整數(shù). (2)組問題.分組有利于節(jié)約原材料，但是如果分組aish 表示l;在特定的切割方案中出現(xiàn)的次數(shù),xak表太細(xì)，會導(dǎo)致增加庫存管理的負(fù)擔(dān).示切割方案c在原材料k上使用的次數(shù),表示在原收稿日期: 2003 -05 -12基金項目:廣西自然科學(xué)基金資助項目(桂科基0236017)作者簡介:張春玲(1978-), 女,碩士研究生,研究方向: CAD/CAM.中國煤化工MYHCNMHG104桂林工學(xué)院學(xué)報2004年材料h上滿足(2)式的切割方案的總數(shù)，那么將會13 535 cm的原材料上切割5根長度為304 cm的坯有如下的整數(shù)規(guī)劃模型:料，7根長度為319 cm的坯料，10 根長度為397min2 2xaL，(3)cm的坯料，14根長度為415 cm的坯料，不切割長度為366 cm的坯料(為0表示不切割).s.2 ZaxaLx≥d,i=1,,n; (4) .以需求為導(dǎo)向方法得到的切割量會出現(xiàn)比需xek≥0且為整數(shù),c = 1,h;k = 1,.,p. (5)求量少的情況，其方法一般是基于啟發(fā)式算法;從SID- CSP所對應(yīng)的數(shù)學(xué)模型中可知SID -以方案為導(dǎo)向方法得到的切割量則會出現(xiàn)比需求CSP所優(yōu)化的目標(biāo)是最小化被切割的原材料數(shù)量.量多的情況，其方法- .般是基于線性規(guī)劃的，兩當(dāng)原材料的長度全都不同時所建立的數(shù)學(xué)模型與種方法有各自的優(yōu)缺點，可進行適當(dāng)?shù)慕M合得到上述模型是有所不同的如Gradisar等人[4]提出良好的下料效果.-維下料的數(shù)學(xué)模型早在1939年就已由Kan-的GID-CSP ( gencration one-dimensional cutingtorovich提出下 料問題的求解很大程度上依賴于stock problem)， 其數(shù)學(xué)模型中優(yōu)化的目標(biāo)是最小模型的建立，可根據(jù)具體情況進行模型的補充和.化廢料，而且這一-模型中原材料的長度全都不同.修改，一維下料問題所建立的數(shù)學(xué)模型是-一個整Dekof(]) 將優(yōu)化下料過程分為2類:以需求數(shù)規(guī)劃問題， 求解整數(shù)規(guī)劃問題一般使用分支定項為導(dǎo)向(item-oriented) 和以方案為導(dǎo)向( pat-界法或割平面法、分支定界法是一種隱枚舉法，tem- oiemte)的方法，以需求項為導(dǎo)向的方法是效果的好壞取決 于分支的模式和界的確定，但下對顧客的每一-需求項進行單獨的處理，直到一需料問題的求解有其自身的特點，下面討論- -維下求項處理完才處理下-需求項;以方案為導(dǎo)向的料問題的常用算法.方法是把幾種坯料組合進行下料，一次切割可得到不同規(guī)格的坯料.以方案為導(dǎo)向的方法只能對2 - 維下料問題的常用算法原材料長度是單一的或者原材料分為少數(shù)的組時一維下料問題是組合優(yōu)化中的一個經(jīng)典問題，有效，對于原材料的長度都不相同的情況只能用從計算的復(fù)雜性理論上看，優(yōu)化下料問題屬于NP以需求項為導(dǎo)向的方法(表1).難問題，即至今還不存在多項式界算法. NP 難問表1原材料與坯料[5]題的求解通常使用接近最優(yōu)解的近似算法實現(xiàn).Table 1 Stock and ilem求解一維下料問題的算法(1有基于線性規(guī)劃的方顧客需求坯料原材料法、分支定界法、動態(tài)規(guī)劃法、啟發(fā)式算法、模需求需求長度需求量原材料長度編號/cm(根/a擬退火算法、演化算法等.304235352. 1基于線性規(guī)劃的方法3193811 301以方案為導(dǎo)向的方法大多是基于線性規(guī)劃的39794084159 341方法(LPM). 此類方法可以減少廢料，但是會產(chǎn)36生多于需求量的切割量，只適用于單一型材或者是只有少量組的下料?；诰€性規(guī)劃的方法是將以需求項為導(dǎo)向的方法是先選擇第1種需求建立的整數(shù)規(guī)劃問題進行松弛，按照線性規(guī)劃進壞料進行處理，第1種坯料在原材料2上切割6行求解，對得到的解取整、基于線性規(guī)劃的方法根，在原材料1上切制6根，這樣就得到12根可以追 溯到Gilmore和Comory的列生成(column304 cm長的坯料，再選擇第2種坯料處理，在原generaion) 方法[6-7]、 當(dāng)原材料和帶求的坯料的材料4上切割21根，在原材料3切割4根，在原種類相當(dāng)多或者 是坯料的長度特別短而原材料的材料2上切割6根，在原材料1上切割7根，共得長度特別長時， 將導(dǎo)致切割方案太多，--次性將.到38根長度為319 cm的坯料，其它情況類似.若所有的切割方案 全部枚舉出來是不可能的，文獻是以方案為導(dǎo)向的方法，首先將坯料進行組合，[6]中國煤化工，進而利用迭代如(5, 7, I0, 14, 0)方案表示在第1種長度為的方Y(jié)HCNMHG持定的方法和動第24卷第1期張春玲等:一維優(yōu)化下料問題105態(tài)規(guī)劃求解得到進人基的列，最后對主規(guī)劃的解得到近似的最優(yōu)解; 模擬退火算法是基于金屬退取整. Hassler [8] 對Gilmore-Gomory 的算法進行火的機理 建立起來的一種全局最優(yōu)化方法，它能了改進，修改了初始解，利用更強的約束條件控夠以隨機搜 索技術(shù)從概率的意義上找出目標(biāo)函數(shù)制切割方案的產(chǎn)生以減少切割方案的變更，Vale~ 的全局最小點. W augner 12]利用遺傳算法解決一riol9]將列生成算法與分支定界法相結(jié)合,利用弧維下料問題并考慮了廢料、庫存使用和最后存貨流模型，1種切割方案對應(yīng)于1條路徑，在弧流的等問題. Liang[13])用只使用變異算 子的演化規(guī)劃同變量上進行分支.分支價值算法( branch-and-時對2個目標(biāo)進行優(yōu)化，采用了3PS和SRI兩個price)又稱整數(shù)規(guī)劃列生成算法，它是在分支定變異算子， 劉道海等[4]從蟻群算法中信息素的概界樹的每個結(jié)點上使用column gereratin 算法、念得到啟示， 將信息素的觀點引入道變異算子中，Vanderheck[I0]介紹了- -種基于列生成的算法，對用與適應(yīng)值聯(lián) 系在一起的信息素的變化來引導(dǎo)每分支定界法進行擴展，討論分支模式，提出了一個基因位的變異， 并把這-算法運用到優(yōu)化下料種偽多項式啟發(fā)式，并在整數(shù)規(guī)劃列生成算法中中李元香、張進波、徐靜雯等115]提出- -種基于應(yīng)用.變長編碼求解- - .維下料問題的演化算法，收到了2.2基于啟發(fā)式算法的方法比較好的結(jié)果，材料平均利用率可達(dá)到97%.當(dāng)原材料的長度都不相同的時候只能用以需3 相關(guān)問題求項為導(dǎo)向的方法求解，這有2種可能:用確切的方法(分支定界或動態(tài)規(guī)劃)或者是用形式為研究中發(fā)現(xiàn)[16 -18]對于1CSP的很多實例，下SHP (Sequence Heuristic Procedure) 的近似算法.料問題所建 立的整數(shù)規(guī)劃問題的最優(yōu)解與利用松啟發(fā)式算法所使用的啟發(fā)式一般只適用于特定的 弛后線性規(guī) 劃問題求得的最優(yōu)解具有一定的性質(zhì).問題，無通用性，有效的啟發(fā)式對問題的求解是這些性質(zhì)有 利于確定下料實例所屬類別，簡化計很有用的，但是有時尋找-一個有效的啟發(fā)式比解算量, 對高維下料問題的研究也有幫助.引用文決問題本身還要困難.啟發(fā)式算法得到的結(jié)果一獻[18]中的四元組E= (m, I, b, L)來描述般不會太差，通常也可將啟發(fā)式進行組合. Gra- - -維下料問題的實例，其中I = (h,12,-lm),bdisar[5]將一種字典 排序的方法應(yīng)用于多型材下料= (b,2,.",bmn)T ,m是坯料種類,L是原材料長問題，以需求項為導(dǎo)向，用啟發(fā)式(SHP) 最小度,1和b 分別是每種坯料的長度和對應(yīng)的需求量，化約束條件的影響，并設(shè)置參數(shù)Y來調(diào)整廢料與非負(fù)整數(shù)向量aj;= (arj,ny,-",am)",a≠0且滿下料方案的復(fù)雜度之間的權(quán)、將基于線性規(guī)劃的足Zlay≤L,(j= 1,2,-- ,n) ,n是切割方案的總方法和基于啟發(fā)式的方法相結(jié)合["，用2個階段數(shù),是切割方案a;的使用次數(shù),則所建立的數(shù)學(xué)求解:首先將問題轉(zhuǎn)換成可用LPM求解的模式，模型如下:然后將切割方案中包含比需求量多的解刪除，最后的結(jié)果是兩部分的解之和: S=SLPM +SsHp，這minz = 2x，s.t.ait;≥bi;,i = 1,,m,樣既能減少廢料又能得到確切的需求量.x;≥0,j是整數(shù),j = 1,,n.(6)2.3 其它算法與式(6)相應(yīng)的松馳模型為遺傳算法和模擬退火算法用于優(yōu)化下料問題中效果良好:遺傳算法是基于自然選擇和基因遺minz =二x，s.a;q;≥b;,i = 1,,m,傳的搜索算法，具有很好的魯棒性，在解決復(fù)雜xj≥0j = 1,.,n.(7)問題的優(yōu)化方面非常適用前面已提到， 當(dāng)切割設(shè)Z* =Z*(E) ,Z。= Z。(E)分別表示(6)和方案特別多時一次性枚舉是不可能的，利用遺傳(7) 的最佳解, 0(E): =Z"(E) - 2。(E).算法，先隨機的生成-些切割方案,形成初始種0(E)