黃 劍，劉建勝，夏芳臣

HUANG Jian，LIU Jian-sheng，XIA Fang-chen

(南昌大學(xué) 機(jī)電工程學(xué)院，南昌 330031)

0 引言

云制造是一種利用網(wǎng)絡(luò)和制造服務(wù)平臺，按用戶需求組織網(wǎng)上制造資源（制造云），為用戶提供各類按需制造服務(wù)的一種網(wǎng)絡(luò)化制造新模式[1]。不同的地域的制造資源進(jìn)行優(yōu)化組合，實現(xiàn)短時間、低成本以及高質(zhì)量的零件的加工，正是云制造資源優(yōu)化配置目標(biāo)。云制造資源的優(yōu)化配置是實現(xiàn)云制造技術(shù)的關(guān)鍵之一[2]。目前，已有采用啟發(fā)式算法研究云制造資源優(yōu)化配置[2～7]。馬雪芬等提出了兩種可行的制造資源優(yōu)化配置，以遺傳算法求解制造資源優(yōu)化配置模型[3]；王正成等提出了利用蟻群算法求解網(wǎng)絡(luò)化制造跨企業(yè)資源服務(wù)鏈的構(gòu)建問題[4]；尹勝等提出了多任務(wù)和多目標(biāo)的外協(xié)加工資源優(yōu)化配置模型，采用了遺傳算法求解了該配置模型，并以實例驗證[5]。以上已經(jīng)建立了單個和多個零件的加工優(yōu)化配置模型，但未對多個零件的工序選擇的候選資源存在關(guān)聯(lián)進(jìn)行研究，這樣會形成是單個零件配置的累加。針對存在的問題，本文對多個零件的工序選擇候選資源存在關(guān)聯(lián)情況下，提出以時間(T)和成本(C)為多目標(biāo)的多零件云制造資源優(yōu)化配置模型，并利用遺傳算法(Genetic A1gorithm，GA)對該模型進(jìn)行了求解。

1 問題描述

當(dāng)企業(yè)同時存在多個零件需要同時加工，由于自身的生產(chǎn)能力或技術(shù)水平無法滿足要求，需要求助于外部制造資源來完成零件幾個或者多個工序加工。在云制造環(huán)境下，包括M個協(xié)同加工企業(yè)(包含本企業(yè)在內(nèi))，需要同時加工n個零件，每個零件j包含p道協(xié)同工序。

根據(jù)協(xié)同加工企業(yè)和零件工序情況，多個零件工序會出現(xiàn)選擇同一候選制造資源組，因此，多個零件選擇資源會存在制約關(guān)系。如圖1所示，在同一工序?qū)又?，不同零件工序選擇的候選資源組會出現(xiàn)不同或者相同。當(dāng)工序選擇的候選資源組不同時，不同零件工序選擇的候選資源是相互獨立，多個零件工序與單個零件工序選擇候選加工資源是一樣；當(dāng)工序選擇的候選資源組相同時，會出現(xiàn)加工等待的情況，即一個零件的一道工序加工完成后，才能加工另一個零件。這樣，完成零件加工的時間包含加工時間和運輸時間，還需要包含等待加工時間。

圖1 多個零件工序選擇候選資源存在關(guān)聯(lián)示意圖

云制造服務(wù)平臺提供給用戶的資源一定是有限的范圍下，而不是無限數(shù)目。如圖2所示，多個零件進(jìn)行優(yōu)化配置時，若同一工序?qū)庸ば蛲瑫r選擇資源，則出現(xiàn)等待加工時間的情況可以分成兩大類：1)n＞m時，一定要考慮等待加工時間；2)n≤m時，有兩個及以上的工序選擇同一資源，需要考慮等待加工時間。

圖2 工序與相同候選資源組的數(shù)量關(guān)系

2 數(shù)學(xué)模型

2.1 目標(biāo)函數(shù)

云制造資源的優(yōu)化配置時，需要考慮包括時間、成本、質(zhì)量、企業(yè)信譽及可靠性等要素。從市場需求的角度出發(fā)，本文以時間（T）和成本（C）為優(yōu)化目標(biāo)，并建立如下目標(biāo)函數(shù)。

2.1.1 時間目標(biāo)函數(shù)

