一種隨機需求環(huán)境下固定批量生產組織模型優(yōu)化算法

孫改玲， 龔 利

（湖北華電襄陽發(fā)電有限公司，湖北 襄陽 441041）

0 引 言

企業(yè)在組織生產時，應盡可能做到以銷定產，以降低庫存、缺貨及相應的成本。學者們的研究大多集中于批量可以連續(xù)變動，或者基本可以連續(xù)變動的企業(yè)。近期，SOX，Muckstadt、應保勝、曹于忠[1－4]等注意到了市場需求的隨機性，對單層、多產品、能力受限的批量問題進行了深入研究；劉曉[5]采用啟發(fā)式遺傳算法建立了單產品生產計劃模型；夏天、徐克林[6]等采用作業(yè)成本法建立了單產品經濟生產批量模型。然而，現實中，企業(yè)的產品往往不止一種，而且很多企業(yè)的生產不具有無限可分性（如煉鋼企業(yè)的產量必須是單個高爐容量的整數倍），生產批量的選擇范圍是有限的；部分企業(yè)甚至只有幾種固定的生產組織方式，這樣問題就從尋找最優(yōu)批量轉化為選擇最優(yōu)批量。企業(yè)只能根據預測的銷量確定一個相近的產量，結果往往是當期缺貨或者有剩余。在當期利潤最大或者成本最低的目標下，企業(yè)的決策就是在缺貨所對應的產量與剩余所對應的產量之間做出選擇，相對比較容易。

在現實生活中，企業(yè)的生產經營活動是一個永續(xù)的過程，企業(yè)沒有銷完的產品可用于下一階段的銷售，當期的生產安排有可能影響到下一期的生產安排。特別地，企業(yè)當期的成本最低并不必然地導致長期成本最低。例如，某企業(yè)各期的市場需求都是0.5，產量只能選擇0或者1，在單位缺貨成本為1而庫存成本為1.2的情況下，追求當期成本最低的決策者將永遠選擇產量為0，兩期的總成本為1；追求長期成本最低的決策者將選擇第一期的產量為1，第二期的產量為0，兩期的總成本為0.6。如果市場需求不是固定不變甚至是隨機的，如果企業(yè)有限的生產能力可以用于多種產品的生產，企業(yè)生產過程的組織將會變得非常復雜，甚至無法用手工求解。文中將探索借助遺傳算法求解近似最優(yōu)解的算法，以推動這一問題的進一步解決。

1 模型描述

企業(yè)生產M種產品，產品類型集合R＝｛1，2，…，r，…，M｝；有N 種固定的生產組合方式，組合方式集合S＝｛1，2，…，s，…，N｝。企業(yè)的生產經營過程是永續(xù)的，為了處理上的方便，限定為K 個周期，生產周期集合T＝｛1，2，…，t，…，K｝。我們還認為，企業(yè)當期生產的產品均可以用于當期銷售。

企業(yè)的生產經營活動存在成本，因生產組織的不同而導致的成本差異主要體現為庫存成本、加班成本和缺貨成本。如果企業(yè)當期及以前生產的產品沒有銷售出去，將占用庫存，第t期、第r種產品的庫存成本表示為Itr；如果當期的總產量超出了企業(yè)的生產能力，企業(yè)將支付加班費，第t期、采用第s種組合方式時的加班費表示為Ets；如果企業(yè)可用于當期銷售的產品量小于市場需求，企業(yè)將損失獲利的機會，產生缺貨成本，第t期、第r種產品的缺貨成本表示為Ltr。

企業(yè)的決策目標是K個周期內的總成本最小。由于市場需求存在波動，企業(yè)的決策是一個動態(tài)的過程?？删唧w描述為：先根據各種產品的庫存、企業(yè)的生產能力、對市場需求的長期預測等確定當期生產產量；等到下一周期再根據前面各期的銷售情況修正對市場需求的長期預測，進而確定下一周期的產量；周而復始，直至K期。每一期的具體決策過程如圖1所示。企業(yè)第J期期初的決策目標及約束條件可用數學符號表示如下：

