摘  要： 針對一維下料優(yōu)化問題，根據(jù)企業(yè)的實際生產(chǎn)情況，考慮能夠滿足和不滿足生產(chǎn)兩種情況，建立一個新的優(yōu)化模型，并使用蜂群遺傳算法求解方案。用各零件長度的一個排列作為一個染色體，每個零件的長度作為染色體的一個基因，根據(jù)蜂群原理設(shè)置兩個不同的種群，種群1用于全局搜索，種群2用于局部搜索。實驗結(jié)果表明，該模型具有一定的實用價值。
關(guān)鍵詞： 一維下料問題；優(yōu)化下料；蜂群遺傳算法；染色體；種群；抑制算子

    下料問題是將庫存的原材料切割成形狀不同、大小不一或是長短各異的多種零件以滿足顧客的需求，在鋼鐵企業(yè)、造紙業(yè)、紡織業(yè)和木材加工業(yè)中都有著廣泛的應(yīng)用，Dyckhoff[1]和Wascher[2]就下料問題給予了全面的分類。根據(jù)原材料和零件維數(shù)的數(shù)目，可以把下料問題劃分為一維下料問題、二維下料問題和多維下料問題。
    一維下料問題是其中一個重要的組成部分，討論該問題是研究二維、三維等多維下料問題的基礎(chǔ)。不同學(xué)者在對待這個問題時也有著不同的研究重點，例如考慮最大限度地節(jié)約原材料，提高原材料利用率；如何減少排樣方案數(shù)；或是優(yōu)先使用較短原材料、增加最后一根余料長度；在規(guī)定的交貨期前完成生產(chǎn)任務(wù)等不同目標(biāo)。經(jīng)過調(diào)查發(fā)現(xiàn)，大部分研究一維下料問題的文獻(xiàn)很少考慮企業(yè)面臨生產(chǎn)力不足的情況，這時企業(yè)會面臨一定的損失或者盈利下降的問題，參考文獻(xiàn)[3]考慮了有交貨期限制的一維下料問題，通過合理安排生產(chǎn)進(jìn)度來減少延遲所造成的損失；而參考文獻(xiàn)[4]、參考文獻(xiàn)[5]雖然針對不完全下料這種情況提出了解決方案，但也僅僅在如何提高原材料的利用率上加以研究，其他與此相關(guān)的文章也鮮見發(fā)表。任何時候企業(yè)的生產(chǎn)能力都是有限制的,包括加工能力和原材料儲備，而生產(chǎn)出來的各種零件也因為其市場價值或后期加工需求的緊迫程度不同所帶來的收益也不盡相同，當(dāng)企業(yè)不得不面對這些突發(fā)情況時，合理安排價值高、需求緊迫的零件優(yōu)先生產(chǎn)、同時盡可能多地減少廢料、使企業(yè)的損失最小成為決策者必須考慮的問題之一，本文在這種情況下針對單一規(guī)格原材料的一維下料問題給出了一個以價值導(dǎo)向為基礎(chǔ)的、將問題實際量化的新模型。
