螞蟻算法在面向零件的網絡化制造中的應用研究

摘要:為了有效地實現網絡制造環境下資源共享與優化配置，提出了協同制造鏈的概念，指出協同制造鏈是一種圍繞零件制造過程的網絡化制造動態聯盟。在此基礎上給出了協同制造鏈的定義和形式化描述，并以某航空發動機關鍵零件為具體應用研究對象，詳細分析了協同制造鏈的構建和演化過程;同時，對協同制造鏈構建和演化過程中的關鍵問題——協同制造鏈排序進行了重點研究，建立了該問題的數學描述模型，設計并實現了一個基于螞蟻算法的協同制造鏈排序策略。最后通過實例驗證了該策略的有效性。

關鍵詞:網絡化制造; 協同制造鏈; 螞蟻算法

中圖分類號:TP391文獻標志碼:A

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

當前，以Internet為代表的網絡技術正在使制造業發生深刻的變化。企業動態聯盟[1]正向著網絡化制造動態聯盟方向發展。按照網絡化制造[2，3]模式運作的經濟實體稱為網絡化制造動態聯盟，它是網絡化制造提出的一個重要概念，是網絡化制造的基本組織形式。本文將不同制造企業在基于網絡的協作制造環境下圍繞零件制造過程所形成的網絡化制造動態聯盟稱為協同制造鏈，它是實施零件分散網絡化制造的一種有效資源組織形式。協同制造鏈圍繞零件的制造過程，利用計算機網絡將異地制造資源迅速整合在一起，以降低生產成本#65380;縮短生產周期#65380;提高產品質量。

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

1協同制造鏈定義及其構建和演化過程

1.1協同制造鏈定義

定義1協同制造鏈是圍繞零件制造過程，將其劃分為若干協同制造任務并外包給網絡中各企業所提供的制造服務完成，各制造服務之間按一定順序組合而成的一個鏈(制造服務是企業核心制造能力面向服務的封裝。在協同制造鏈構建與演化過程中，如果某任務無須外包，則將企業自身也視為一項制造服務)。

在協同制造鏈中，每一個節點都是一個協同制造任務—制造服務對。節點之間的先后順序關系由零件的結構特點#65380;工藝要求#65380;制造成本#65380;加工質量以及交貨期等確定。可形式化描述如下:

1.2協同制造鏈構建和演化過程

協同制造鏈的構建和演化過程可以使用UML順序圖來描述，如圖1所示。由圖可知，協同制造鏈的構建和演化過程主要涉及到協同制造鏈發起企業#65380;協作企業#65380;網絡化敏捷制造平臺三個對象。該過程可劃分為制造任務分解和描述#65380;制造服務發現和匹配#65380;協同制造鏈生成和優化#65380;合同簽訂和項目執行#65380;協同制造鏈解體五個階段。本節將以某型號航空發動機關鍵零件為具體應用研究對象，對其各階段進行詳細分析。

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

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

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

3)協同制造鏈生成和優化它包括兩個步驟，即制造服務優化選擇和協同制造鏈排序。制造服務發現和匹配僅僅以制造能力為惟一指標對制造服務進行衡量，獲得各協同制造任務的候選制造服務集合。為了進一步優選出最佳制造服務，還需要依據加工質量#65380;交貨及時性#65380;加工成本#65380;服務質量等指標對候選制造服務集合中的制造服務進行綜合評價。完成綜合評價后，協同制造鏈發起企業將獲得一個優選后的SDPP。在優選后的SDPP中，OR節點已被消除，協同制造任務與制造服務一一對應，即為一個協同制造任務—制造服務對。圖4為某型號航空發動機關鍵零件優選后的SDPP。

在協同制造鏈構建過程中，協同制造鏈發起企業還需進一步對優選后的SDPP進行排序，消除SDPP中的AND節點，最終生成協同制造鏈。圖5為最終生成的某型號航空發動機關鍵零件的協同制造鏈。

4)合同簽訂與項目執行協同制造鏈構建成功后，協同制造鏈發起企業與鏈中的相關制造服務提供商簽訂商務合同，協同制造鏈正式進入運行階段。在協同制造鏈運行階段，采用基于網絡的協作項目管理形式對零件的整個制造過程進行管理。

5)協同制造鏈解體當零件制造任務完成后，各相關企業完成資金結算，協同制造鏈即自行解體。

2協同制造鏈排序問題分析和建模

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

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

3基于螞蟻算法的協同制造鏈排序

3.1螞蟻算法基本原理

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

3.2基于螞蟻算法的協同制造鏈排序

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

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

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

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

a)根據路徑上的信息素濃度，以相應的概率來選擇下一個制造服務提供商。

4結束語

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

參考文獻:

[1]胡開順，姚小群，葉邦彥，等.動態聯盟供應鏈的結構模型及其規劃設計[J].中國制造業信息化，2003，32(1):73－75.

[2]顧寄南.網絡化制造技術[M].北京:化學工業出版社，2004:23－27.

[3]王萃寒，馮徑.網絡化制造的技術體系研究[J].中國制造業信息化，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].北京:北京大學出版社，1998.

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

[7]吳斌.群體智能中的研究及其在知識發現中應用[D].北京:中國科學院計算技術研究所，2002.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”