王曉偉，劉 林，周 謐

(合肥工業(yè)大學 管理學院，安徽 合肥230009)

下料問題是將庫存的原材料切割成形狀不同、大小不一或是長短各異的多種零件以滿足顧客的需求，在鋼鐵企業(yè)、造紙業(yè)、紡織業(yè)和木材加工業(yè)中都有著廣泛的應 用 ，Dyckhoff[1]和 Wa¨scher[2]就 下 料 問 題 給 予 了 全 面 的分類。根據(jù)原材料和零件維數(shù)的數(shù)目，可以把下料問題劃分為一維下料問題、二維下料問題和多維下料問題。

一維下料問題是其中一個重要的組成部分，討論該問題是研究二維、三維等多維下料問題的基礎。不同學者在對待這個問題時也有著不同的研究重點，例如考慮最大限度地節(jié)約原材料，提高原材料利用率；如何減少排樣方案數(shù)；或是優(yōu)先使用較短原材料、增加最后一根余料長度；在規(guī)定的交貨期前完成生產任務等不同目標。經過調查發(fā)現(xiàn)，大部分研究一維下料問題的文獻很少考慮企業(yè)面臨生產力不足的情況，這時企業(yè)會面臨一定的損失或者盈利下降的問題，參考文獻[3]考慮了有交貨期限制的一維下料問題，通過合理安排生產進度來減少延遲所造成的損失；而參考文獻[4]、參考文獻[5]雖然針對不完全下料這種情況提出了解決方案，但也僅僅在如何提高原材料的利用率上加以研究，其他與此相關的文章也鮮見發(fā)表。任何時候企業(yè)的生產能力都是有限制的,包括加工能力和原材料儲備，而生產出來的各種零件也因為其市場價值或后期加工需求的緊迫程度不同所帶來的收益也不盡相同，當企業(yè)不得不面對這些突發(fā)情況時，合理安排價值高、需求緊迫的零件優(yōu)先生產、同時盡可能多地減少廢料、使企業(yè)的損失最小成為決策者必須考慮的問題之一，本文在這種情況下針對單一規(guī)格原材料的一維下料問題給出了一個以價值導向為基礎的、將問題實際量化的新模型。

1 模型結構

模型的建立需要考慮將兩個問題同時融入其中：一是企業(yè)自身能力可以滿足生產需求，包括生產能力滿足和原材料庫存充足，在這種情況下，下料方案所產生的廢料最小，原材料的利用率最高是決策者所關心的主要方面，這時模型所要解決的就只是充分利用原材料的問題；另一個方面是因為客觀原因導致的生產力受限或因為上游企業(yè)原材料供應不上而導致無法按時完成全部的生產任務，此時，將需求緊迫和延遲交貨所造成的損失價值高的零件優(yōu)先安排生產，保證企業(yè)總的損失最小是主要目標。

具體參數(shù)設定如下：假設企業(yè)共需要生產m種零件，i為待生產零件的編號，li為第i種零件的長度，vi為第i種零件對應的市場價值，di為第i種零件的需求數(shù)量，L則為原材料的長度，v為其單位價值，n為生產中使用的原材料總數(shù)量，aij為j號原材料所生產的第i種零件的數(shù)量，cj為j號原材料切割完畢后剩下的余料的長度，E為企業(yè)的生產能力或是原料總量限制。具體模型如下：

目標函數(shù)為：

約束條件是：

目標函數(shù)（1）保證了企業(yè)的總體損失最小，當滿足生產時，目標變?yōu)槭股a結束后產生的廢料損失最小；式（2）確保企業(yè)的生產總量不會超出需求的數(shù)量，使得產需平衡，這里認為超額生產的零件會帶來庫存、管理、耗損等一系列費用，同樣視為損失；式（3）則確保在一根原材料上生產出的零件長度之和不會超過原材料自身的長度，否則生產是無法進行的；式（4）限制企業(yè)實際能夠生產的零件數(shù)量。

2 蜂群遺傳算法

根據(jù)上述已經建立的模型，采用應用較多的遺傳算法求解問題。遺傳算法最早是在20世紀60年代末～70年代初由美國密歇根大學的Holland教授及其學生提出的。本文采用一種基于蜂群繁殖原理的改進型遺傳算法[6，7]，這種算法既能保證最優(yōu)個體的存活和交配的權利，又能保持種群中個體的多樣性。

