螞蟻算法在面向零件的網(wǎng)絡(luò)化制造中的應(yīng)用研究

摘要:為了有效地實(shí)現(xiàn)網(wǎng)絡(luò)制造環(huán)境下資源共享與優(yōu)化配置，提出了協(xié)同制造鏈的概念，指出協(xié)同制造鏈?zhǔn)且环N圍繞零件制造過程的網(wǎng)絡(luò)化制造動(dòng)態(tài)聯(lián)盟。在此基礎(chǔ)上給出了協(xié)同制造鏈的定義和形式化描述，并以某航空發(fā)動(dòng)機(jī)關(guān)鍵零件為具體應(yīng)用研究對(duì)象，詳細(xì)分析了協(xié)同制造鏈的構(gòu)建和演化過程;同時(shí)，對(duì)協(xié)同制造鏈構(gòu)建和演化過程中的關(guān)鍵問題——協(xié)同制造鏈排序進(jìn)行了重點(diǎn)研究，建立了該問題的數(shù)學(xué)描述模型，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于螞蟻算法的協(xié)同制造鏈排序策略。最后通過實(shí)例驗(yàn)證了該策略的有效性。

關(guān)鍵詞:網(wǎng)絡(luò)化制造; 協(xié)同制造鏈; 螞蟻算法

中圖分類號(hào):TP391文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001－3695(2008)02－0386－04

當(dāng)前，以Internet為代表的網(wǎng)絡(luò)技術(shù)正在使制造業(yè)發(fā)生深刻的變化。企業(yè)動(dòng)態(tài)聯(lián)盟[1]正向著網(wǎng)絡(luò)化制造動(dòng)態(tài)聯(lián)盟方向發(fā)展。按照網(wǎng)絡(luò)化制造[2，3]模式運(yùn)作的經(jīng)濟(jì)實(shí)體稱為網(wǎng)絡(luò)化制造動(dòng)態(tài)聯(lián)盟，它是網(wǎng)絡(luò)化制造提出的一個(gè)重要概念，是網(wǎng)絡(luò)化制造的基本組織形式。本文將不同制造企業(yè)在基于網(wǎng)絡(luò)的協(xié)作制造環(huán)境下圍繞零件制造過程所形成的網(wǎng)絡(luò)化制造動(dòng)態(tài)聯(lián)盟稱為協(xié)同制造鏈，它是實(shí)施零件分散網(wǎng)絡(luò)化制造的一種有效資源組織形式。協(xié)同制造鏈圍繞零件的制造過程，利用計(jì)算機(jī)網(wǎng)絡(luò)將異地制造資源迅速整合在一起，以降低生產(chǎn)成本#65380;縮短生產(chǎn)周期#65380;提高產(chǎn)品質(zhì)量。

圍繞零件的制造過程，協(xié)同制造鏈的各成員之間存在一種時(shí)序關(guān)系。因此在協(xié)同制造鏈的構(gòu)建和演化過程中，如何在制造工藝約束下，正確#65380;合理地安排協(xié)同制造鏈中分布在不同地理位置上各成員企業(yè)之間的先后順序是一個(gè)極其關(guān)鍵的問題，直接關(guān)系到協(xié)同制造鏈構(gòu)建和運(yùn)行的成敗。本文在分析協(xié)同制造鏈構(gòu)建和演化過程的基礎(chǔ)上，對(duì)該問題進(jìn)行了重點(diǎn)研究，提出了基于螞蟻算法[4]的協(xié)同制造鏈排序策略。

1協(xié)同制造鏈定義及其構(gòu)建和演化過程

1.1協(xié)同制造鏈定義

定義1協(xié)同制造鏈?zhǔn)菄@零件制造過程，將其劃分為若干協(xié)同制造任務(wù)并外包給網(wǎng)絡(luò)中各企業(yè)所提供的制造服務(wù)完成，各制造服務(wù)之間按一定順序組合而成的一個(gè)鏈(制造服務(wù)是企業(yè)核心制造能力面向服務(wù)的封裝。在協(xié)同制造鏈構(gòu)建與演化過程中，如果某任務(wù)無(wú)須外包，則將企業(yè)自身也視為一項(xiàng)制造服務(wù))。

