基于FAHP和改進蟻群算法的網絡化制造資源鏈構建研究

王正成 謝先文

浙江理工大學，杭州，310018

0 引言

隨著制造與網絡信息技術的不斷融合，利用網絡優勢、協同網絡制造資源組成跨組織制造資源鏈是制造業發展的必然趨勢。在異地跨組織制造資源的協同與共享過程中，如何解決好協同制造任務在時間、成本、服務、質量準則下資源的優化配置，構建網絡化制造資源服務鏈是目前制造業亟待解決的問題。當前對網絡化制造資源鏈的研究，還停留在部分制造企業的制造資源集成上，實現的是某些環節上制造資源的優化配置，而沒有從全局考慮的角度出發，協同、集成和共享跨組織的異地制造資源，組成最優的制造加工路線，從而實現整個行業資源的優化配置。

本文針對上述研究的不足，以協同制造總任務的任務分解及單任務驅動的網絡候選制造資源的評價選擇為基礎，構建網絡化協同制造總任務資源鏈模型；利用轉移時間、成本和綜合制造能力建立評價函數，并采用改進的蟻群算法對該模型進行求解。

1 研究綜述

協同制造總任務的分解是網絡化制造關注的核心問題之一。研究人員從策略、模型、方法和技術等多個視角對此進行了大量的研究。如文獻［1］為解決任務分解分配與跨組織協同業務過程分離問題，提出了基于工作流的任務分解分配方法，并建立了基于Petri網的任務分解分配工作流模型。文獻［2－3］針對協同制造任務類多量大，導致計算復雜、求解困難的問題，以智能多A－gent技術為基礎，分別提出了一種避免死鎖和基于Agent自動協商的任務分解與分配機制。本文從制造任務與網絡制造資源的匹配性以及分解粒度角度出發，提出一種基于網絡資源匹配的任務分解算法，使得協同制造總任務能夠很好地分解與分配。

時序約束單任務驅動網絡制造資源的評價選擇影響著整個服務加工路線的優劣。目前對設備資源的評價方法主要有層次分析法、模糊綜合評價法［4］、灰色關聯分析法［5］、模糊層次分析法。網絡制造資源具有海量性特征且各評價要素之間相互影響、相互聯系，模糊且難以量化，因此，本文采用模糊層次算法（FAHP）對網絡設備資源進行評價篩選，從而找到最優的設備資源。

跨組織網絡化制造資源鏈的構建是一個多目標決策NP問題，解決這一問題的主要方法有遺傳算法［6］、神經網絡法、關聯分析法、退火算法以及蟻群算法［7］。但是這些方法通常存在收斂速度慢和易于陷入局部最優等缺點，難以解決大規模的優化問題。本文針對網絡制造任務的時序約束性和資源的異或性特征，構建適合于蟻群算法的網絡資源鏈模型，并對蟻群算法進行改進以適應該模型，加快算法的收斂速度，提高最優解的質量。

2 相關關鍵技術方法研究

2.1 網絡制造協同總任務的分解過程與算法

2.1.1 制造任務分解及算法的描述

網絡制造協同總任務的分解是以現存的網絡制造設備資源為前提，按照制造產品的層次、粒度及擴散次序逐步向下分解，使得分解的協同制造子任務能夠找到與之相匹配的制造資源。因此采用如下公式對網絡制造協同總任務進行描述：

其中，ti、ci、qi分 別 為 時 間、成 本、質 量；Tmax、Cmax、Qmin分別為允許的最長時間、最大成本、最小質量要求。I為輸入的將要分解的制造任務。利用任務分解原則，自頂而下分解。S（i）為約束集判斷函數，當前任務分解后，判斷是否存在與之相匹配的制造資源，滿足約束則S（i）取值為1，反之則取值為0。i為分解層次。（O，Taski－1）中的O表示當S（i）取值為1時，任務分解成功，輸出該子任務；Taski－1表示當網絡平臺不存在與任務相匹配的資源時，進入下一步分解，以此類推。網絡制造任務的分解算法及過程如圖1所示。網絡候選資源庫為網絡平臺提供制造資源，采用貪婪算法搜索和發現協同制造子任務的網絡制造資源，規則庫為任務分解的原則及相關專業知識。

圖1 網絡制造任務分解流程圖

2.1.2 算法實現

（1）任務初始分解。分析輸入任務的整體情況，掌握產品的基本結構和模塊化特點，根據制造產品的擴散順序，按照協同制造總任務的分解原則（規則庫）對該任務進行部件級分解。令層次為i＝1。

