多品種變批量拉鏈生產(chǎn)計劃優(yōu)化方法研究

關(guān)鍵詞：生產(chǎn)計劃； 多品種變批量； 遺傳算法

中圖分類號：TP39 文獻(xiàn)標(biāo)識碼：A文章編號：2095-2163（2013）05-0081-04

0引言

隨著時代的發(fā)展，變批量多品種生產(chǎn)模式應(yīng)運而生，因其有著靈活應(yīng)對市場變化、滿足客戶多樣需求，提高企業(yè)市場競爭力等諸多優(yōu)點[1]。已有眾多學(xué)者對多品種變批量進(jìn)行了深入的研究并提出各種生產(chǎn)優(yōu)化模型[2]。憑此契機，本文也研究了一種多品種變批量情況下的生產(chǎn)計劃優(yōu)化方法。

多品種變批量生產(chǎn)是一種根據(jù)待制造產(chǎn)品的品種和批量變化，而快速調(diào)整生產(chǎn)計劃的生產(chǎn)模式。該模式面向生產(chǎn)任務(wù)和生產(chǎn)資源，以快速重排、重復(fù)利用的方式快速調(diào)整生產(chǎn)計劃，使得生產(chǎn)功能、生產(chǎn)能力和生產(chǎn)過程得到快速改變，以實現(xiàn)產(chǎn)品多品種、變批量的柔性生產(chǎn)[3]。變批量生產(chǎn)強調(diào)生產(chǎn)過程中的產(chǎn)品的不確定性，包括產(chǎn)品品種的不確定性，產(chǎn)品數(shù)量的不確定性。變批量多品種生產(chǎn)中的生產(chǎn)資源還應(yīng)該具備柔性。由于拉鏈生產(chǎn)的多品種變批量特性，在實際生產(chǎn)中都是將變批量的產(chǎn)品整合為多個子批的產(chǎn)品而統(tǒng)一安排生產(chǎn)，在滿足每個子批的交貨量和交貨期的情況下，采用生產(chǎn)計劃優(yōu)化方法，實現(xiàn)最短生產(chǎn)周期[4]。

由于生產(chǎn)計劃問題通常存在著很多約束，使其成為非常難解的NP完全性復(fù)雜的優(yōu)化問題，如果采用常規(guī)的精確算法，將難以在較短時間內(nèi)找到問題的最優(yōu)解，于是引入遺傳算法。目前，遺傳算法已成為生產(chǎn)計劃優(yōu)化等NP難問題的研究實現(xiàn)熱點和實用解決方法。本文提出了一種新的生產(chǎn)計劃問題的多種群遺傳算法，該算法通過隨機產(chǎn)生兩個初始種群，各自進(jìn)化，并彼此遷移，每個種群都產(chǎn)生局部最優(yōu)解，相互比較獲得全局最優(yōu)解。

1問題描述

多品種變批量的拉鏈制造企業(yè)在計劃期收到一批訂單，由于品種與批量的不確定性，整理后分為N子批產(chǎn)品，通過生產(chǎn)資源設(shè)備、模架、模具的相應(yīng)組合以實現(xiàn)產(chǎn)品的生產(chǎn)。由于設(shè)備出模次數(shù)，模具的出模個數(shù)和模架上安放模具個數(shù)等約束，設(shè)備生產(chǎn)每種產(chǎn)品的生產(chǎn)能力可能各不相同。由于設(shè)備和產(chǎn)品等約束，產(chǎn)品在各個設(shè)備的生產(chǎn)計劃會導(dǎo)致完成所有批次產(chǎn)品的生產(chǎn)周期不一樣。

2模型建立

2.1確定多品種產(chǎn)品分成子批的生產(chǎn)序列

首先根據(jù)接收到的訂單計劃將其按產(chǎn)品類型、批量大小和交貨期分為子批，具體步驟如下：

（1）按產(chǎn)品類型分成不同種類產(chǎn)品批次。

（2）再按每種產(chǎn)品的交貨期進(jìn)行分批。每個滿足相近交貨期生產(chǎn)的產(chǎn)品將合成為同一批次。

（3）若某種批量的交貨量并未超過最大批量限制，則將其分為一批。否則將最大批量分為一批，超出部分按照（3）再重新分批。

