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

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

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

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

遺傳算法在多品種小批量模式MPS中的應(yīng)用

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

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

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

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

1 引言

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

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

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

2 主生產(chǎn)計劃排單模型

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

2.1 能力約束模型

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

能力利用率=生產(chǎn)產(chǎn)品占用的能力/總能力＝

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

在實際生產(chǎn)中，生產(chǎn)產(chǎn)品占用的能力不能大于總能力，

此數(shù)學(xué)模型符合約束理論的思想，能直觀表現(xiàn)出能力的利用率情況。本文研究的目標(biāo)就是使關(guān)鍵工作中心的能力利用率最大化。

2.2 提前期約束模型

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

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

2.3 主生產(chǎn)計劃排單的雙目標(biāo)數(shù)據(jù)模型

綜合以上分析，建立主生產(chǎn)計劃排單的雙目標(biāo)數(shù)學(xué)模型如公式（3）、（4）：

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

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

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

3.1 遺傳算法思想

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

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

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

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

3.2.1 染色體的編碼設(shè)計

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

圖1 遺傳算法邏輯流程

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

3.2.2 種群初始化

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

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

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

3.2.3 適應(yīng)度函數(shù)的確定

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

3.2.4 選擇

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

3.2.5 交叉

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

3.2.6 變異

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

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

3.2.7 終止條件

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

4 算法應(yīng)用結(jié)果分析

利用前面建立的主生產(chǎn)計劃排單模型及GA對模型的優(yōu)化設(shè)計，采用面向?qū)ο蟮木幊陶Z言Java實現(xiàn)了該算法。將企業(yè)生產(chǎn)中的具體數(shù)據(jù)通過上述算法仿真運算，對計算結(jié)果進行分析，證實該算法在一定程度上提高了適應(yīng)度值，即對解決此問題具有一定效果。具體數(shù)據(jù)如下：

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

表1 物料主文件

表2 訂單項目信息

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

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

表4 經(jīng)過GA生成的MPS1）

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

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

5 結(jié)束語

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

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

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

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

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

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

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

[9]王小平，曹立明.遺傳算法理論應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，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]石苓，竇延平.基于生產(chǎn)計劃排單的遺傳算法的優(yōu)化與應(yīng)用[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）

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

主生產(chǎn)計劃；約束理論；準(zhǔn)時制生產(chǎn)；遺傳算法

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.

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

楊美榮（1980—），女，講師，主要研究方向：ERP、J2EE系統(tǒng)架構(gòu)與開發(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