當(dāng)多個零件進(jìn)行外協(xié)加工時，出現(xiàn)同一工序?qū)拥墓ば蜻x擇相同的制造資源組的情況下，需要考慮加工零件的等待時間。等待加工時間計算公式：

式中：tp、tq為零件p、q前m?1道工序的總加工時間(未含有等待加工時間)；tp,i,u、tq,i,v

零件i的外協(xié)工序j在候選資源u處所耗費的總時間為：

因此，其時間目標(biāo)函數(shù)：

式中：n為外協(xié)加工的零件數(shù)量；mi為零件i外協(xié)加工工段數(shù)量；ri、j為零件i的工序j所對應(yīng)的候選加工資源數(shù)數(shù)量；ji,j,k為決策因子，若零件i的工序j選擇候選資源k，則決策變量為1，否則為0。

2.1.2 加工成本目標(biāo)函數(shù)

式中： 為零件i的外協(xié)工序j在候選資源u處的加工成本；為零件i外協(xié)工序j在候選資源u與下一道工序i+1在候選資源v之間的運輸成本。

2.1.3 加權(quán)求和

在云制造服務(wù)平臺下，不同用戶對產(chǎn)品的最長交貨期、總成本等方面要求的側(cè)重點不同。同時，目標(biāo)函數(shù)之間既相互關(guān)聯(lián)，又相互制約。通過采用最通常的權(quán)重法，將多目標(biāo)轉(zhuǎn)化為單目標(biāo)。

式中：w1、w2為時間、成本的權(quán)重系數(shù)，w1+w2=1；Tmax、Cmax為用戶要求的最長交貨期、可以支付的最高成本。

2.2 約束條件

面向多零件的云制造資源優(yōu)化配置模型主要存在時間約束、成本約束和決策因子約束。

1）目標(biāo)值約束

2）決策因子約束

云制造環(huán)境下，一道工序下的相同零件只能分配給一個候選資源加工，即：

3 遺傳算法求解

遺傳算法是一種全局性的概率搜索算法，具有對函數(shù)的性態(tài)無要求、并行性很高和搜索效率高,以及全局最優(yōu)解求解能力較好等獨特的性能[3]。但是，采用遺傳算法對面向多零件的云制造資源優(yōu)化配置模型求解，需要解決以下問題。

1）編碼。 在遺傳算法中，設(shè)計合適的編碼方法，對于問題的表達(dá)至關(guān)重要。整數(shù)編碼對于組合優(yōu)化問題最為有效[8]。因此，本文采用整數(shù)編碼求解。

2）最小化問題的適應(yīng)度函數(shù)。 標(biāo)定是將目標(biāo)函數(shù)映射成適值度函數(shù)，根據(jù)不同問題，采取不同的標(biāo)定方法，線性標(biāo)定中的參數(shù)隨著迭代次數(shù)的增加而變化時就得到了動態(tài)線性標(biāo)定。動態(tài)線性標(biāo)定是最常用的一種適值標(biāo)定方法，計算公式是：

圖3 選擇壓力的調(diào)節(jié)

3)群體規(guī)模。一般來說，遺傳算法中種群規(guī)模越大越好，但是種群規(guī)模的增大也將導(dǎo)致運算時間的增大。假設(shè)種群規(guī)模為NP，染色體長度為1，通常情況下，1.5l ≤NP＜2l/2。

4)選擇策略。Ho11and提出的輪盤賭選擇是最知名的選擇方式[9]。根據(jù)每個染色體的適應(yīng)值的比例來確定該個體的選擇概率或生存概率。若個體為i，適應(yīng)值為 Fi，種群規(guī)模為NP，則該個體的選擇概率為：

5)交叉概率(pc)和變異概率(pm)。 由于交叉和變異概率跟隨問題的不同，可能有不的取值。對整數(shù)編碼而言，交叉概率 pc=0.90～1.00，變異概率 pm=0.005～0.05，Pm＜0.05,否則，遺傳算法的進(jìn)化過程近似于隨機(jī)搜索行為。

6)遺傳算子操作。 單切點交叉是由Ho11and提出的最基礎(chǔ)的一種交叉方式，但由于存在信息量小、末尾基因總是被交換等缺陷。在實際中大量采用兩點交叉算子，本文采用雙切點交叉算子。

