遺傳算法在多品種小批量模式MPS中的應用

楊美榮，崔曼曼，史建鋒，肖玲諾

1.哈爾濱工業(yè)大學 經濟管理學院（威海），山東 威海 264209

2.哈爾濱工業(yè)大學 管理學院，哈爾濱 150001

3.哈爾濱工業(yè)大學 人文與社會科學學院，哈爾濱 150001

遺傳算法在多品種小批量模式MPS中的應用

楊美榮1，崔曼曼2，史建鋒2，肖玲諾3

1.哈爾濱工業(yè)大學 經濟管理學院（威海），山東 威海 264209

2.哈爾濱工業(yè)大學 管理學院，哈爾濱 150001

3.哈爾濱工業(yè)大學 人文與社會科學學院，哈爾濱 150001

1 引言

傳統(tǒng)大規(guī)模生產的優(yōu)勢在于能夠通過規(guī)模經濟降低成本，但是卻不能靈活適應市場需求。隨著市場需求的多樣化和個性化，多品種小批量生產己成為制造業(yè)的主要生產方式之一。這種生產方式能夠靈活地適應市場多樣化的需求，但由于產品種類多、批量小，工藝過程也不相同，產品生產計劃的穩(wěn)定性差，給企業(yè)生產管理帶來諸多困難。在激烈的市場競爭中，如何在保證企業(yè)經濟利益的同時，快速響應客戶個性化需求，提高客戶滿意度是企業(yè)最關心的問題。在多品種小批量生產模式下，企業(yè)大多是根據客戶訂單組織生產的，因此擁有方便、快捷、有效的主生產計劃（Master Production Schedule，MPS）是快速有效解決客戶需求的重要途徑?？蛻粲唵蔚臄盗恳约坝唵我蟮钠贩N數量較多，因此需要營銷部門與生產部門共同對訂單進行評估，決定是否可以接單。MPS根據客戶訂單和企業(yè)生產能力，把經營計劃或生產大綱中的產品系列具體化，使之成為展開物料需求計劃的主要依據，起到了從綜合計劃向具體計劃過渡的承上啟下的作用。

MPS的編制和優(yōu)化問題一直受到學術界重視。從國外研究來看，生產計劃模型大多是線性規(guī)劃模型或者是整數規(guī)劃模型，其中線性規(guī)劃模型使用最多。Chu[1]從整體的綜合生產計劃問題到最基本的產品裝配問題，針對不同層次模型的復雜性，用線性規(guī)劃方法給出了詳細的解決方案；Byrne和Bakir[2]等采用分析/仿真混合的方法求解生產計劃問題，得到很好的效果。主生產計劃理論與排單問題是分不開的，解決這個問題的關鍵在于排單算法。對此，國外已經進行了很多年的研究，發(fā)展出幾十種先進生產排程算法，比較常用的如：專家系統(tǒng)、模擬退火法、神經網絡優(yōu)化等，這些算法各有優(yōu)劣，可用在不同場合。目前新的不同算法仍正在蓬勃發(fā)展中。在系統(tǒng)開發(fā)上，比較有影響力的ERP軟件商有德國的SAP，美國的Oracle和SSA，以及瑞典的IFS等幾家。

國內，許多研究人員對主生產計劃模型建立這一課題也進行了研究。徐福緣等人[3]用線性目標規(guī)劃方法構造了一個多品種小批量生產條件下的企業(yè)年度生產計劃模型，通過設備工時約束，使關鍵設備加工臺時不超過全年提供的臺時；王時龍[4]等人利用知識工程的原理解決了多品種小批量模式下成批成套生產問題。除此以外，越來越多的學者從不同的角度，采用不同的解決方法對主生產計劃算法進行優(yōu)化。于曉義[5]等針對多協(xié)作車間的并行協(xié)同計劃調度問題，提出了基于工序約束的并行協(xié)同進化遺傳算法。劉敏[6]針對遺傳算法求解過程長，易走向局部最小值等特點，提出了自適應退火遺傳算法，解決了車間日作業(yè)計劃的調度問題。但由于多品種、小批量條件下的作業(yè)是一個NPC問題，至今世界上還沒有一個效率高且通用的優(yōu)化算法。國內，MPS系統(tǒng)開發(fā)比較好的主要是用友、金碟、浪潮通軟、神州數碼等幾家大型ERP軟件開發(fā)商。但是由于排產技術瓶頸的存在，中國大多數企業(yè)目前仍然停留在對BOM低層次的完善和對進銷存財務模塊低水平重復開發(fā)上。其中，絕大多數的MPS系統(tǒng)只是編織一個初稿計劃，然后計算能力需求情況，因而它只提供一個作為能力平衡的依據，大多情況下還是要依靠人來調整。

