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

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

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

0引言

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

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

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

1問(wèn)題描述

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

2模型建立

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3優(yōu)化算法

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

3.1問(wèn)題的編碼

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

其中，aij表示將設(shè)備j分配給子批i的生產(chǎn)時(shí)間。矩陣的第i行向量[ai1，ai2，…，aim]依次表示子批i的產(chǎn)品在各個(gè)設(shè)備上的生產(chǎn)時(shí)間。矩陣的第j列向量表示將設(shè)備j分配給各個(gè)子批的產(chǎn)品次序和生產(chǎn)時(shí)間。在初始化產(chǎn)生的染色體中，將子批i在設(shè)備j上的生產(chǎn)時(shí)間代入染色體的基因aij中，這樣依次代入，則初始化的染色體為[a11，a12，…，a1m，a21，…，aij，…，anm]。通過(guò)自左向右遍歷染色體所產(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ù)，由此來(lái)計(jì)算每個(gè)染色體的適應(yīng)度值。

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

3.3遺傳操作

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

3.3.1選擇

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

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

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

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

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

Ei=fifi（4）

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

如果Ei=0，則個(gè)體i被淘汰。

3.3.2交叉

本文采用的交叉法是在染色體上依據(jù)問(wèn)題性質(zhì)定位多個(gè)分割點(diǎn)，再隨機(jī)選取兩個(gè)相鄰分割點(diǎn)，定義這兩點(diǎn)之間的區(qū)域?yàn)橐黄ヅ鋮^(qū)域，并使用位置交換操作交換兩個(gè)父串的匹配區(qū)域 。具體的交叉操作如下：

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

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

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

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

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

3.3.3變異

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

（1）染色體長(zhǎng)度n*m，隨機(jī)選擇一個(gè)a（a

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4仿真實(shí)驗(yàn)與分析

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

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

[3]安進(jìn). 車間生產(chǎn)批量?jī)?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)，等. 對(duì)常用選擇算子的分析[J] . 上海交通大學(xué)學(xué)報(bào)，2000 ，34 （4） ：564 - 566.

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

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

（上接80頁(yè)）

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

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

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

同時(shí)，雙機(jī)與磁盤互聯(lián)的缺點(diǎn)為：

（1）單點(diǎn)錯(cuò)。即使系統(tǒng)中某一個(gè)節(jié)點(diǎn)出錯(cuò)，也會(huì)導(dǎo)致系統(tǒng)全部宕機(jī)；

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

[3]史文路.雙機(jī)熱備份系統(tǒng)的研究與設(shè)計(jì)[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]李利軍.星載雙機(jī)熱備份計(jì)算機(jī)系統(tǒng)設(shè)計(jì)[D]. 西安：西安電子科技大學(xué)，2010.

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

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