1 模型結(jié)構(gòu)
    模型的建立需要考慮將兩個問題同時融入其中：一是企業(yè)自身能力可以滿足生產(chǎn)需求，包括生產(chǎn)能力滿足和原材料庫存充足，在這種情況下，下料方案所產(chǎn)生的廢料最小，原材料的利用率最高是決策者所關(guān)心的主要方面，這時模型所要解決的就只是充分利用原材料的問題；另一個方面是因為客觀原因?qū)е碌纳a(chǎn)力受限或因為上游企業(yè)原材料供應(yīng)不上而導(dǎo)致無法按時完成全部的生產(chǎn)任務(wù)，此時，將需求緊迫和延遲交貨所造成的損失價值高的零件優(yōu)先安排生產(chǎn)，保證企業(yè)總的損失最小是主要目標(biāo)。
    具體參數(shù)設(shè)定如下：假設(shè)企業(yè)共需要生產(chǎn)m種零件，i為待生產(chǎn)零件的編號，li為第i種零件的長度，vi為第i種零件對應(yīng)的市場價值，di為第i種零件的需求數(shù)量，L則為原材料的長度，v為其單位價值，n為生產(chǎn)中使用的原材料總數(shù)量，aij為j號原材料所生產(chǎn)的第i種零件的數(shù)量，cj為j號原材料切割完畢后剩下的余料的長度，E為企業(yè)的生產(chǎn)能力或是原料總量限制。具體模型如下：
  
    目標(biāo)函數(shù)（1）保證了企業(yè)的總體損失最小，當(dāng)滿足生產(chǎn)時，目標(biāo)變?yōu)槭股a(chǎn)結(jié)束后產(chǎn)生的廢料損失最小；式（2）確保企業(yè)的生產(chǎn)總量不會超出需求的數(shù)量，使得產(chǎn)需平衡，這里認(rèn)為超額生產(chǎn)的零件會帶來庫存、管理、耗損等一系列費用，同樣視為損失；式（3）則確保在一根原材料上生產(chǎn)出的零件長度之和不會超過原材料自身的長度，否則生產(chǎn)是無法進(jìn)行的；式（4）限制企業(yè)實際能夠生產(chǎn)的零件數(shù)量。
2 蜂群遺傳算法
    根據(jù)上述已經(jīng)建立的模型，采用應(yīng)用較多的遺傳算法求解問題。遺傳算法最早是在20世紀(jì)60年代末～70年代初由美國密歇根大學(xué)的Holland教授及其學(xué)生提出的。本文采用一種基于蜂群繁殖原理的改進(jìn)型遺傳算法[6，7]，這種算法既能保證最優(yōu)個體的存活和交配的權(quán)利，又能保持種群中個體的多樣性。
    在自然界中，整個蜂群是由蜂后、雄蜂和雌蜂三部分組成的，每個蜂群中有且僅有一只蜂后，蜂后也是整個蜂群中唯一一個具有生殖能力的蜜蜂。蜂后如果死亡或者失去繁殖能力，若干潛在可能成為新蜂后的雌蜂會互相競爭，直到一只勝出成為新一代的蜂后。蜂后會產(chǎn)生兩種類型的后代，一種發(fā)育成雌蜂，數(shù)量較多，沒有生育能力；而另一種則發(fā)育成雄蜂，數(shù)量較少，只負(fù)責(zé)和蜂后進(jìn)行交配。
    根據(jù)蜂群的生育原理，文中的蜂群遺傳算法的種群是由蜂后、雄蜂群和雌蜂群三者組成，其中蜂后的數(shù)量為1，雄蜂群個體的數(shù)量為N，雌蜂群個體的數(shù)量為M。
2.1 適應(yīng)度函數(shù)
    文中所述一維下料問題的優(yōu)化目標(biāo)是使得下料方案的總損失最小，用適應(yīng)度函數(shù)來評價算法時，一般規(guī)定適應(yīng)度越大解的質(zhì)量越好。根據(jù)上述原因，本文將適應(yīng)度函數(shù)取為：
  
其中，分子是已生產(chǎn)零件的價值總和減去廢料的價值之和，分母為總需求零件的價值和，只有當(dāng)需求滿足且沒有余料時，適應(yīng)度函數(shù)值可以達(dá)到最大，取值為1，即原材料利用率達(dá)到了100%。
2.2 染色體編碼
    編碼方式也稱為基因表達(dá)方式，種群中的每個個體即每個染色體由基因構(gòu)成。本文中染色體的編碼采用零件全排列組合方式，即個體中的每個基因代表一個零件，例如由要切的1個3號零件、2個2號零件、1個8號零件、3個5號零件隨機(jī)產(chǎn)生的編號序列(2，5，3，8，2，5，5)就是一個個體。譯碼時，取一根原料，按順序從編號序列中取一個零件配切，直到所取的零件不能在此原料上配切為止，然后從序列中刪去已配切的零件編號，再取一根原料，對剩下的零件編號序列重復(fù)以上步驟直到生產(chǎn)滿足或是原材料用盡。