7)修復(fù)。交叉操作和變異操作后，分別需要根據(jù)公式(7)～(9)修復(fù)個體滿足約束條件。

8)終止準(zhǔn)則。最大迭代次數(shù)作為終止準(zhǔn)則。

4 實例

某生產(chǎn)企業(yè)有3個零件需要同時協(xié)同加工，其相關(guān)信息如表1、表2所示。本實例是在Visua1 Studio 2010 +SQL server2008環(huán)境下進(jìn)行。 程序開始運行后，設(shè)置遺傳參數(shù)：種群規(guī)模為14，最大迭代次數(shù)為100，。進(jìn)行優(yōu)化時，權(quán)重系數(shù)分別為w1=0.6，w2=0.4，目標(biāo)值的約束為：TAmax=90、TBmax=275、TCmax=140、CAmax=850、CBmax=800、CCmax=1270。圖4、圖5分別是零件加工時間的讀取界面和運行結(jié)果界面，其中最后獲得了最優(yōu)的加工路線為：0-0-0-1-0-0-1-0。對應(yīng)的外協(xié)加工資源優(yōu)化配置結(jié)果如表3所示。

圖4 零件數(shù)據(jù)讀取界面

圖5 程序結(jié)果界面

表1 候選資源的加工時間T、加工成本C數(shù)據(jù)

表2 候選資源之間的運輸時間 t'(h)、運輸成本 c'(元)

表3 最終優(yōu)化配置結(jié)果

5 結(jié)論

本文探討了多個零件的工序選擇相同的候選資源時，云制造資源的優(yōu)化配置問題，建立了基于時間(T)和成本(C)為目標(biāo)云制造多零件制造優(yōu)化配置數(shù)學(xué)模型。通過本文設(shè)計的遺傳算法求解模型，并采用算例驗證了模型及算法的有效性。但云制造平臺環(huán)境下，用戶要求的目標(biāo)的優(yōu)化配置不僅局限于時間和成本，因此，還需要進(jìn)一步研究在云制造環(huán)境下的優(yōu)化目標(biāo)體系，以及多目標(biāo)的優(yōu)化配置模型及優(yōu)化方法。

[1] 李伯虎,張霖,王時龍,等.云制造—面向服務(wù)的網(wǎng)絡(luò)化制造新模式[J].計算機(jī)集成制造系統(tǒng),2010,16(01)∶1-7+16.

[2] 王時龍,宋文艷,康玲,等.云制造環(huán)境下的制造資源優(yōu)化配置研究[J].計算機(jī)集成制造系統(tǒng),2012,18(7)∶1396-1405.

[3] 馬雪芬,戴旭東,孫樹棟.面向網(wǎng)絡(luò)化制造的制造資源優(yōu)化配置研究[J].計算機(jī)集成制造系統(tǒng),2004,10(5)∶179-193.

[4] 王正成,潘曉弘,潘旭偉.基于蟻群算法的網(wǎng)絡(luò)化制造資源服務(wù)鏈構(gòu)建[J].計算機(jī)集成制造系統(tǒng),2010,16(01)∶174-181.

[5] 尹勝,尹超,劉飛,等.多任務(wù)外協(xié)加工資源優(yōu)化配置模型及遺傳算法求解[J].重慶大學(xué)學(xué)報,2010,33(03)∶49-55.

[6] 劉衛(wèi)寧,劉波,孫棣華.面向多任務(wù)的制造云服務(wù)組合[J].計算機(jī)集成制造系統(tǒng),2013,19(01)∶199-209.

[7] 韋韞,李東波,童一飛.面向服務(wù)的網(wǎng)絡(luò)化協(xié)同制造資源多目標(biāo)重組優(yōu)化調(diào)度[J].農(nóng)業(yè)機(jī)械學(xué)報,2012,43(03)∶193-199.

[8] 玄光男,于歆杰.遺傳算法與工程優(yōu)化[M].北京∶清華大學(xué)出版社,2004.

[9] Ho11and J.Adapatation in Natura1 and Artificia1 Systems[A].Kos,Greece∶ECCOMAS,2007∶50(55)∶94-101.