這樣共分成了N個子批的產(chǎn)品，再對這N個子批生成生產(chǎn)次序：

（1）確定每個子批包含的所有產(chǎn)品的交貨期，并以其中的最小交貨期作為整個子批的交貨期。

（2）將所有子批按照交貨期從小到大進(jìn)行依序生產(chǎn)。

（3）交貨期相同的子批，交貨量小的和不可延遲的則要優(yōu)先生產(chǎn)。

（4）產(chǎn)生最終生產(chǎn)序列。

2.2確定子批序列的生產(chǎn)計劃模型

本模型的主要任務(wù)是在綜合各種生產(chǎn)資源生產(chǎn)能力的情況下，進(jìn)行生產(chǎn)計劃優(yōu)化。在完成這些子批產(chǎn)品生產(chǎn)的基礎(chǔ)上，生成各個設(shè)備完成這批訂單的生產(chǎn)計劃。第5期陶小晶：多品種變批量拉鏈生產(chǎn)計劃優(yōu)化方法研究智能計算機與應(yīng)用第3卷

在拉片壓鑄車間，有設(shè)備、模架和模具。每臺設(shè)備安放一臺模架，由于模架與模具的組合，每臺模架上安裝的模具數(shù)量不定，設(shè)備上安放的模架通常為限定。在某段時間內(nèi)，接到一批訂單，每個訂單需要的產(chǎn)品多種多樣，需要的產(chǎn)品批量也有大有小，產(chǎn)品的交貨期也有分段。假設(shè)將該批訂單整合，然后分成N個子批進(jìn)行生產(chǎn)，該模型要在滿足全部訂單的各種產(chǎn)品交貨量和交貨期的前提下，根據(jù)生產(chǎn)資源的生產(chǎn)能力，生成將所有設(shè)備分配給各種產(chǎn)品以完成這批訂單的生產(chǎn)計劃。該計劃將使得完成該批訂單的生產(chǎn)周期最小。

此處，假設(shè)每臺設(shè)備每天工作8小時；這N個子批產(chǎn)品在每臺設(shè)備上按各子批優(yōu)先順序生產(chǎn)；模架上更換模具時間忽略；拉片生產(chǎn)設(shè)備有限，模架和模具數(shù)量足夠；模架安放不同的模具時個數(shù)不定；每臺設(shè)備在同一時刻只能生產(chǎn)一種拉片產(chǎn)品；每種產(chǎn)品在模具上生產(chǎn)之前的準(zhǔn)備工作都不考慮；過程不考慮突發(fā)事件，所有資源正常工作；每種產(chǎn)品的交貨量與交貨期已知；按照整理過后的批次順序進(jìn)行排產(chǎn)。

綜合上述各假設(shè)條件，可得子批序列的生產(chǎn)計劃模型如下：

模型中，MSmin為最小生產(chǎn)周期；MSj為設(shè)備j的生產(chǎn)時間；DNi為第i批產(chǎn)品的交貨量；DTi為第i批產(chǎn)品的交貨期；Ej為安放在設(shè)備j上的模架的出模次數(shù)；bij為子批i的產(chǎn)品在設(shè)備j的模架上可安放的模具數(shù)量；ci為出模子批i的產(chǎn)品的模具每次出模個數(shù)；aij為標(biāo)志是否將設(shè)備j分配給子批i進(jìn)行生產(chǎn)；tij為將設(shè)備j分配給子批i的生產(chǎn)時間。

3優(yōu)化算法

由于拉片壓鑄為生產(chǎn)計劃問題，，需要進(jìn)行生產(chǎn)方案的全局尋優(yōu)。本文采用多種群遺傳算法進(jìn)行生產(chǎn)計劃優(yōu)化。

3.1問題的編碼

本文采用自然數(shù)編碼的方式，以各子批要生產(chǎn)的產(chǎn)品為對象進(jìn)行編碼，并使用一個n*m矩陣來表示該問題的可行解?，F(xiàn)在給出n個子批產(chǎn)品在m臺設(shè)備上的加工序列矩陣如下：