2.3 遺傳算子的選擇
2.3.1 交叉算子
    雄蜂群按照交叉率和蜂后進(jìn)行交叉操作，有利于產(chǎn)生新的高適應(yīng)度的個體。交叉后產(chǎn)生一雄一雌的后代。用雄性后代取代父代，雌性后代臨時存放，以便作下一步處理。雄蜂群主要是為了保持較高的選擇壓力，以提高收斂速度。交叉是最重要的遺傳算子，本文中交叉算子的設(shè)計采用順序交叉方案，首先隨機(jī)確定兩個交叉位置，在交換交叉點之間的片段后，從第2個交叉位置起在原先父代個體中，刪除從另一個父代個體中交換過來的基因，然后從第2個交叉位置后填入剩余基因，從而生成兩個新的染色體。
2.3.2 變異算子
    變異可以提供初始種群中所沒有的染色體，為種群提供新的內(nèi)容。變異算子的設(shè)計多采用多點交換變異的方案，本文采用的變異算子皆為兩點變異，即在每個染色體中以概率P隨機(jī)選取染色體上的兩點進(jìn)行交換。變異概率控制著新基因?qū)敕N群的比例，若太低，一些有用的基因就難以進(jìn)入選擇；若太高，則會造成后代失去雙親繼承下來的好特性。
2.3.3 選擇算子
    雌性蜂群按照錦標(biāo)賽選擇的方法，將交叉后產(chǎn)生的雌性后代和原雌性蜂群中的個體進(jìn)行選擇，重新組成M個個體的新雌蜂群。選擇方法為：兩個群體各隨機(jī)抽取x個個體進(jìn)行比較，適應(yīng)度高者保留，直到滿足新群體規(guī)模。這個新的雌性蜂群和原來的雌蜂群在個體上存在了一定數(shù)量的差異，所以需要重新選擇蜂后，方法是從新群體中選出適應(yīng)度最大的個體與蜂后比較，若適應(yīng)度高于原蜂后，那么就取代原蜂后；否則，原蜂后不做改變。錦標(biāo)賽規(guī)模一般取為2。
2.3.4 抑制算子
    蜂后為了維持自身的地位，需要對編碼相似程度較高的染色體進(jìn)行抑制，抑制的閾值為T。具體的抑制方法是：若雌蜂群中的某些個體與蜂后之間的歐式距離D≤T，則進(jìn)行抑制，刪除這些個體并以隨機(jī)個體取代。其他沒有被抑制的個體按照變異率進(jìn)行變異。雌蜂群的目的主要是為了保持種群的多樣性，避免種群早熟收斂，隨時可以跳出局部峰值。歐式距離D表示如下：
    
其中參數(shù)d為染色體的長度，Abi為A染色體的第i個基因位，Bbi為B染色體的第i個基因位。
2.3.5 算法描述
    蜂群遺傳算法BSGA(Bee-Swarm Genetic Algorithm)的過程描述為：
    (1)隨機(jī)產(chǎn)生兩個群體，雄蜂群和雌蜂群，每個種群各有N和M個個體，在雌蜂群中選出適應(yīng)度最大的個體做為蜂后；
    (2)雄性個體經(jīng)過輪盤選擇操作，按固定的交叉率與蜂后進(jìn)行交叉，產(chǎn)生一個雄性和一個雌性后代，然后再進(jìn)行變異操作；
    (3)雌性蜂群按照錦標(biāo)賽選擇的方法，將新產(chǎn)生的雌性后代和原雌性蜂群進(jìn)行選擇操作，重組為新的M個個體的雌蜂群；
    (4)對新產(chǎn)生的雌性群體實行蜂后排擠機(jī)制，對群體中與蜂后的歐式距離D在一定閾值之內(nèi)的個體予以消滅，再隨機(jī)生成新的雌性個體，補齊該種群所消滅的個體的數(shù)量；
    (5)若算法條件不滿足，回到過程(3)；否則，輸出蜂后作為全局最優(yōu)解；
    (6)算法結(jié)束。
