一維優(yōu)化下料問(wèn)題

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