2 主生產計劃排單模型

在理想生產條件下，比如人力、原材料等資源都充足，設備的能力問題就是決定企業(yè)產出的關鍵。根據約束理論（Theory of Constraints，TOC）和準時制生產（Just in Time，JIT）思想[7]可知設備能力是一個約束，而產品提前期是另外一個約束，解決問題的關鍵就是要最大限度地利用這兩個約束保證瓶頸設備得到充分利用，保證產品提前期得到很好的滿足。針對這個問題，本文建立一個以關鍵工作中心能力利用率最大化和提前/拖期罰款[8]最小為目標的數學模型。

2.1 能力約束模型

本文分析能力約束的條件是在理想的生產條件下，即物料、人力等資源充足。MPS制定的一個主要問題是充分合理地利用瓶頸資源，使關鍵工作中心的能力利用率最大。能力利用率的計算如公式（1）：

能力利用率=生產產品占用的能力/總能力＝

m表示涉及到m種關鍵工作中心；n表示企業(yè)需要生產n種規(guī)格的產品；k表示企業(yè)要對n種產品制定k個時段的主生產計劃；Xijh表示i時段h設備上加工j產品的數量；qijh表示i時段h設備上加工j產品所需要占用的額定能力；Ujh表示i時段h設備的額定可用能力。

在實際生產中，生產產品占用的能力不能大于總能力，

此數學模型符合約束理論的思想，能直觀表現出能力的利用率情況。本文研究的目標就是使關鍵工作中心的能力利用率最大化。

2.2 提前期約束模型

MPS制定中的另一個主要問題是確定訂單的投產日期。關于提前期約束模型的建立，可以考慮企業(yè)拖期罰款和提前的成本。如果不能按交貨期交貨就是違約，要按照一定的比例向客戶付違約費用。因此，拖期時間越短，拖期罰款越少，企業(yè)的利潤越高。還要考慮過早完成訂單生產增加的管理成本。本文提出基于JIT的懲罰函數，以拖期罰款和因提前生產而引起的庫存保管費之和最少為目標來建立數學模型。模型中用到的提前期是指產品的生產提前期，生產提前期通常是變動的，提前時間的長短隨著每批加工量大小而變動。懲罰函數計算如公式（2）：

其中Tj=T′j+lj×Xj。n、m、k定義同上，Xj為j產品本次投產的數量，Xij為i時段j產品的生產數量；Tj為第j種產品的提前期，Tj由固定部分（計劃提前期）Tj'和可變部分構成，lj為單位產量增加的提前期；rj為第j種產品的投產日期，dj為第j種產品的合同交貨日期；βj為單位時間（天）拖期懲罰因子；αj為單位時間（天）提前懲罰因子。

2.3 主生產計劃排單的雙目標數據模型

綜合以上分析，建立主生產計劃排單的雙目標數學模型如公式（3）、（4）：

其中，z1表示設備的能力利用率最大，z2表示懲罰金額最小。對兩個公式分析后發(fā)現，z1求最大比率，z2求最小數值，計算求解時很不方便。對模型進行以下轉換：對z1求倒數，z2轉化為求罰款和訂單金額比值，其思想與z2模型的思想一致。轉換后的數學模型如公式（5）、（6）：

Cj為j產品本次投產的訂單金額，y1表示設備能力利用率的倒數，y2表示罰款與訂單金額比值的最小值。