其中，aij表示將設(shè)備j分配給子批i的生產(chǎn)時間。矩陣的第i行向量[ai1，ai2，…，aim]依次表示子批i的產(chǎn)品在各個設(shè)備上的生產(chǎn)時間。矩陣的第j列向量表示將設(shè)備j分配給各個子批的產(chǎn)品次序和生產(chǎn)時間。在初始化產(chǎn)生的染色體中，將子批i在設(shè)備j上的生產(chǎn)時間代入染色體的基因aij中，這樣依次代入，則初始化的染色體為[a11，a12，…，a1m，a21，…，aij，…，anm]。通過自左向右遍歷染色體所產(chǎn)生的生產(chǎn)結(jié)果都是可行的，用這類方法產(chǎn)生的初始解也都為可行解。

3.2適應(yīng)度函數(shù)

通常，取目標(biāo)函數(shù)直接作為適應(yīng)度函數(shù)，在這里取生產(chǎn)完成一批訂單的生產(chǎn)周期MSmax=max{MSj|j=1，…，m}的倒數(shù)作為適應(yīng)度函數(shù)，由此來計算每個染色體的適應(yīng)度值。

令MSkmax表示第k個染色體的生產(chǎn)周期，則該染色體的適應(yīng)度函數(shù)即表示為：

3.3遺傳操作

針對前述的編碼方式，采用如下遺傳操作[5]。

3.3.1選擇

本文采用精英保留策略和期望值策略結(jié)合使用的選擇方法。精英保留策略指的是將當(dāng)前種群中適應(yīng)度值最高的個體不進(jìn)行交叉變異而直接復(fù)制到下一代種群中。采用精英保留策略能夠使進(jìn)化過程的每一代種群內(nèi)的最優(yōu)解不致為交換和變異操作所破壞，從而增加獲得局部最優(yōu)解的概率。

采用精英保留策略和期望值策略結(jié)合使用的選擇方法是：在種群開始進(jìn)化時，將種群內(nèi)的最優(yōu)解直接復(fù)制到下一代種群中，再考慮剩余染色體個體的期望值，通過期望值操作將其他染色體遺傳到下一代種群中。期望值操作的步驟是：

（1）按照適應(yīng)度的值計算期望值fi，計算公式為：

fi=1n∑ni=1fi（3）

（2）計算種群中的每一個體在下一代生存的期望值Ei，計算公式為：

Ei=fifi（4）

（3）將Ei四舍五入取整得Ei，Ei即為選中個體i的個數(shù)。

如果Ei=0，則個體i被淘汰。

3.3.2交叉

本文采用的交叉法是在染色體上依據(jù)問題性質(zhì)定位多個分割點，再隨機選取兩個相鄰分割點，定義這兩點之間的區(qū)域為一匹配區(qū)域，并使用位置交換操作交換兩個父串的匹配區(qū)域 。具體的交叉操作如下：

（1）任意選擇兩個父代染色體P1和P2。

（2）根據(jù)這兩個染色體的構(gòu)成n*m，將這兩個染色體按m分割成n+1個分割點。隨機選擇一個a（a

（3）將L1中的基因依次插入到P2染色體的空位中，將L2中的基因依次插入到P1染色體的空位中，分別生成子代染色體S1和S2，未被選中的基因在子代染色體中的相對位置是保持不變的。

對于4*4（4批次產(chǎn)品，4臺設(shè)備）的生產(chǎn)計劃問題，有p1和p2兩個生產(chǎn)計劃方案：

上面染色體每一個“.”處為一個分割點，隨機選擇a=1，則第2個分割點（第4*1+1=5個基因）為起始，第3個分割點（第4*2=8個基因）為結(jié)束的基因串就分別是L1=[0 3 2 2]，L2=[5 0 2 2]。將L1放入染色體P2中原來L2在的空位處，將L2放入染色體P1中原來L1在的空位處實現(xiàn)交叉操作，保持其余各基因串順序不變。得到子代染色體：

3.3.3變異

本文采用的變異操作的具體步驟是：

（1）染色體長度n*m，隨機選擇一個a（a

（2）以變異概率p使g1的基因值加1，g2的基因值減2。

（3）將g1和g2插回Q中兩個基因的原來位置，成為新的染色體R。

（4）先檢驗第a+1批次產(chǎn)品的生產(chǎn)可行性，即新染色體R的可行性。若可行，再比較新個體與父代個體的適配值。如果新個體適配值較小，則用其取代父代個體；否則，保持父代個體不變。

