黃 劍，劉建勝，夏芳臣

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

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

0 引言

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

1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

式中：n為外協(xié)加工的零件數(shù)量；mi為零件i外協(xié)加工工段數(shù)量；ri、j為零件i的工序j所對(duì)應(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之間的運(yùn)輸成本。

2.1.3 加權(quán)求和

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

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

2.2 約束條件

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

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

2）決策因子約束

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

3 遺傳算法求解

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

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

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

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

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

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

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

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

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

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

4 實(shí)例

某生產(chǎn)企業(yè)有3個(gè)零件需要同時(shí)協(xié)同加工，其相關(guān)信息如表1、表2所示。本實(shí)例是在Visua1 Studio 2010 +SQL server2008環(huán)境下進(jìn)行。 程序開始運(yùn)行后，設(shè)置遺傳參數(shù)：種群規(guī)模為14，最大迭代次數(shù)為100，。進(jìn)行優(yōu)化時(shí)，權(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分別是零件加工時(shí)間的讀取界面和運(yùn)行結(jié)果界面，其中最后獲得了最優(yōu)的加工路線為：0-0-0-1-0-0-1-0。對(duì)應(yīng)的外協(xié)加工資源優(yōu)化配置結(jié)果如表3所示。

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

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

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

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

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

5 結(jié)論

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

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

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

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

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

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

[6] 劉衛(wèi)寧,劉波,孫棣華.面向多任務(wù)的制造云服務(wù)組合[J].計(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é)報(bào),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.