（2）搜索子任務的網絡候選制造資源服務。經步驟（1）分解后，采用貪婪算法在網絡制造資源集成平臺上檢索發現所有能完成這些子任務的候選資源服務。

（3）任務分解終止判定。對于尋找到的所有候選資源，采用約束判斷函數S（i），判斷這些資源是否滿足時間、成本、質量的約束。若S（i）＝1，則任務分解結束，儲存該分解方案；若S（i）＝0，則轉到步驟（1）且i←i＋1。

（4）將子任務集進行匯總，形成制造產品結構順序圖。按照產品的結構與功能模塊對制造子任務進行匯總，再根據分解層次的順序進行逆序組合形成產品結構圖。

（5）分解結束，并將該網絡協同制造總任務的分解方案添加到知識庫，以備后用。

2.2 單任務驅動的網絡化制造資源選擇評價

為每個分解形成的單任務選出合適的資源服務是網絡化制造資源集成共享的目標，而對資源服務進行科學評價是任務提交方作出正確決策的前提，因此，建立一套行之有效的評價指標體系是任務提交方對網絡化制造資源服務進行選擇的依據。網絡化制造資源選擇評價是一個多層面、多方參與、復雜的系統工程，涉及很多因素，并且各因素之間存在著復雜的聯系。

2.2.1 評價指標體系的建立

影響網絡化制造資源服務選擇的因素很多，根據任務類型、目的和性質的不同，對資源服務選擇的考察重點也不同。在合作伙伴選擇評價指標和方法方面，國內外學者做了大量的研究和實踐，本文在總結相關研究成果的基礎上，結合網絡化制造資源合作共享的特點，遵循指標系統全面性、科學性、靈活可操作性以及定性定量相結合的原則，對網絡化制造資源服務評價指標體系進行了分層構建，從時間因素、質量因素、成本因素、服務因素、能力因素、信譽因素和匹配因素等角度進行分析，建立了圖2所示的網絡化制造資源服務評價指標體系。

圖2 網絡化制造設備資源評價指標體系

2.2.2 模糊層次分析法（FAHP）

模糊綜合層次分析法是模糊綜合評價法與層次分析法相結合的一種綜合評價方法，該方法根據模糊數據理論將定性問題定量化，使得復雜問題變得簡單易量化。FAHP用于網絡化制造資源評價的基本思想是利用模糊理論簡化復雜指標的度量，弱化人的主觀性，并以客觀數值反映網絡制造設備資源的優劣。本文根據網絡候選制造資源設備的特點，對FAHP作相應改進以適應其評價選擇。

（1）在已有的時間、質量、成本、服務因素的基礎上，加入協同企業的信譽因素、能力因素和匹配因素，使得網絡候選資源設備的評價更加全面、具體、可量化。

（2）利用已建立的評價指標體系，根據指標之間的重要程度建立模糊一致矩陣，并運用層次權重公式計算得到下層因素針對上一因素的權重序列

其中，rij為評價指標體系中因素ai與因素aj相比較重要性標度值，即模糊一致性矩陣中第i行j列的值。參數λ滿足為因素ai在目標Ok下的權重。根據圖2可知，該過程需進行兩次層次間的排序，將得到的兩次權重綜合，得到最后一層因素對于總目標的綜合權重ωT。

（3）在方案層中，各指標不再進行重要程度的相互比較，而是經過實地調研，得到網絡候選制造資源的樣本數據矩陣，并對其進行歸一化處理，直接反映出子準則對頂層目標的重要程度。在這一過程中，需要采用統一量綱函數，對于收益性指標，如質量、綜合性能等采用以下公式：

而對于成本類的屬性指標，如時間、成本因素等，則采用如下轉換公式：

得到網絡候選制造資源的樣本數據矩陣R（k）。

（4）建立隸屬度矩陣U，將矩陣中的各數據值限制在［1，10］中。以數值的形式反映到最后的綜合性能評價上，利于制造設備資源的排序，為之后整個網絡化制造設備資源鏈的構建提供便利。

（5）根據評價指標權重ωT、制造資源樣本數據矩陣R（k）及隸屬度矩陣U，采用公式Z＝UωTR（k）確定各網絡制造設備資源綜合性能值Z；根據Z的大小對各網絡制造資源設備的進行排序，并為建立網絡化制造服務鏈的評價函數min F提供數據支持。