在協(xié)同制造鏈中，每一個(gè)節(jié)點(diǎn)都是一個(gè)協(xié)同制造任務(wù)—制造服務(wù)對(duì)。節(jié)點(diǎn)之間的先后順序關(guān)系由零件的結(jié)構(gòu)特點(diǎn)#65380;工藝要求#65380;制造成本#65380;加工質(zhì)量以及交貨期等確定。可形式化描述如下:

1.2協(xié)同制造鏈構(gòu)建和演化過程

協(xié)同制造鏈的構(gòu)建和演化過程可以使用UML順序圖來(lái)描述，如圖1所示。由圖可知，協(xié)同制造鏈的構(gòu)建和演化過程主要涉及到協(xié)同制造鏈發(fā)起企業(yè)#65380;協(xié)作企業(yè)#65380;網(wǎng)絡(luò)化敏捷制造平臺(tái)三個(gè)對(duì)象。該過程可劃分為制造任務(wù)分解和描述#65380;制造服務(wù)發(fā)現(xiàn)和匹配#65380;協(xié)同制造鏈生成和優(yōu)化#65380;合同簽訂和項(xiàng)目執(zhí)行#65380;協(xié)同制造鏈解體五個(gè)階段。本節(jié)將以某型號(hào)航空發(fā)動(dòng)機(jī)關(guān)鍵零件為具體應(yīng)用研究對(duì)象，對(duì)其各階段進(jìn)行詳細(xì)分析。

1)制造任務(wù)分解和描述工藝路線是連接產(chǎn)品設(shè)計(jì)和產(chǎn)品制造的橋梁，其主要任務(wù)是為被加工零件選擇合理的加工方法和加工順序。工藝路線分析是制造任務(wù)分解和描述的基礎(chǔ)。與企業(yè)內(nèi)部的工藝路線分析不同，在協(xié)同制造鏈構(gòu)建過程中，企業(yè)選擇加工方法時(shí)不僅要考慮本企業(yè)的制造資源，而且還應(yīng)基于廣泛的網(wǎng)絡(luò)化資源選擇加工方法。完成加工方法選擇后，企業(yè)通常還需要以精度區(qū)段作為排序標(biāo)準(zhǔn)，按“先粗后精#65380;先主后次#65380;先面后孔”等規(guī)則確定各加工方法之間的優(yōu)先關(guān)系。此外，協(xié)同制造鏈發(fā)起企業(yè)還應(yīng)根據(jù)零件的制造要求(包括數(shù)量#65380;精度#65380;質(zhì)量#65380;成本#65380;交貨時(shí)間等)確定每道加工任務(wù)的工期和成本，評(píng)估本企業(yè)制造資源能否滿足要求，判斷哪些加工任務(wù)需要外協(xié)，并將其確定為外協(xié)加工任務(wù)(即協(xié)同制造任務(wù))。評(píng)估的結(jié)果將作為制造服務(wù)發(fā)現(xiàn)的依據(jù)。完成上述工作后，協(xié)同制造鏈發(fā)起企業(yè)將獲得一個(gè)面向協(xié)同制造的零件工藝規(guī)劃(collaborative－oriented process plan，COPP)。圖2為某型號(hào)航空發(fā)動(dòng)機(jī)關(guān)鍵零件的COPP。

COPP有別于企業(yè)內(nèi)部的傳統(tǒng)工藝規(guī)程。傳統(tǒng)工藝規(guī)程中，工序間具有嚴(yán)格的順序關(guān)系并且完成了每道工序的設(shè)備#65380;工裝以及刀具的選擇。COPP只給出了協(xié)同制造任務(wù)劃分及其相關(guān)加工要求(主要包括加工基準(zhǔn)#65380;工序尺寸#65380;加工余量以及時(shí)間定額等)，并沒有與具體的資源相關(guān)聯(lián);各任務(wù)間僅進(jìn)行了初步排序，尚未為每一個(gè)任務(wù)建立嚴(yán)格的順序關(guān)系。圖2中AND節(jié)點(diǎn)之間的加工任務(wù)表示其加工先后順序關(guān)系尚未確定，而非指加工時(shí)間上的并行。為便于描述，本文將其稱之為并行制造任務(wù)集合(對(duì)于單個(gè)任務(wù)，本文將其看做是一個(gè)僅包含一個(gè)協(xié)同制造任務(wù)的并行制造任務(wù)集)。