選擇a=1，范圍第4*1+1個基因開始，4*2個基因結(jié)束，基因串是[0 3 2 2]，隨機選擇p1的第6個基因和第8個基因為變異基因g2，g1。g1的基本值加1變?yōu)?，g2的基因值減2變?yōu)?，將g1和g2插回原來的染色體，構(gòu)成新染色體R為：

3.4利用多種群遺傳算法優(yōu)化生產(chǎn)計劃問題

多種群遺傳算法的設(shè)計思想是存在不同初始值的幾個種群，每個種群都有著對應(yīng)的進(jìn)化參數(shù)，采用不同的選擇策略和交叉變異算子使種群發(fā)生進(jìn)化，產(chǎn)生每個種群的局部最優(yōu)個體，進(jìn)而得出全局的最優(yōu)個體[6]。

采用多種群遺傳算法求解生產(chǎn)計劃模型的具體步驟如下：

（1）初始化種群。使用自然數(shù)編碼方法，隨機產(chǎn)生染色體組成兩個種群。

（2）初始化種群進(jìn)化參數(shù)。為每個種群選擇交叉概率、變異概率和種群間精英遷移的概率。

（3）為每個種群確定選擇操作。對種群1選用的選擇操作為精英保留策略和期望值策略結(jié)合方法，對種群2選用的選擇操作為輪盤賭法。

（4）各個種群按照各自設(shè)定的交叉概率和變異概率進(jìn)行交叉和變異操作。

（5）對產(chǎn)生的新一代種群，各個種群按照設(shè)定的遷移概率交換種群間的個體。交換后更新種群，形成下一代種群。

（6）檢驗是否滿足終止條件，如果滿足則產(chǎn)生各個種群的局部最優(yōu)個體，如果不滿足則返回（4）繼續(xù)進(jìn)化。

（7）對兩個種群產(chǎn)生的局部最優(yōu)個體進(jìn)行比較，得出全局最優(yōu)個體，輸出全局最優(yōu)個體。

4仿真實驗與分析

例1：在一段時間內(nèi)，有4個訂單計劃生產(chǎn)。這4個訂單需要的拉片產(chǎn)品及其交貨量交貨期如表1；生產(chǎn)設(shè)備M={1，2，3}，設(shè)備的出模次數(shù)分別是{80，70，60}，各個設(shè)備每天生產(chǎn)8小時。產(chǎn)品i（i=1，2，3，4）的模具安放在設(shè)備j（j=1，2，3）上的個數(shù)如表2所示，所有產(chǎn)品分批后結(jié)果則表3所示。

種群1初始個體數(shù)量30，交叉概率0.9；變異概率0.1，遷移概率0.05，最優(yōu)個體保留個數(shù)2；最大遺傳代數(shù)50；種群2初始個體數(shù)量30，交叉概率0.85，變異概率0.15，遷移概率0.05，最優(yōu)個體保留個數(shù)2，最大遺傳代數(shù)50。

仿真結(jié)果分析：算法收斂曲線如圖1所示，最優(yōu)生產(chǎn)計劃如表4所示，甘特圖如圖2所示。比較局部染色體后，得到全局最優(yōu)染色體[6 0 6 0 16 10 0 14 16 27 4 2 ]。 最小生產(chǎn)周期為34小時。

Tab.4 Production planing子批號設(shè)備1（小時）設(shè)備2（小時）設(shè)備3（小時）子批1606子批201610子批301416子批42742由以上仿真結(jié)果可以看出：種群1和種群2都能夠保持種群多樣性，且都逐步達(dá)到最優(yōu)解，該算法具有良好的收斂性和有效性。文獻(xiàn)[7]對模型的優(yōu)化結(jié)果為35小時，而根據(jù)本文的優(yōu)化方法，優(yōu)化結(jié)果為34小時，且有多個排產(chǎn)結(jié)果。

5結(jié)束語

本文應(yīng)用多種群遺傳算法對拉鏈生產(chǎn)中的拉片壓鑄的生產(chǎn)計劃優(yōu)化問題進(jìn)行了研究。采用表示生產(chǎn)時間的自然數(shù)編碼，選用適合本問題的選擇、交叉和變異操作，以完成生產(chǎn)的最小生產(chǎn)周期為評價指標(biāo)，并建立完整的生產(chǎn)計劃模型的優(yōu)化算法。仿真結(jié)果表明該算法實現(xiàn)了生產(chǎn)計劃方案的全局優(yōu)化。