在自然界中，整個蜂群是由蜂后、雄蜂和雌蜂三部分組成的，每個蜂群中有且僅有一只蜂后，蜂后也是整個蜂群中唯一一個具有生殖能力的蜜蜂。蜂后如果死亡或者失去繁殖能力，若干潛在可能成為新蜂后的雌蜂會互相競爭，直到一只勝出成為新一代的蜂后。蜂后會產生兩種類型的后代，一種發(fā)育成雌蜂，數(shù)量較多，沒有生育能力；而另一種則發(fā)育成雄蜂，數(shù)量較少，只負責和蜂后進行交配。

根據(jù)蜂群的生育原理，文中的蜂群遺傳算法的種群是由蜂后、雄蜂群和雌蜂群三者組成，其中蜂后的數(shù)量為1，雄蜂群個體的數(shù)量為N，雌蜂群個體的數(shù)量為M。

2.1 適應度函數(shù)

文中所述一維下料問題的優(yōu)化目標是使得下料方案的總損失最小，用適應度函數(shù)來評價算法時，一般規(guī)定適應度越大解的質量越好。根據(jù)上述原因，本文將適應度函數(shù)取為：

其中，分子是已生產零件的價值總和減去廢料的價值之和，分母為總需求零件的價值和，只有當需求滿足且沒有余料時，適應度函數(shù)值可以達到最大，取值為1，即原材料利用率達到了100%。

2.2 染色體編碼

編碼方式也稱為基因表達方式，種群中的每個個體即每個染色體由基因構成。本文中染色體的編碼采用零件全排列組合方式，即個體中的每個基因代表一個零件，例如由要切的 1個3號零件、2個 2號零件、1個8號零件、3個 5號零件隨機產生的編號序列(2，5，3，8，2，5，5)就是一個個體。 譯碼時，取一根原料，按順序從編號序列中取一個零件配切，直到所取的零件不能在此原料上配切為止，然后從序列中刪去已配切的零件編號，再取一根原料，對剩下的零件編號序列重復以上步驟直到生產滿足或是原材料用盡。

2.3 遺傳算子的選擇

2.3.1 交叉算子

雄蜂群按照交叉率和蜂后進行交叉操作，有利于產生新的高適應度的個體。交叉后產生一雄一雌的后代。用雄性后代取代父代，雌性后代臨時存放，以便作下一步處理。雄蜂群主要是為了保持較高的選擇壓力，以提高收斂速度。交叉是最重要的遺傳算子，本文中交叉算子的設計采用順序交叉方案，首先隨機確定兩個交叉位置，在交換交叉點之間的片段后，從第2個交叉位置起在原先父代個體中，刪除從另一個父代個體中交換過來的基因，然后從第2個交叉位置后填入剩余基因，從而生成兩個新的染色體。

2.3.2 變異算子

變異可以提供初始種群中所沒有的染色體，為種群提供新的內容。變異算子的設計多采用多點交換變異的方案，本文采用的變異算子皆為兩點變異，即在每個染色體中以概率P隨機選取染色體上的兩點進行交換。變異概率控制著新基因導入種群的比例，若太低，一些有用的基因就難以進入選擇；若太高，則會造成后代失去雙親繼承下來的好特性。

2.3.3 選擇算子

雌性蜂群按照錦標賽選擇的方法，將交叉后產生的雌性后代和原雌性蜂群中的個體進行選擇，重新組成M個個體的新雌蜂群。選擇方法為：兩個群體各隨機抽取x個個體進行比較，適應度高者保留，直到滿足新群體規(guī)模。這個新的雌性蜂群和原來的雌蜂群在個體上存在了一定數(shù)量的差異，所以需要重新選擇蜂后，方法是從新群體中選出適應度最大的個體與蜂后比較，若適應度高于原蜂后，那么就取代原蜂后；否則，原蜂后不做改變。錦標賽規(guī)模一般取為2。

2.3.4 抑制算子