2)制造服務(wù)發(fā)現(xiàn)和匹配它是一個(gè)將協(xié)同制造任務(wù)的能力需求特征與制造服務(wù)的制造能力特征進(jìn)行匹配，以制造能力為基礎(chǔ)搜索出所有滿足任務(wù)加工要求的制造服務(wù)的過程。針對(duì)零件制造過程中本企業(yè)無(wú)法滿足的制造能力，協(xié)同制造鏈發(fā)起企業(yè)從位于網(wǎng)絡(luò)化敏捷制造平臺(tái)上的制造服務(wù)注冊(cè)中心搜索能夠滿足協(xié)同制造任務(wù)加工能力要求的制造服務(wù)，并將協(xié)同制造任務(wù)外包給相應(yīng)的制造服務(wù)提供商進(jìn)行委托加工。對(duì)每一個(gè)協(xié)同制造任務(wù)，制造服務(wù)注冊(cè)中心可能會(huì)返回多個(gè)滿足能力需求的制造服務(wù)，本文稱之為候選制造服務(wù)集合。完成制造服務(wù)發(fā)現(xiàn)與匹配后，協(xié)同制造鏈發(fā)起企業(yè)將獲得一個(gè)依賴于制造服務(wù)的零件工藝規(guī)劃(service－dependent process plan，SDPP)。圖3為某型號(hào)航空發(fā)動(dòng)機(jī)關(guān)鍵零件的SDPP。

3)協(xié)同制造鏈生成和優(yōu)化它包括兩個(gè)步驟，即制造服務(wù)優(yōu)化選擇和協(xié)同制造鏈排序。制造服務(wù)發(fā)現(xiàn)和匹配僅僅以制造能力為惟一指標(biāo)對(duì)制造服務(wù)進(jìn)行衡量，獲得各協(xié)同制造任務(wù)的候選制造服務(wù)集合。為了進(jìn)一步優(yōu)選出最佳制造服務(wù)，還需要依據(jù)加工質(zhì)量#65380;交貨及時(shí)性#65380;加工成本#65380;服務(wù)質(zhì)量等指標(biāo)對(duì)候選制造服務(wù)集合中的制造服務(wù)進(jìn)行綜合評(píng)價(jià)。完成綜合評(píng)價(jià)后，協(xié)同制造鏈發(fā)起企業(yè)將獲得一個(gè)優(yōu)選后的SDPP。在優(yōu)選后的SDPP中，OR節(jié)點(diǎn)已被消除，協(xié)同制造任務(wù)與制造服務(wù)一一對(duì)應(yīng)，即為一個(gè)協(xié)同制造任務(wù)—制造服務(wù)對(duì)。圖4為某型號(hào)航空發(fā)動(dòng)機(jī)關(guān)鍵零件優(yōu)選后的SDPP。

在協(xié)同制造鏈構(gòu)建過程中，協(xié)同制造鏈發(fā)起企業(yè)還需進(jìn)一步對(duì)優(yōu)選后的SDPP進(jìn)行排序，消除SDPP中的AND節(jié)點(diǎn)，最終生成協(xié)同制造鏈。圖5為最終生成的某型號(hào)航空發(fā)動(dòng)機(jī)關(guān)鍵零件的協(xié)同制造鏈。

4)合同簽訂與項(xiàng)目執(zhí)行協(xié)同制造鏈構(gòu)建成功后，協(xié)同制造鏈發(fā)起企業(yè)與鏈中的相關(guān)制造服務(wù)提供商簽訂商務(wù)合同，協(xié)同制造鏈正式進(jìn)入運(yùn)行階段。在協(xié)同制造鏈運(yùn)行階段，采用基于網(wǎng)絡(luò)的協(xié)作項(xiàng)目管理形式對(duì)零件的整個(gè)制造過程進(jìn)行管理。

5)協(xié)同制造鏈解體當(dāng)零件制造任務(wù)完成后，各相關(guān)企業(yè)完成資金結(jié)算，協(xié)同制造鏈即自行解體。