圖1 求解第J期預計最小總成本的過程

式中：Sts—— 第t期采用第s種組合方式生產；

vtr—— 第t期第r種產品期初的庫存；

ptsr—— 第t期采用第s種生產組合方式所生產的第r種產品的產量；

dtr—— 第t期第r種產品需求量（實際的或預測的）；

αr，βr—— 分別表示第r種產品的單位庫存成本和缺貨成本。

2 算 法

文中提出的問題很難求出最優(yōu)解（或者根本就不可能在事前求出最優(yōu)解），我們給出用遺傳算法[7]求解近似最優(yōu)解的具體實現辦法。

2.1 遺傳基因編碼

研究的問題有K個周期，每個周期有N種可供選擇的組合。如果用二進制編碼，將產生染色體過長的問題；如果采用固定長度編碼，則需要編寫和預測次數一樣多的遺傳算法程序。因此，建議采用變長度染色體整數編碼。采用這種編碼方式，只要隨著時間的推移逐步輸入各期的實際銷量，就可以改變染色體的長度，從而可以在不同的時期用同一個算法程序進行生產安排。每個染色體長度為預測期數加1，最后一位用于存放該染色體的適應度函數值。染色體長度的變化規(guī)則為時間經過1期染色體長度變短1位，例如第1期期初的染色體長度為K＋1位，第5期期初染色體長度則為K－3位。染色體中第i位對應的數s就表示從求解當期算起的第i期應該采用第s種生產組合，如染色體“5321893535650”就表示第1期用第5種生產組合，第2期用第3種生產組合…第12期采用的第5種生產組合，整個染色體表示進行12期生產安排的情況。

2.2 適應度函數的設計和計算

以總成本最小作為最優(yōu)解的判斷標準，總成本由預測期間所有的缺貨成本、庫存成本和加班成本構成。為了使優(yōu)秀個體的適應度取值更大，便于利用輪盤賭的方法選擇個體，把總成本的導數乘上一個足夠大的數作為個體的適應度函數值。在后面的算例中，將適應度函數設為：

2.3 遺傳操作

遺傳操作就是根據各個基因個體對環(huán)境的適應情況（用適應度的值判斷）進行選擇交叉和變異的操作，不斷尋找更優(yōu)解的過程。首先利用輪盤賭的方法選出父代個體，然后把選中的個體進行配對，并對其進行設定的交叉操作。遺傳算法中有多種交叉方法，文中給出的算例采用了交叉概率為0.6的兩點交叉的方式。另外，還采用了單點變異，在選中的變異個體中隨機得到一個位置，再將解空間中產生的一個隨機數賦予該位置。變異的概率一般取0.001～0.1[8]，文中算例的變異概率取為0.05。

2.4 遺傳中止

當迭代次數大于最大代數或連續(xù)多代的改進量小于設定的一個很小值時，算法中止。

3 算例及仿真結果

本算例選用了2種產品、10個固定生產組合，總共進行為期12個月的生產安排，其中前5種為正常生產，后5種為加班生產。各種生產安排組合方式見表1。

表1 固定生產組合的類型

初始情況和相關單位費用見表2。

表2 兩種產品的初始庫存和相關成本

各種產品的歷史銷售量和實際銷售量見表3。

表3 兩種產品各月的歷史銷售量和實際銷售量

在本算例中，通過分析歷史數據，發(fā)現銷售量與時間之間的散點圖呈拋物線型，所以，假定銷售量和時間滿足拋物線型關系，設dtr＝ar（t－t＊r）2＋br，其中，t＊r為拋物線極值點所對應的時點，dtr為第r種產品在第t期實際或預測的銷售量，第r種產品各期需求量的集合為：

根據歷史數據，用矩陣最小二乘法估算參數ar，br，的值。令

則可得

從而得到預測銷售曲線表達式。再考慮外界環(huán)境的變化，如每月銷量可能上漲某個固定值或某個百分比的基礎上，做出本年度的生產預測。最后用遺傳算法求出生產安排的一個滿意解。后面各期再按前面求解思路進行求解。