蜂后為了維持自身的地位，需要對編碼相似程度較高的染色體進行抑制，抑制的閾值為T。具體的抑制方法是：若雌蜂群中的某些個體與蜂后之間的歐式距離D≤T，則進行抑制，刪除這些個體并以隨機個體取代。其他沒有被抑制的個體按照變異率進行變異。雌蜂群的目的主要是為了保持種群的多樣性，避免種群早熟收斂，隨時可以跳出局部峰值。歐式距離D表示如下：

其中參數(shù)d為染色體的長度，Abi為 A染色體的第 i個基因位，Bbi為B染色體的第i個基因位。

2.3.5 算法描述

蜂群遺傳算法BSGA(Bee-Swarm Genetic Algorithm)的過程描述為：

(1)隨機產生兩個群體，雄蜂群和雌蜂群，每個種群各有N和M個個體，在雌蜂群中選出適應度最大的個體做為蜂后；

(2)雄性個體經過輪盤選擇操作，按固定的交叉率與蜂后進行交叉，產生一個雄性和一個雌性后代，然后再進行變異操作；

(3)雌性蜂群按照錦標賽選擇的方法，將新產生的雌性后代和原雌性蜂群進行選擇操作，重組為新的M個個體的雌蜂群；

(4)對新產生的雌性群體實行蜂后排擠機制，對群體中與蜂后的歐式距離D在一定閾值之內的個體予以消滅，再隨機生成新的雌性個體，補齊該種群所消滅的個體的數(shù)量；

(5)若算法條件不滿足，回到過程(3)；否則，輸出蜂后作為全局最優(yōu)解；

(6)算法結束。

3 仿真案例分析

仿真程序采用PB編程，設置雄性種群數(shù)目為50，雌性種群數(shù)目為 50，染色體的交叉概率為0.8，變異概率為0.005，迭代最大次數(shù)為100次。

算例1：計算參考文獻[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的網線40段，求所需每箱長度為305 m的網線箱數(shù)及分割方案。因為本文中的目標函數(shù)和適應度函數(shù)中有價值系數(shù)的存在，所以賦予零件和原料每米相同的單位價值1，具體價值和長度不同的例子將在算例2中討論。

表1給出了利用本文給出的算法計算得到的結果，網線需要7箱，合計余料31 m，其中除了最長的那箱余料31 m，材料利用率為89.84%，其余的都加以充分利用。

表1 算例演算過程及結果

模型主要考慮解決的問題是不能完成全部生產任務時的情況，如何盡可能地在有限的資源內創(chuàng)造較高的價值是本文所關心的問題，在此給出算例2：假設需求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元。仿真結果如表2所示。

表2 算例演算過程及結果

從仿真結果中可以看到，在原材料不足（這里僅考慮原料不足的狀況，生產力不足的情況和此類似）時，需要考慮的是盡可能多地生產產品，創(chuàng)造價值。(v)表示考慮價值因素影響的切割方式，通過仿真結果中的數(shù)據(jù)對比可以看到，原料不滿足生產時，如果以價值為導向進行切割，將比不考慮價值因素的切割方式得到更多的利潤，這樣可以保證在突發(fā)情況下盡可能多地創(chuàng)造出價值。這時，企業(yè)可以把帶來價值高的自己進行生產，而將其余產品的加工進行外包等其他形式進行。實驗數(shù)據(jù)也證明了本文中提出的模型具有一定的實際使用意義。

本文針對企業(yè)實際的一維下料問題，運用蜂群遺傳算法求解。從實例結果來看，在保證最高生產價值的同時，原材料的利用率也令人滿意，對于在實際生產中應對突發(fā)狀況是很有意義的。

[1]DYCKHOFF H.A typology of cutting and packing problems[J].European Journal of Operational Research，1990，44(2)：145-159.

[2]WA¨SCHER 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 Operational Research，2010，201(3)：701-711.

[4]李培勇.多規(guī)格一維型材優(yōu)化下料[J].機械科學與技術，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].中國人工智能學會第 11屆全國學術年會論文集，2005：733-736.

[7]吳迪，李長榮，宋廣軍.基于蜂群遺傳算法的一維優(yōu)化下料問題[J].計算機技術與發(fā)展，2010，20(10)：82-85.