2協(xié)同制造鏈排序問題分析和建模

工藝排序描述了零件從毛坯到成品的全過程，是零件工藝規(guī)劃的核心內(nèi)容之一。由上述協(xié)同制造鏈構(gòu)建與演化過程可知，COPP是一個(gè)由并行制造任務(wù)集構(gòu)成的具有偏序關(guān)系[5]的集合。并行制造任務(wù)集內(nèi)的協(xié)同制造任務(wù)尚未確定先后加工順序，因此需要對(duì)COPP中各并行制造任務(wù)集內(nèi)的所有協(xié)同制造任務(wù)進(jìn)行排序，從而確定零件的最終加工順序，完成協(xié)同制造鏈的構(gòu)建。經(jīng)過基于能力約束的制造服務(wù)發(fā)現(xiàn)和匹配及制造服務(wù)優(yōu)化選擇后，COPP中每一個(gè)協(xié)同制造任務(wù)均對(duì)應(yīng)一個(gè)制造服務(wù)。此時(shí)，協(xié)同制造鏈排序問題就相應(yīng)轉(zhuǎn)換為對(duì)各制造服務(wù)的排序問題。

傳統(tǒng)工藝規(guī)程編制中的排序問題約束復(fù)雜，必須考慮諸如加工方法#65380;加工對(duì)象#65380;零件形狀#65380;精度要求等因素，經(jīng)驗(yàn)性和個(gè)性很強(qiáng)，難以建立數(shù)學(xué)模型求解。與傳統(tǒng)的工藝排序不同，協(xié)同制造鏈的構(gòu)建是建立在零件工藝分析基礎(chǔ)之上的。在其從COPP到SDPP的演化過程中，已經(jīng)充分考慮了制造工藝#65380;加工成本以及加工時(shí)間等問題，故安排各并行制造任務(wù)集內(nèi)部協(xié)同制造任務(wù)的加工順序時(shí)無(wú)須再考慮上述因素。因此，協(xié)同制造鏈排序問題將僅從加工路線角度出發(fā)，為零件異地協(xié)同制造過程規(guī)劃出一條最優(yōu)的加工路徑，使零件以最短的運(yùn)輸時(shí)間#65380;最低的運(yùn)輸成本在各制造服務(wù)提供商之間流轉(zhuǎn)，從而高效地完成零件制造過程。下面給出協(xié)同制造鏈排序問題的形式化描述。

3基于螞蟻算法的協(xié)同制造鏈排序

3.1螞蟻算法基本原理