2.3 多任務驅動的網絡化制造資源鏈構建算法

2.3.1 蟻群算法基本原理

蟻群算法具有良好反饋性，能夠很好地解決多任務驅動的網絡化制造資源鏈構建問題。

利用圖論知識對網絡制造資源鏈進行描述：帶權有向網絡圖G＝（V，E，A，W），其中，V 為網絡制造設備資源集，E為兩節點的邊集，A為各網絡制造資源集的綜合制造能力，W 為E上各邊的權值的有窮集，包括轉移成本參數C和轉移時間參數D。基于G＝（V，E，A，W）的蟻群算法組成模型如圖3所示。

為將各模塊之間的操作規則表述清晰，用如下符號標記：n為網絡候選設備資源集，m為螞蟻數 量 ，t 為 循 環 次 數為兩個不同任務之間的轉移費用，其中ij為后序資源編號，ef為前序資源編號表示轉移時間表示能見度因子表示t時刻（ef，ij）上的信息素濃度；Start、End表示起點與終點；初始時刻所有螞蟻都在起點，各邊信息素濃度為常量（cons）。螞蟻搜索過程轉移規則如下：

圖3 基于G＝ （V，E，A，W）的蟻群模型

式中，allowed表示螞蟻下一步可選擇的路徑表；α為路徑的相對重要性；β為路徑能見度相對重要性。

當完成一次遍歷后，各路徑上的信息素濃度采用以下公式進行更新：

式中，ρ為信息揮發度；Q為螞蟻循環一個過程所釋放的信息素總量；Lk為轉移成本或轉移時間為第k只螞蟻在本次循環中留在連接（ef，ij）上的信息 增 量為 本 次 循 環 中 （ef，ij） 邊 上 的 信息增量。

2.3.2 算法改進

網絡制造資源鏈的蟻群模型與基本蟻群算法存在差異：首先前者具有時序性，只有當前序制造子任務完成后，才能開始后序的任務，并且起始節點都固定。其次網絡制造資源具有異或性，即同一任務的提供網絡候選設備資源只能從中選取一個。

根據以上特點，對基本蟻群算法進行改造：①根據網絡制造任務的制造時序，進行升序編號，則禁忌表的網絡候選設備資源的編號都是連續的。②在禁忌表中加入一個控制變量Hi，當Ri中的某一資源被選用，則Hi記錄相關信息并將Ri中其他候選資源排除出禁忌表，而自身變為Hi＋1。

另外，基本蟻群算法存在收斂速度慢、易陷于局部最優的特點，本文采用序排列和獎懲思想相結合，對其進行改進。具體做法如下：在信息素更新前，對排名前L只螞蟻進行獎勵，以快速提高短路徑信息素濃度；為防止該算法陷入局部最優，再將揮發因子ρ值設置到相對高，另外將各邊上的信息素濃度限制在［τmin，τmax］范圍內。具體采用下列公式對信息素進行更新：

其中，l是被挑選出來被獎勵的螞蟻數量，排序數越小，獎勵的信息濃度越高。根據所構建的網絡蟻群模型及其相應的改進，建立網絡化制造資源鏈的評價函數：C和D分別為Ri之間轉移而產生轉移成本和轉移時間；Z表示制造資源的綜合制造能力，其值來源于網絡候選資源設備的評價選擇。綜合考慮上述因素，建立設備資源鏈的評價函數：

其中，因整個制造過程存在著并行和串行任務，所以轉移時間D為完成所有轉移制造任務中的最長時間Dmax。另外C、D為成本性指標，而Z為效應性指標，根據文獻［7］所述方法進行量綱修正。μ1、μ2、μ3為加權系數，表示目標的相對重要性，且μ1＋μ2＋μ3＝1。

3 算例

某模具制造企業2011年2月10日接到一個大型注塑模具制造的訂單，批量為10件，總成本不超過500萬元，交貨期為2011年3月16日。由于該企業制造設備資源有限，需尋找本企業外的資源來共同完成該大型注塑模具的制造任務。

首先對總任務制造工藝及流程進行分析，單臺產品制造成本為44萬元，制造時間為30天，由此可知單臺產品的轉移成本Cmax≤6萬元，轉移時間Dmax≤6d，整個制造資源鏈綜合性能經過量綱修正為Zmax≤50。約束為