3 基于遺傳算法的MPS模型優(yōu)化設計

3.1 遺傳算法思想

遺傳算法（Genetic Algorithm，GA）首先采用某種編碼方式將解空間映射到編碼空間，每個編碼對應問題的一個解，稱為個體或染色體，再隨機產生一群初始個體，稱為種群，種群中的每個染色體是問題的一個解。染色體的好壞用適應度來衡量。在后續(xù)迭代中，按照適者生存原理，根據適應度大小挑選染色體，并借助各種遺傳算子對染色體進行交叉和變異，交叉或變異運算后生成下一代染色體，稱為后代。根據適應度的大小從上一代和后代中選擇一定數量的染色體，作為下一代群體，再繼續(xù)進化。經過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或次優(yōu)解。

GA包括三個基本操作[9-10]：選擇、交叉和變異。選擇操作實現對群體中的染色體的優(yōu)勝劣汰，適應度高的個體被遺傳到下一代群體中的概率大，反之概率小。常用方法有：輪盤賭法、排序法、隨機聯賽選擇法、最佳個體保留法；交叉運算是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體，目前常用的配對策略是隨機配對。交叉算子的設計包括兩方面的內容：一是如何確定交叉點的位置，二是如何進行部分基因的交換；常用的交叉算法有：單點交叉、雙點交叉、均勻交叉、算術交叉。變異運算指將個體編碼串中的某些基因值用其他基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算決定了遺傳算法的局部搜索能力。交叉運算和變異運算相互配合共同完成對搜索空間的全局搜索和局部搜索，常用的變異算法有：基本位變異、均勻變異。

遺傳算法（GA）的步驟如圖1所示。

3.2 基于GA的MPS模型的優(yōu)化設計

3.2.1 染色體的編碼設計

GA的優(yōu)化過程不能直接作用在問題空間的參數，必須把它們轉換成遺傳空間中由基因按一定結構組成的染色體，這一轉換操作稱為編碼，編碼的選擇是影響算法性能與效率的重要因素。常用的遺傳編碼方式有二進制編碼、實數編碼、字符編碼[11]等。

圖1 遺傳算法邏輯流程

顯然這樣的一條染色體就是問題的一個解；而且這種實數編碼方法無需解碼，計算結果可直接作為主生產計劃的方案。

3.2.2 種群初始化

首先對一個染色體的基因串，使用Random（0，Xj）（j= 1，2，…，n）方法隨機生成一組基因串，即某個時段生產的各種產品的數量（在0和Xj之間的一個數值），如Xij，然后計算（Xj－Xij），再利用Random（0，Xj－Xij）隨機生成染色體的下一組基因串。用此種方法生成一個染色體的基因串。值得注意的是，最后一個時段基因串的產生方式：

由于每個個體的基因串的產生是隨機的，個體的多樣性可得到保證。用上述方法產生的個體能夠自動滿足約束條件，大大減少了產生初始可行解的計算量。種群中所有個體的基因串都用此種方式產生，直到產生規(guī)定群體數目。

本文研究的問題的種群數目Num的選取與訂單的個數及計劃期的時段數有關，Num的取值大小會影響搜索的收斂速度。當下達的訂單個數較多時，Num取值應較大；否則，Num取值較小。根據多次實驗結果分析，當訂單小于8時，Num取200；否則，Num取400。

3.2.3 適應度函數的確定

適應度函數是適應度與問題參數之間的函數關系。本文研究的目標就是使f（x）=y1+wy2達到最小，其中，w為目標y2在總目標中所占權重，其值根據企業(yè)的喜好偏重而定。在本文分析中，取w=0.6。把f（x）轉化為最大值形式后作為算法中的適應度函數，即G(x)=C-f(x)。其中C為事先給定的足夠大的常數。分析可知y1≤1，y2＜1，所以可取C=100。

3.2.4 選擇