當設定交叉概率為0.6，變異概率為0.05，種群個體為500個，迭代次數為100次時，用最小二乘法預測，用變長串遺傳算法求得的結果見表4中2～13行，表4中后4行為人工手算結果的代表。限于篇幅，只列出了4個最優(yōu)的手算結果。

表4 用遺傳算法得出的各月生產安排和最小總成本

在第1個月初的生產安排結果為：1，2，4，4，9，9，9，8，9，3，3，5，全年的最小總成本為229240元。在其后的每個月月初，將以前月份的實際銷售量和生產安排輸入程序，對以后的銷售預測和生產安排進行修正。在求解過程中，適應度函數首先會隨著代數的增加而上升，然后趨于穩(wěn)定。5月初適應度值隨代數變化的趨勢如圖2所示（當時計算的總成本為218230）。

圖2 在4月末用遺傳算法求解時適應度值隨代數變化的趨勢圖

需要說明的是，我們是根據預測來安排生產的，而預測是不可能絕對準確的，因此，各月算出的總成本并不是一直下降，而是有上下波動的。程序的最后計算結果為213340。

為了檢驗結果的有效性，我們請某研究生班45位同學用人工的方法計算了本算例的近似最優(yōu)解，得出的最小成本為23萬，大于程序給出的結果。

4 結 語

利用變長串遺傳算法求解固定批量的生產組織問題，可以避開復雜的線性規(guī)劃模型，比較簡單、方便地求出整體最優(yōu)的生產安排方案。如果企業(yè)在初期就能對各期銷售量做出比較準確的預測，那么整個期間的生產安排只用一次遺傳算法就可以得到滿意解。由于很難準確預測實際的銷售量，在決策過程中不得不根據實際銷售情況不斷修正對未來的預期。文中運用了最小二乘法不斷對未來銷售量的預測做了修正，并在此基礎上用變長串遺傳算法動態(tài)地求解了各期的固定批量生產組合的安排方式，達到了較好的效果。按固定批量生產的工業(yè)企業(yè)和按固定數量進貨的商業(yè)企業(yè)都可使用，具有一定的推廣價值。

文中存在兩個不足之處：一是預測方法的選取有待改進。本算例中銷售量與時間的關系不完全滿足拋物線型，預測銷量與實際銷量存在一定的偏差，這就降低了獲得最優(yōu)解的可能性。如果能得到更符合實際的解析式或者更好的預測方法，預測就會更準確，生產安排就可能更優(yōu)；二是受計算機配置的限制，相對于初期的整個解空間，種群個數和迭代次數選擇得還不夠大，選優(yōu)的效果可能會受到影響。如果在企業(yè)的生產實際中使用此方法，在初期可以設定更大的種群個數和迭代次數，會更接近最優(yōu)解。

[1]Sox C R，Muckstadt J A.Multi－item，multi－period production planning with uncertain demand[J].AIIE Transactions，1996，28：891－900.

[2]Sox C R，Muckstadt J A.Optimization－based planning for the stochastic lot－scheduling problem [J].AIIE Transactions，1997，42（3）：349－357.

[3]應保勝，張華，楊少華.多品種批量生產企業(yè)的動態(tài)生產計劃研究[J].中國制造業(yè)信息化，2003，32（12）：85－88.

[4]曹于忠，楊丹.不確定需求情形下確定生產批量的方法[J].重慶大學學報，2003，26（11）：105－108.

[5]劉曉.批量生產計劃模型與優(yōu)化方法[M].北京：科學出版社，2010：63－47.

[6]夏天，徐克林，洪旭東.作業(yè)成本法的經濟生產批量模型[J].工業(yè)工程，2009，12（4）：73－75.

[7]徐小博，蘇筱蔚，胥桂仙，等.基于遺傳算法的匹配問題求解[J].長春工業(yè)大學學報：自然科學版，2003，24（4）：31－33.

[8]王小平，曹立明.遺傳算法：理論、應用與軟件實現[M].西安：西安交通大學出版社，2002：46－47.