衛(wèi) 妍

（蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州730070）

生產(chǎn)批量問題是企業(yè)生產(chǎn)管理中一個常見的約束批量問題。主要目標(biāo)是確定最優(yōu)的生產(chǎn)批量，使得生產(chǎn)費用、生產(chǎn)準(zhǔn)備費用和庫存費用綜合指標(biāo)最小。MRPII是在MRP的基礎(chǔ)上發(fā)展起來的，它主要在考慮市場的需求、企業(yè)的生產(chǎn)能力和對用戶的服務(wù)水平等諸多因素的前提下安排企業(yè)的生產(chǎn)發(fā)展戰(zhàn)略:①長期規(guī)劃（公司層）；②中、短期生產(chǎn)計劃 （分廠或車間層）；③生產(chǎn)計劃的具體實現(xiàn)（車間或班組層）。在MRPII中，第②層的主要問題之一是生產(chǎn)計劃中的約束批量問題。對該問題的研究，可以指導(dǎo)在生產(chǎn)實踐中的批量生產(chǎn)問題，并為企業(yè)生產(chǎn)產(chǎn)生重大的經(jīng)濟(jì)效益。

1 模型建立

本文建立的是基于獨立需求的生產(chǎn)批量優(yōu)化問題的遺傳算法，所以對該批量生產(chǎn)問題做如下假設(shè)。

假設(shè):該問題中對各產(chǎn)品的需求是獨立的。原模型:

式中:T為計劃時段，如一年的12個月，一周5d等；n為產(chǎn)品的品種數(shù)；xit為決策變量；Iit為決策變量；dit為時段t內(nèi)對產(chǎn)品i的需求量；Si為生產(chǎn)產(chǎn)品i時的生產(chǎn)準(zhǔn)備費用，這一費用是由于機(jī)器要求更換加工產(chǎn)品而一次性發(fā)生的；ci為單位產(chǎn)品i的生產(chǎn)費用；hi為單位產(chǎn)品i的庫存費用；akit為時段單位產(chǎn)品i占用資源k的量；Akit為t時段產(chǎn)品i的生產(chǎn)準(zhǔn)備占用資源k的量；ckt為t時段資源k的可提供量；rij為產(chǎn)品j的生產(chǎn)過程中對產(chǎn)品i的需求量，由于本文是基于獨立需求的生產(chǎn)批量問題，所以rij＝0。式（1）的約束條件變?yōu)?/p>

2 問題求解

主要思想:

1）每次記錄下當(dāng)前較優(yōu)解，單點交叉法、交配概率Pc＝0.6。

2）交配后代直接替代雙親，而將沒有交配的雙親使其直接遺傳到下一代，從而使得交配后的群體規(guī)模同舊群體的規(guī)模相同。

3）再以p＝0.14的概率變異。更新當(dāng)前最優(yōu)染色體的進(jìn)化循環(huán)過程。

2.1 編 碼

本文xit，Iit為連續(xù)性決策變量，所以通過產(chǎn)生特定范圍的隨機(jī)數(shù)初始化為各階段生產(chǎn)品量，并且將其轉(zhuǎn)換為二進(jìn)制編碼當(dāng)作染色體，yit根據(jù)生產(chǎn)批量確定是否為1或0。當(dāng)xit＞0時，yit＝1；否則，yit＝0。初始種群

由于生成的初始解有可能不是可行解，可根據(jù)約束式（1）、式（2）、式（4）來剔除。

2.2 交配規(guī)則

本文使用單點交叉法:確定雙親后，隨機(jī)選擇一個交配位，然后交換交配位后面的基因，對換后形成兩個后代。

2.3 變 異

使用隨機(jī)函數(shù)Random（）先從種群中選出個體，再隨機(jī)選出一個生產(chǎn)階段中的某個產(chǎn)品，對其隨機(jī)位進(jìn)行變異。

2.4 種群選擇

計算過程中，通過計算獲得較小目標(biāo)函數(shù)值并將該個體的信息記錄下來，計算出概率，將大于設(shè)定概率的個體二進(jìn)制編碼兩兩交叉變異，獲得新的種群。此時計算出新種群的目標(biāo)函數(shù)值，與記錄中的目標(biāo)函數(shù)值作比較，將新舊種群中的優(yōu)秀個體再重新組成下一代新種群。依次重復(fù)，得到收斂目標(biāo)函數(shù)值。

3 算法及流程

在算法編寫過程中做到較優(yōu)種群的及時記錄和更新。本文在初始化種群時，為減少不可行解的產(chǎn)生，在產(chǎn)生同一階段的生產(chǎn)批量時，使用下式:

xct為t階段生產(chǎn)c的批量，其他同上。因此，產(chǎn)生的個體具有較強的可行性。

在交配函數(shù)中，采用雙親雙子交配規(guī)則進(jìn)行交叉后，對Iit和yit進(jìn)行計算和更新。然后進(jìn)行選擇變異，接下來剔除不可行的個體。為了保證種群的規(guī)模不變，在計算時，首先會將上次的記錄中未參與交配的個體加入計算種群中。

最后，經(jīng)過100次迭代，得到100次中最優(yōu)值和最差值、平均值，以及最優(yōu)與最差的差值，分別與最優(yōu)和最差的比。算法流程圖如圖1所示。

圖1 算法流程

4 計算結(jié)果與結(jié)論

本文采用VS2010對獨立需求生產(chǎn)批量優(yōu)化問題的遺傳算法進(jìn)行編程實現(xiàn)，在n＝7，Pc＝0.6，Pm＝0.14時，分別對階段T＝5，15，20，…，35進(jìn)行100次模擬計算，所得結(jié)果如表1所示。

為了加快該遺傳算法的收斂速度，本文在傳統(tǒng)二進(jìn)制遺傳算法中引入了記憶機(jī)制。應(yīng)用改進(jìn)的算法求解了一個具體實例，結(jié)果表明該算法不論在尋優(yōu)能力方面，還是在求解速度和穩(wěn)定性方面都取得很好的效果，能夠較好地解決基于獨立需求的約束生產(chǎn)批量計劃問題。

表1 算法結(jié)果

［1］邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計算方法［M］.北京:清華大學(xué)出版社，1999.

［2］潘正君，康立山.演化計算［M］.北京:清華大學(xué)出版社，1998.

［3］謝金星，姜啟源，邢文訓(xùn).能力受限的批量問題的數(shù)學(xué)模型與算法新進(jìn)展［J］.運籌學(xué)雜志，1996，15（1），1－12.

［4］唐立新，楊自厚，王夢光.單級無能力約束批量問題大小問題的遺傳搜索算法［J］.東北大學(xué)學(xué)報，1997（3）:46－48.

［5］王錫凡.電力系統(tǒng)優(yōu)化規(guī)劃［M］.北京:水利電力出版社，1990.

［6］李茂軍，童調(diào)生.單親遺傳算法及其全局收斂性分析［J］.自動化學(xué)報，1999，25（1）:68－71.

［7］李睿，孫有信，吳德瑄，等.基于遺傳算法的供應(yīng)鏈分層協(xié)調(diào)機(jī)制［J］.交通科技與經(jīng)濟(jì)，2012，14（1）:93－95.