本文選用了這樣一種方法進行選擇：首先將每代中最優(yōu)的一個染色體直接復制到下一代，然后對其他染色體采用輪盤賭方式按其適應度進行選擇，如此重復，直到滿足種群個體數。這種選擇算法可保證迄今為止所得到的最優(yōu)個體不被淘汰，它是GA收斂的一個重要保證條件。而且遵循優(yōu)勝劣汰的規(guī)律，適應度大的染色體被選中的概率大。

3.2.5 交叉

交叉率的選擇決定了交叉操作的頻率，頻率越高，可以越快地收斂到最有希望的最優(yōu)解區(qū)域，因此一般選取較大的交叉率，但太高的頻率也可能導致過早收斂，基本GA中交叉率一般取0.4～0.9。根據多次實驗結果分析，交叉率取0.8。

3.2.6 變異

根據個體的變異率，對經過交叉操作的群體中的個體進行變異操作。這里采用在染色體中隨機選擇父代個體矩陣的兩行進行互換，產生新的個體矩陣。這種操作方式使得除訂單的交貨期順序有變化之外其他約束條件沒有被破壞。與交叉算法一樣，變異算法在隨機選擇配對染色體時選用除第一個個體以外的其他個體，這樣可保證迄今為止所得到的最優(yōu)個體不受變異操作的影響保留至下一代，避免種群退化。

變異率的選取受種群大小、染色體長度等因素影響，在基本GA中，變異率通常選取很小的值，一般取0.001～0.1。若選取高的變異率，雖然增加樣本模式的多樣性，但可能會引起不穩(wěn)定。種群大小及染色體長度越大，變異率選取越小。根據多次實驗結果分析，變異率取0.1。

3.2.7 終止條件

終止條件也是GA中的一個重要方面，因其直接關系到算法的效率。一般情況下若給定滿足的條件，則直接用其作為終止條件或給定遺傳代數作為終止條件。本文采用直接給定其遺傳代數作為其終止條件。

4 算法應用結果分析

利用前面建立的主生產計劃排單模型及GA對模型的優(yōu)化設計，采用面向對象的編程語言Java實現了該算法。將企業(yè)生產中的具體數據通過上述算法仿真運算，對計算結果進行分析，證實該算法在一定程度上提高了適應度值，即對解決此問題具有一定效果。具體數據如下：

假設企業(yè)要對5份訂單的10個訂單項目進行主生產計劃安排。物料主文件如表1所示，訂單項目信息如表2所示，按交貨時間排序后的訂單項目信息如表3所示。主生產計劃的計劃展望期從2008年7月15日開始，至2008年8月11日結束；時段以周為單位，即時段的時間跨度為7天，共有4個時段。

表1 物料主文件

表2 訂單項目信息

表3 按時間排序后的訂單項目信息

GA中交叉率、變異率、群體規(guī)模、遺傳代數等各參數的選取對算法收斂的速度和結果都有影響。本文對GA各參數經過多次運算分析，交叉率取0.8，變異率取0.1，遺傳代數取100，取群體規(guī)模為400。用GA對MPS模型進行優(yōu)化求解，求得結果如表4；僅按交貨期隨機生成的MPS如表5。

表4 經過GA生成的MPS1）

表5 僅按交貨期隨機生成的MPS

對表4與表5結果進行分析：用GA進行優(yōu)化計算得出的主生產計劃方案適應度為G（x）=98.91，目標函數的結果為f（x）=1.09；僅利用交貨期的順序隨機生成的主生產計劃得出的適應度為G（x）=98.77，目標函數是f（x）=1.23。由此可知GA優(yōu)化結果更好。把表4及表5結果分別帶入數學模型進行驗證，發(fā)現表4罰款金額較?。?54元＜1 596元），關鍵工作中心利用率較高（0.93＞0.86），證實優(yōu)化結果基本符合生產的實際要求。因此，用GA解決此問題是正確有效的。

5 結束語

本文詳細介紹了MPS雙目標排單模型的建立，然后提出了MPS排單模型的GA優(yōu)化設計與實現的具體方法和步驟，最后給出了排單模型GA優(yōu)化的實例分析，證明了GA的可行性。該算法在某些時候可能會收斂于局部最優(yōu)解，此時增加遺傳代數可以在一定程度上避免這個問題。

