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

孫改玲， 龔 利

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

0 引 言

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

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

1 模型描述

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

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

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

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

式中：Sts—— 第t期采用第s種組合方式生產(chǎn)；

vtr—— 第t期第r種產(chǎn)品期初的庫存；

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

dtr—— 第t期第r種產(chǎn)品需求量（實際的或預(yù)測的）；

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

2 算 法

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

2.1 遺傳基因編碼

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

2.2 適應(yīng)度函數(shù)的設(shè)計和計算

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

2.3 遺傳操作

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

2.4 遺傳中止

當(dāng)?shù)螖?shù)大于最大代數(shù)或連續(xù)多代的改進量小于設(shè)定的一個很小值時，算法中止。

3 算例及仿真結(jié)果

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

表1 固定生產(chǎn)組合的類型

初始情況和相關(guān)單位費用見表2。

表2 兩種產(chǎn)品的初始庫存和相關(guān)成本

各種產(chǎn)品的歷史銷售量和實際銷售量見表3。

表3 兩種產(chǎn)品各月的歷史銷售量和實際銷售量

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

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

則可得

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

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

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

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

圖2 在4月末用遺傳算法求解時適應(yīng)度值隨代數(shù)變化的趨勢圖

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

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

4 結(jié) 語

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

文中存在兩個不足之處：一是預(yù)測方法的選取有待改進。本算例中銷售量與時間的關(guān)系不完全滿足拋物線型，預(yù)測銷量與實際銷量存在一定的偏差，這就降低了獲得最優(yōu)解的可能性。如果能得到更符合實際的解析式或者更好的預(yù)測方法，預(yù)測就會更準(zhǔn)確，生產(chǎn)安排就可能更優(yōu)；二是受計算機配置的限制，相對于初期的整個解空間，種群個數(shù)和迭代次數(shù)選擇得還不夠大，選優(yōu)的效果可能會受到影響。如果在企業(yè)的生產(chǎn)實際中使用此方法，在初期可以設(shè)定更大的種群個數(shù)和迭代次數(shù)，會更接近最優(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īng)保勝，張華，楊少華.多品種批量生產(chǎn)企業(yè)的動態(tài)生產(chǎn)計劃研究[J].中國制造業(yè)信息化，2003，32（12）：85－88.

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

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

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

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

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