參考文獻(xiàn)：

[1]任瑞榮. 多品種變批量生產(chǎn)質(zhì)量控制關(guān)鍵技術(shù)的研究與應(yīng)用[D]. 上海：東華大學(xué)， 2010.

[2]李宏霞，彭威，史海波.裝配車間的多品種變批量的生產(chǎn)調(diào)度優(yōu)化模型[J]. 機械設(shè)計與制造， 2006（6）：94-96.

[3]安進(jìn). 車間生產(chǎn)批量優(yōu)化調(diào)度研究[D]. 南京：南京航空航天大學(xué)，2005.

[4]CAVALICRI S ， GAIARDCLLI P. Hybrid genetic algorithms for a multiple-objective scheduling problem [J] . Journal of Intelligent Manufacturing ，1998 （9） ：361 - 367.

[5]任慶生，葉中，曾進(jìn)，等. 對常用選擇算子的分析[J] . 上海交通大學(xué)學(xué)報，2000 ，34 （4） ：564 - 566.

[6]蔡良偉，張基宏，李霞. 作業(yè)車間調(diào)度問題的多種群遺傳算法[J]. 電子學(xué)報， 2005， 33（ 6） ： 991- 994.

[7]張畢西，謝祥添.非流水型生產(chǎn)調(diào)度問題的研究[J].機械制造，2007，45（4）：60-62.

（上接80頁）

（2）對硬件配置要求較低，服務(wù)器采用的配置相當(dāng)自由；

（3）系統(tǒng)平滑切換，不會造成使用不便；

（4）系統(tǒng)效率較高。因為數(shù)據(jù)管理和服務(wù)器故障糾錯由相對獨立的兩個子系統(tǒng)聯(lián)合完成，而雙機心跳線使用的又是冗余網(wǎng)絡(luò)，所以不需消耗CPU和寬帶資源。

同時，雙機與磁盤互聯(lián)的缺點為：

（1）單點錯。即使系統(tǒng)中某一個節(jié)點出錯，也會導(dǎo)致系統(tǒng)全部宕機；

（2）當(dāng)磁盤陣列出現(xiàn)邏輯故障或物理故障時，還會導(dǎo)致儲存數(shù)據(jù)全部丟失。

5結(jié)束語

在全球信息高速路建設(shè)漸趨完成的今天，大到高新科技前沿技術(shù)，小到平民百姓日常生活，信息服務(wù)無處不在，而保護(hù)這些信息甚至已成為維護(hù)社會穩(wěn)定的必要手段。雙機熱備份技術(shù)的出現(xiàn)解決了這一問題，在保護(hù)重要數(shù)據(jù)的同時，又不致影響到用戶正常使用。在網(wǎng)絡(luò)技術(shù)的激烈競爭中，人力組配是很寶貴的重要資源，雙機熱備份即節(jié)省了人力資源，因而具有重要的實用推廣價值。

參考文獻(xiàn)：

[1]施維力.淺談服務(wù)器的雙機熱備份技術(shù)[J].廣播電視信息，2009（12）： 60-61.

[2]王崇霞.數(shù)據(jù)庫雙機熱備份系統(tǒng)解決方案[J]. 微機發(fā)展，2003（S2）：79-80，85.

[3]史文路.雙機熱備份系統(tǒng)的研究與設(shè)計[D].南京：南京工業(yè)大學(xué)，2006.

[4] ALLCOCK B，F(xiàn)OREST I， NEFEDOVA V. High-Performance remote access to climate simulation data：A challenge Problem for data grid technologies[A].The conf of High-Performance Networking and Computing，Denver SC2001[C].USA：[s.n.]，2001：283-297.

[5]李利軍.星載雙機熱備份計算機系統(tǒng)設(shè)計[D]. 西安：西安電子科技大學(xué)，2010.

[6]曹陽.RAID技術(shù)實現(xiàn)及發(fā)展[J].電腦學(xué)習(xí)，2006（4）：43-44，60.

[7]徐敏，陸達(dá)，趙洪志，等.廉價冗余盤陣列（RAID）發(fā)展綜述[J]. 計算機工程與應(yīng)用，1999（6）：27-29.