Deneubourg等人[6]的研究表明，螞蟻具有找到蟻巢和食物之間最短路徑的能力。這種能力是靠其留在所經(jīng)過路徑上的一種揮發(fā)性分泌物pheromone(稱為信息素，該物質(zhì)隨著時(shí)間的推移會(huì)逐漸揮發(fā))來(lái)實(shí)現(xiàn)的。螞蟻在一條路徑上前進(jìn)時(shí)，會(huì)留下信息素，后來(lái)的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上信息素的濃度成正比。對(duì)于一條路徑，選擇它的螞蟻越多，則該路徑上留下的信息素濃度就越高，而濃度高的信息素又會(huì)吸引更多的螞蟻，從而形成一種正反饋。通過這種正反饋，螞蟻?zhàn)罱K可以尋找到食物的最佳(短)路徑。來(lái)源于螞蟻覓食行為的螞蟻算法由于其新穎的全局優(yōu)化能力，已應(yīng)用在多方面的研究中。Colorni等人將其應(yīng)用于典型的NP－h(huán)ard組合優(yōu)化問題上(如二次分配#65380;車間作業(yè)進(jìn)度問題等)取得了較好的成績(jī);Dorigo采用螞蟻算法解決了傳統(tǒng)的TSP(traveling salesman problem)[7]，取得了優(yōu)于Hopfield神經(jīng)網(wǎng)絡(luò)的性能。此外，螞蟻算法還被廣泛應(yīng)用于電信網(wǎng)以及IP網(wǎng)中尋找路由，均獲得了滿意的結(jié)果。

3.2基于螞蟻算法的協(xié)同制造鏈排序

由前文對(duì)協(xié)同制造鏈排序問題的分析可知，該問題可簡(jiǎn)單表述為按V0V1V2…Vh(huán)V0偏序關(guān)系，尋找一條訪問協(xié)同制造鏈中所有集合Vi(i=0，1，…，h)中每個(gè)制造服務(wù)提供商且僅訪問一次的最短長(zhǎng)度閉環(huán)路徑。下面描述螞蟻算法求解該問題的主要過程。

首先設(shè)置螞蟻訪問路徑的初始信息素濃度。在每次搜索開始時(shí)，設(shè)有q只螞蟻被安放在隨機(jī)選擇的制造服務(wù)提供商上，螞蟻各自開始自己的搜索過程。例如第g只螞蟻被放入到Vi中的制造服務(wù)提供商v(i)k上，

在具體搜索過程中，螞蟻g首先沿著距離短且信息素濃度較高的路徑訪問Vi中的下一個(gè)制造服務(wù)提供商。如果螞蟻g已訪問完Vi中全部制造服務(wù)提供商，則仍基于距離和信息素濃度去訪問下一個(gè)集合Vi+1中的制造服務(wù)提供商(如果i=h，則訪問V0中的v(0)1)，直至將協(xié)同制造鏈中的制造服務(wù)提供商全都訪問遍。當(dāng)所有螞蟻完成訪問后，即進(jìn)行全局信息素濃度的更新，每只螞蟻根據(jù)它們已完成的周游路徑距離更新它們走過路徑的信息素濃度。信息素濃度的更新完成后，檢查所有螞蟻的訪問結(jié)果，記錄由螞蟻找到的最短路徑。重復(fù)上述過程直到所有螞蟻都走同一路線，或達(dá)到用戶定義的最大周游次數(shù)。

在具體求解過程中，每只螞蟻的行為符合下列規(guī)律:

a)根據(jù)路徑上的信息素濃度，以相應(yīng)的概率來(lái)選擇下一個(gè)制造服務(wù)提供商。

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

通過采用協(xié)同制造鏈的形式可以實(shí)現(xiàn)跨車間乃至跨企業(yè)的資源組合和優(yōu)化，能夠充分挖掘企業(yè)制造資源潛力，解決我國(guó)制造業(yè)缺乏協(xié)同機(jī)制，制造資源相對(duì)缺乏#65380;分散以及利用率低的問題。協(xié)同制造鏈排序是協(xié)同制造鏈構(gòu)建和演化過程中的一個(gè)關(guān)鍵問題，其本質(zhì)上是一個(gè)復(fù)雜的組合優(yōu)化問題。針對(duì)該問題，本文提出了一個(gè)基于螞蟻算法的協(xié)同制造鏈排序策略。螞蟻算法吸收了螞蟻的行為特性，通過其內(nèi)在的搜索機(jī)制，在協(xié)同制造鏈排序問題求解中顯示了良好的效果。

參考文獻(xiàn):

[1]胡開順，姚小群，葉邦彥，等.動(dòng)態(tài)聯(lián)盟供應(yīng)鏈的結(jié)構(gòu)模型及其規(guī)劃設(shè)計(jì)[J].中國(guó)制造業(yè)信息化，2003，32(1):73－75.

[2]顧寄南.網(wǎng)絡(luò)化制造技術(shù)[M].北京:化學(xué)工業(yè)出版社，2004:23－27.

[3]王萃寒，馮徑.網(wǎng)絡(luò)化制造的技術(shù)體系研究[J].中國(guó)制造業(yè)信息化，2004，33(5):80－83.

[4]COLORNI A， DORIGO M， MANIEZZO V. Distributed optimization by ant colonies[C]//Proc of the 1st Europ Conf on Artificial Life. Paris: Elsevier Publishing， 1991:134－142.

[5]耿素云.集合論與圖論[M].北京:北京大學(xué)出版社，1998.

[6]DENEUBOURG J L， GOSS S. Collective patterns and decision ma－king[J]. Ethology， Ecology and Evolution， 1989，1(4):295－311.

[7]吳斌.群體智能中的研究及其在知識(shí)發(fā)現(xiàn)中應(yīng)用[D].北京:中國(guó)科學(xué)院計(jì)算技術(shù)研究所，2002.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”