3 仿真案例分析
    仿真程序采用PB編程，設(shè)置雄性種群數(shù)目為50，雌性種群數(shù)目為50，染色體的交叉概率為0.8，變異概率為0.005，迭代最大次數(shù)為100次。
    算例1：計算參考文獻(xiàn)[7]中的例子?，F(xiàn)需總長度2 104 m，長度分別為4 m、6 m、10 m、13 m、14 m、19 m、20 m、21 m、22 m、28 m、32 m、33 m、36 m、38 m、38 m、40 m、41 m、42 m、48 m、48 m、50 m、55 m、57 m、60 m、64 m、66 m、67 m、72 m、76 m、77 m、83 m、84 m、85 m、86 m、91 m、91 m、94 m、94 m、99 m、100 m的網(wǎng)線40段，求所需每箱長度為305 m的網(wǎng)線箱數(shù)及分割方案。因為本文中的目標(biāo)函數(shù)和適應(yīng)度函數(shù)中有價值系數(shù)的存在，所以賦予零件和原料每米相同的單位價值1，具體價值和長度不同的例子將在算例2中討論。
    表1給出了利用本文給出的算法計算得到的結(jié)果，網(wǎng)線需要7箱，合計余料31 m，其中除了最長的那箱余料31 m，材料利用率為89.84％，其余的都加以充分利用。

    模型主要考慮解決的問題是不能完成全部生產(chǎn)任務(wù)時的情況，如何盡可能地在有限的資源內(nèi)創(chuàng)造較高的價值是本文所關(guān)心的問題，在此給出算例2：假設(shè)需求10種零件，長度分別為135 cm、31 cm、23 cm、92 cm、28 cm、257 cm、14 cm、110 cm、55 cm、147 cm，需求量分別為75、250、250、45、200、50、920、67、100、15個，零件價值分別為217、44、30、113、33、450、18、169、63、277元，原料長度為600 cm，單位價值為0.5元。仿真結(jié)果如表2所示。

    從仿真結(jié)果中可以看到，在原材料不足（這里僅考慮原料不足的狀況，生產(chǎn)力不足的情況和此類似）時，需要考慮的是盡可能多地生產(chǎn)產(chǎn)品，創(chuàng)造價值。(v)表示考
慮價值因素影響的切割方式，通過仿真結(jié)果中的數(shù)據(jù)對比可以看到，原料不滿足生產(chǎn)時，如果以價值為導(dǎo)向進(jìn)行切割，將比不考慮價值因素的切割方式得到更多的利潤，這樣可以保證在突發(fā)情況下盡可能多地創(chuàng)造出價值。這時，企業(yè)可以把帶來價值高的自己進(jìn)行生產(chǎn)，而將其余產(chǎn)品的加工進(jìn)行外包等其他形式進(jìn)行。實驗數(shù)據(jù)也證明了本文中提出的模型具有一定的實際使用意義。
    本文針對企業(yè)實際的一維下料問題，運用蜂群遺傳算法求解。從實例結(jié)果來看，在保證最高生產(chǎn)價值的同時，原材料的利用率也令人滿意，對于在實際生產(chǎn)中應(yīng)對突發(fā)狀況是很有意義的。
參考文獻(xiàn)
[1] DYCKHOFF H.A typology of cutting and packing problems [J].European Journal of Operational Research，1990，44(2)：145-159.
[2] WASCHER G，HAUSSNER H，SCHUMANN H.An improved  typology of cutting and packing problems[J].European Journal of Operational Research，2007，183(3)：1109-1130.
[3] HARALD R，VOSSEN W M.The one-dimensional cutting stock problem with due dates[J].European Journal of Oper ational Research，2010，201(3)：701-711.
[4] 李培勇.多規(guī)格一維型材優(yōu)化下料[J].機(jī)械科學(xué)與技術(shù)，2003，22(Z1)：80-83.
[5] POLDI K C，ARENALES M N.Heuristics for the one-dimensional cutting stock problem with limited multiple stock  lengths[J].Computers and Operations Research，2009，36(6)：2074-2081.
[6] 吳迪，崔榮一.蜂群遺傳算法[C].中國人工智能學(xué)會第11屆全國學(xué)術(shù)年會論文集，2005：733-736.
[7] 吳迪，李長榮，宋廣軍.基于蜂群遺傳算法的一維優(yōu)化下料問題[J].計算機(jī)技術(shù)與發(fā)展，2010，20(10)：82-85.