[1]Chu S C K.A mathematical programming approach towards optimized master production scheduling[J].International Journal of Production Economics，1995，38：269-279.

[2]Byrne M D，Bakir M A.Production planning using a hybrid simulation analytical approach[J].International Journal of Production Economics，1999，59：305-311.

[3]徐福緣，凌佩雯，范晉鷹.一個小批量多品種的生產計劃模型[J].工業(yè)工程，2000，4（3）：44-46.

[4]王時龍，易力力，任亨斌，等.多品種小批量成批成套生產滾動計劃的生成方法[J].重慶大學學報，2009，32（9）：1024-1042.

[5]于曉義，孫樹棟，褚崴.基于并行協(xié)同進化遺傳算法的多協(xié)作車間計劃調度[J].計算機集成制造系統(tǒng)，2008，14（5）：991-1000.

[6]劉敏，嚴雋薇.基于自適應退火遺傳算法的車間日作業(yè)計劃調度方法[J].計算機學報，2007，30（7）：1164-1172.

[7]李艷，吉衛(wèi)喜.基于投產數量的實數編碼遺傳算法在雙目標主生產計劃模型中的應用[J].機械制造，2006，44（8）：62-64.

[8]Stevenson W J.Production operations management[M].張群，張杰，譯.北京：機械工業(yè)出版社，2000：391-413.

[9]王小平，曹立明.遺傳算法理論應用與軟件實現[M].西安：西安交通大學出版社，2002：5-20.

[10]Hajela P，Lee E，Cho H.Genetic algorithms in topologic design of grillage structure[J].Computer-Aided Civil and Infrastructure Engineering，1998，13：13-22.

[11]石苓，竇延平.基于生產計劃排單的遺傳算法的優(yōu)化與應用[J].計算機仿真，2005，22（4）：86-89.

YANG Meirong1,CUI Manman2,SHI Jianfeng2,XIAO Lingnuo3

1.School of Economics and Management at Weihai,Harbin Institute of Technology,Weihai,Shandong 264209,China
2.School of Management,Harbin Institute of Technology,Harbin 150001,China
3.School of Humanities and Social Science,Harbin Institute of Technology,Harbin 150001,China

According to Just-in-Time production and Theory of Constraints,centering on two restrictions of producing ability of key work center and production lead time,determining the maximum utilization of key work center and the least earliness/tardiness fine as the two goals of MPS model,this paper presents a double-goal MPS model based on multi-variety and small-batch enterprise. It uses GA to optimize the MPS model.Through analyzing the results of the enterprise data,GA has been proved to be effective.

master production schedule;Theory of Constraints（TOC）;Just-in-Time（JIT）;Genetic Algorithms（GA）

結合準時制生產和約束理論，以“關鍵設備產能”和“產品提前期”兩大約束為重心，確定以關鍵工作中心利用率最高和提前/拖期罰款最少作為MPS模型的兩個目標，提出了一種多品種、小批量生產模式下企業(yè)MPS的雙目標排單模型的建立思路和方法；應用遺傳算法對模型進行優(yōu)化計算，通過對企業(yè)實例數據的運行結果分析，驗證了方案的有效性。

主生產計劃；約束理論；準時制生產；遺傳算法

A

TP311

10.3778/j.issn.1002-8331.1110-0351

YANG Meirong,CUI Manman,SHI Jianfeng,et al.Applications of Genetic Algorithm in production planning of multi-categories and small batch mode.Computer Engineering and Applications,2013,49（13）：266-270.

山東省自然科學基金（No.2009ZRA10043）。

楊美榮（1980—），女，講師，主要研究方向：ERP、J2EE系統(tǒng)架構與開發(fā)。E-mail：ymr324@163.com

2011-10-18

2012-01-06

1002-8331（2013）13-0266-05

CNKI出版日期：2012-03-21http://www.cnki.net/kcms/detail/11.2127.TP.20120321.1734.012.html