然后，采用分解算法對該任務進行分解，主要包含7個子任務，本企業加工模架和模具裝配，而其他子任務通過企業協作來完成。對子任務進行編號，工藝流程如圖4所示。

圖4中Task1為模架加工和模板加工，Task2為型腔的初步加工，Task3為電極加工，Task4為型芯的電火花加工，Task5為模具裝配。Start為任務的發起方（只發布相關的制造任務，不存在實物的轉移，線條為虛線），End為最終回歸到企業。

圖4 任務分解后的制造流程

之后，利用網絡候選資源的優劣排序，從中選出2個較優的設備資源參加網絡化制造資源服務鏈的構建。其中表示任務e到任務i的轉移成本（任務i是任務e時序約束下的緊后任務），主要包括執行任務e的候選資源服務與執行任務i的候選資源服務兩者間的物流成本、協作交易成本和等待成本等。表示任務e到任務i的轉移時間，主要包括執行任務e的候選資源服務與執行任務i的候選資源服務兩者間的物流時間、協作交易時間和等待時間等。Zij表示提供制造資源的企業的綜合制造能力。提供的網絡制造資源用Rij表示。表1所示為各制造資源的綜合制造性能，表2所示為各子任務的轉移時間和轉移成本。

表1 制造資源的綜合制造能力

表2 制造產品的轉移費用C（千元）和轉移時間D（d）

最后，在MATLAB平臺上進行模擬仿真計算，采用改進的蟻群算法設置初始參數：螞蟻數量m＝20，α＝1，β＝5，ρ＝0.5，Q＝100，l＝10。經計算得到轉移成本∑C＝5.4萬元，轉移時間∑D＝5.7d，總的綜合性能為∑Z＝45.7。這些因素都滿足成本、時間、綜合性能的約束，因此該網絡化制造資源鏈可行，令μ1＝0.3，μ2＝0.3，μ2＝0.4，網絡化制造資源鏈評價函數 minF＝36.19。該鏈的構建如圖5所示。

圖5 網絡制造資源組成的加工鏈

4 結語

本文算法利用資源服務鏈的順序性和候選資源的異或性特征，有效地縮小最優解的搜索空間。另外獎勵排名前l只尋找到短路徑的螞蟻，并限制路徑上信息素濃度上下限，既加快了它的收斂速度，又使之不陷入局部最優。但當協同制造總任務分解形成的子任務數量較多，且各個子任務對應的候選資源服務也較多時，構建跨組織資源服務鏈計算量會呈指數級增長，導致算法搜索時間偏長。跨組織制造資源服務類多量大，在實際應用中因網絡化制造合作的動態性和除時間、成本、質量等定量因素外的定性因素較多，因此較難建立令人信服的制造資源服務評價指標模型。本文的研究基于了一種現實可行假設：單任務僅由單資源服務完成，而不存在單任務在多資源服務中分配調度問題。在采用模糊層次分析法對候選資源服務選擇評價時，會形成由于候選資源服務指標過多導致數據統計量大，且各指標權重難以確定的問題。上述問題在網絡化制造資源服務集成共享與優化配置中有待進一步研究。

［1］ 唐達，李元生.基于層次細化Petri網的工作流參與者機制與動態特性研究［J］.計算機研究與發展，2004，41（9）：1545－1553.

［2］ Hsieh F S.Deadlock Free Task Distribution and Resource Allocation for Holonic Manufacturing System Based on Multi－agent Framework［C］／／IEEE International Conference on System，Man and Cybernetics.Tucson，USA，2001：2463－2468.

［3］ Lou P，Zhou Z D，Chen Y P，et al.Negotion based Task Allocation in An Open Supply Chain Environment［J］.Proc.of the Institution of Mechanical Engineers，Part B：Journal of Engineering Manufacture，2006，220（6）：975－985.

［4］ 武志軍，寧汝新，王愛民.可重構制造系統布局規劃方案的灰色模糊綜合評價方法［J］.中國機械工程，2007，18（19）：2313－2318.

［5］ 孫忠良，荊無名，洪軍，等.基于層次分析法的模具網絡化制造企業匹配技術［J］.西安交通大學學報，2008，42（3）：291－294.

［6］ 劉金山，廖文和，郭宇.基于雙鏈遺傳算法的網絡化制造資源優化配置［J］.機械工程學報，2008，44（2）：189－195.

［7］ 唐衛寧，徐福緣.基于改進混合蟻群算法的大批量定制協同制造鏈優化［J］.中國機械工程，2008，19（23）：19－24.