基于改進粒子群算法的跨組織資源鏈構建研究

王正成 咸 達

浙江理工大學，杭州，310018

0 引言

跨組織的制造資源集成共享與優化配置能有效解決組織間資源占有不平衡、組織資源重復投資等問題，并成為提升制造企業核心競爭力的關鍵。當前多數跨組織協同制造中的資源集成共享研究側重于產品形成過程中單個或部分環節上的資源集成共享，未能在全局上實現資源的優化配置，且聚焦于跨組織協同制造中資源集成共享的個別或部分獨立問題的解決，未能形成系統性的綜合解決方案，最終使得跨組織協同制造中資源集成共享的效率與效果不佳。另外在跨組織制造資源集成共享與優化配置的過程中，如何使各個制造任務在時間、成本、服務、質量等準則下實現全局優化配置，并構建跨組織制造資源鏈是制造企業的關鍵問題之一，該問題是動態模糊多目標決策NP問題，當前大多數文獻從不同的角度對該問題進行求解。如Sawik［1］研究了在供應商選擇和訂單分配的協同制造環境下，考慮供應鏈中斷和延遲的風險，通過該場景分析提出一種混合整數規劃的方法，以合并風險。齊二石等［2］研究了復雜零件協同制造的資源優化配置問題，以加工時間、運輸費用和加工質量為目標建立數學模型，并利用遺傳算法求解。Vanteddu［3］根據供應商選擇問題，主要考慮了庫存成本和周期時間，并將一個“逆反應系數”加入到該問題模型中。孫忠良等［4］針對制造資源配置評價問題，建立了成本收益數據包絡分析數學模型，并提出了資源的優化配置策略。董景峰等［5］以質量、成本、交貨期和交貨提前期為評估指標，建立了數學模型并利用蟻群算法求解此問題。蘇世彬等［6］針對動態聯盟先進制造模式，結合知識管理和模擬退火算法的思路對動態聯盟盟員進行選擇與淘汰。在實際的跨組織資源鏈的構建過程中，考慮的因素復雜多樣，每個企業的生產能力、服務能力、管理能力、產品質量等不同，在選擇的過程中就會導致最優的全局配置不同，而且在求解模型問題的方法上，容易陷入局部最優值且存在收斂速度慢等問題，難以解決大規模全局優化問題。

1 研究思路

本文提出了跨組織資源鏈概念以及通過該資源鏈的構建實現跨組織協同制造中資源集成共享與優化配置的思路，如圖1所示。

圖1 通過資源服務鏈構建與運行實現資源集成共享

2 數學模型

跨組織制造資源鏈首先根據產品形成過程分解協同制造總任務，形成時序與約束關聯的一系列原子任務鏈，在此基礎上原子任務鏈驅動制造資源需求形成由跨地域的資源組成的動態、復雜和基于時序的有向網絡圖，如圖2所示。

圖2 跨組織資源鏈有向網絡結構示意圖

該問題可以形式化描述為：L＝ ｛T，R，rij，Aiu｝（i＝1，2，…，n；j＝1，2，…，mi）。T為某制造企業接到訂單所形成的協同制造總任務，T＝｛T1，T2，…，Tn｝，n為協同制造總任務經分解形成的原子任務數量，mi為某一原子任務Ti的候選資源服務數量。R為候選資源集合，R＝｛R1，R2，…，Rn｝，T1→R1表示為原子任務T1經檢索匹配和選擇評價形成滿足其時序約束需求的候選資源集R1。候選資源rij表示第i個原子任務選擇第j個候選資源服務來完成。Aiu＝ ｛Ciu，Tiu｝表示兩個前后有直接關系的原子任務之間的連接，包含連接成本Ciu和連接時間Tiu。

基于上述考慮，把跨組織資源鏈構建問題轉化為時序約束限制的路徑尋優問題。在實際的跨組織協同制造中，影響跨組織資源服務鏈構建的因素很多，如時間、成本、服務能力、質量、生產能力、環境、信譽等，這些因素都會影響全局最優的跨組織制造服務鏈的構建。由于企業間競爭激烈，內外部環境變化迅速，因此建立一個綜合各種因素的復雜數學模型并進行求解非常困難，也無現實必要性。為此本文不失一般性地將問題抽象化，把協同制造組織最為關注的時間、成本、服務能力作為服務鏈構建的評價指標，由此定義跨組織資源服務鏈的數學模型如下。

定義決策變量：

跨組織協同制造的時間構成主要是各個原子任務生產制造時間和各個時序原子任務之間的協調連接時間，因此定義時間目標函數為

其中，tij表示第i個原子任務在第j個候選資源服務所進行的生產制造時間，t′iu表示從原子任務i轉移到原子任務u的連接時間。將跨組織協同制造任務鏈中每個并行任務轉移到下一任務所需要時間的最大值進行累加，符合現實生活對跨組織協同制造過程時間的構成。

同樣地，跨組織協同制造資源服務鏈的制造成本是由原子任務生產制造成本和各個原子任務之間的連接成本組成的。定義成本目標函數為

其中，cij表示第i個原子任務在第j個候選企業所進行的生產制造成本，diu表示從原子任務i轉移到原子任務u所需的成本，類似于現實生活中的運輸成本。

由于當前候選資源的服務能力frij為效用性指標，而時間、成本都屬于定量指標，因此有必要對服務能力指標進行量綱一修正［7］，可采用：fij＝ （frij－fmin）/（fmax－fmin）進行修正。其中fmax、fmin分別表示服務能力指標的最大值和最小值。定義服務能力目標函數為

很明顯這是一個多目標優化函數的問題，為此引入權重μ，對目標函數進行優化處理：

式中，μ1、μ2、μ3分別為時間T、成本C、服務能力F所占的權重比例；Tmax、Cmax分別為完成整個服務鏈所需要的時間和成本的最大值；Fmin為服務鏈中所選擇的候選企業綜合服務能力的最小值。

為了求解該模型，本文采用Michalewicz等［8］提出的一種罰函數法解除約束，其表達式為

式中，A為起作用的約束集，由所有等式約束和不能滿足的不等式約束組成；α為懲罰因子；p（x）為罰函數；τ為可變懲罰因子；gi（x）為不等式約束；hi（x）為等式約束；q為不等式約束個數；m為條件約束個數。

化簡后的無約束方程的表達式為

由式（13）可知，在迭代初期，對不可行解懲罰較小，需擴大可行解的搜索，避免陷入局部最優解；后期懲罰力度變大，需限定搜索區域，利于快速尋找全局最優解。

3 構建算法

3.1 二進制粒子群優化算法

3.2 改進的粒子群優化算法

3.2.1 粒子位置編碼

例如，有4個原子任務，原子任務1有2個候選企業，原子任務2有3個候選企業，原子任務3有4個候選企業，原子任務4有2個候選企業，其中原子任務1選擇了第1個候選企業，原子任務2選擇了第3個候選企業，原子任務3選擇了第2個候選企業，原子任務4選擇了第1個候選企業，則粒子的編碼位置如圖3所示。此時粒子的編碼位置x＝ ｛1 0 0 0 1 0 1 0 0 1 0｝。

圖3 粒子位置編碼構造圖

3.2.2 粒子的參數設置

粒子i在D維空間進行搜索，相當于粒子在所有的候選企業中搜索最優的解，在BPSO算法中，慣性權重w決定了粒子先前速度對當前速度的影響程度，直接關系到BPSO算法的搜索能力與收斂速度。當慣性權重較大時，有利于全局搜索，且收斂速度快，但不易得到精確解；當慣性權重較小時，有利于局部搜索，但容易陷入局部最優解。本文參照文獻［10］對w采用線性遞減策略，公式為

其中，wmax、wmin分別為慣性權重的最大值和最小值，Tmax為最大迭代次數，t為當前迭代次數。將粒子的初始速度設為

這樣在迭代開始時，可以很快地進行全局搜索，定位最優解的大致位置，隨著w的減小，粒子速度減小，開始進行局部搜索，尋找最精確的最優解。

如果粒子的速度超出vmax，可能會使粒子飛過最優解；若粒子的速度太小，則導致粒子收斂速度過小，可能被局部最優解所吸引，無法找到最優解，因此對［vmin，vmax］范圍外的粒子速度進行修正：

3.2.3 粒子的位置更新

將式（20）進行歸一化處理：

位置的更新公式如下：

其中，ρ為［0，1］之間的隨機數。例如跨組織資源鏈中原子任務1的候選企業有3個，歸一化后的概率分別為0.35、0.25、0.40，產生的隨機數為0.72，由于0.72在（0.6，1）之間，因此原子任務1應選擇候選企業3，并將候選企業3的位置x13設置為1，x11、x12設置為0。

3.2.4 算法實現

利用改進的粒子群算法求解該模型的偽代碼如下：

4 算例仿真

本文假設有一跨組織協同制造鏈（圖4），有5個原子任務，每個原子任務的候選企業個數和每個候選企業的生產制造的時間（單位為天）、成本（單位為千元）、服務能力參數如表1所示，各個原子任務之間的連接成本、時間參數等如表2～表4所示。其中Rij表示原子任務i選擇第j個候選企業。

圖4 仿真算例跨組織協同制造鏈網絡拓撲結構示意圖

表1 候選企業的服務能力、成本、時間參數表

表2 具有時序性的候選企業的連接時間

表3 具有時序性的候選企業的連接成本

表4 服務鏈中最后轉移到目的地的參數表

最后通過MATLAB平臺進行仿真計算，其中設Cmax＝100千元；Tmax＝23d；Fmin＝4.5；采用改進的粒子群算法（CPSO）進行計算，粒子數為30，迭代次數為200，學習因子c1＝c2＝1.494 45，wmax＝0.9，wmin＝0.4；vmax＝6，vmin＝－6；跨組織協同制造鏈中評價指標的權重可根據具體問題進行相應的分析，如μ3＝0，則該模型就是基于時間和成本考慮的服務鏈模型，這里可令μ1＝0.3，μ2＝0.3，μ3＝0.4。最后求解的結果為minZ＝37.476，其中成本為97千元，完成任務所需時間為21.6d，服務能力為4.74。此時粒子的最優位置x＝｛0 1 1 0 0 0 1 1 0 0 0 1 0｝，構建的跨組織協同制造服務鏈如圖5所示。在求解該跨組織協同制造服務鏈時將改進后的粒子群算法與標準的粒子群算法相比較，如圖6所示，可以看到BPSO陷入局部最優值，并且收斂速度較慢，而改進后的粒子群算法收斂速度較快，到達最優值的迭代次數少，該結果表明改進后的粒子群算法能夠獲得最優值并具有非?？斓氖諗克俣?。

圖5 最優的跨組織資源服務鏈構造圖

圖6 算法仿真比較示意圖

5 結束語

本文通過對跨組織協同制造資源服務鏈的研究，構建了以時間、成本和服務能力為評價指標體系的數學模型，通過罰函數法將約束問題轉變成無約束優化問題，并利用改進的粒子群算法進行求解，提出了粒子的編碼方法，并對粒子的速度進行處理，歸一化后的概率可以決定粒子的位置，直接對候選資源的選擇進行判定。該算法具有收斂速度快、全局優化能力強、不易陷入局部最優的優點。最后通過仿真算例驗證了算法的高效性，為解決跨組織協同制造資源服務鏈的研究問題提供了一種切實可行的方法。

［1］Sawik T.Selection of a Dynamic Supply Portfolio in Make－to－order Environment with Risks［J］.Computers and Operations Research，2011，4（38）：782－796.

［2］齊二石，李輝，劉亮.基于遺傳算法的虛擬企業協同資源優化問題研究［J］.中國管理科學，2011，19（1）：77－83.

Qi Ershi，Li Hui，Liu liang.Research on Collaborative Resource Optimization of Virtual Enterprises Based on Genetic Algorithm［J］.Chinese Journal of Management Science，2011，19（1）：77－83.

［3］Vanteddu G.Supply Chain Focus Dependent Supplier Selection Problem［J］.International Journal of Production Economics，2011，129（1）：204－216.

［4］孫忠良，吳文武，洪軍，等.基于數據包絡分析的網絡化制造聯盟企業制造資源配置評價研究［J］.計算機集成制造系統，2008，14（5）：962－969.

Sun Zhongliang，Wu Wenwu，Hong Jun，et al.Resource Allocation Evaluation of Networked Manufacturing Extended Enterprise Based on DEA［J］.Computer Integrated Manufacturing Systems，2008，14（5）：962－969.

［5］董景峰，王剛，呂民，等.基于改進蟻群算法的多供應商選擇問題求解［J］.計算機集成制造系統，2007，13（8）：1639－1644.

Dong Jingfeng， Wang Gang，Lü Min，et al.Multi－supplier Selection Problem Solution Based on Improved Ant Colony Algorithm［J］.Computer Integrated Manufacturing Systems，2007，13（8）：1639－1644.

［6］蘇世彬，黃瑞華.基于模擬退火算法的動態聯盟盟員的動態選擇［J］.中國管理科學，2005，13（1）：90－94.

Su Shibin，Huang Ruihua.Members Dynamic Selection Based on Simulated Annealing Algorithm in Virtual Enterprise［J］.Chinese Journal of Management Science，2005，13（1）：90－94.

［7］王正成，謝先文.基于FAHP和改進蟻群算法的網絡化制造資源鏈構建研究［J］.中國機械工程，2012，23（12）：1487－1492.

Wang Zhengcheng，Xie Xianwen.Resource Service Chain Construction for Networked Manufacturing Based on FAHP and Improved Ant Colony Algorithm［J］.China Mechanical Engineering，2012，23（12）：1487－1492.

［8］Michalewicz Z，Schoenauer M.Evolutionary Algorithms for Constrained Parameter Optimization Problems［J］.Evolutionary Computation Journal，2010，4（1）：1－32.

［9］Kennedy J，Eberhart R C.A Discrete Binary Version of the Particle Swarm Algorithm［C］//Proceeding of the World Multiconference on Systemics，Cybernetics and Informatics.Piscataway：IEEE Service Center，1997：4104－4109.

［10］王正成，潘曉弘，潘旭偉.基于蟻群算法的網絡化制造資源服務鏈構建［J］.計算機集成制造系統，2010，16（1）：174－181.

Wang Zhengcheng，Pan Xiaohong，Pan Xuwei.Resource Service Chain Construction for Networked Manufacturing Based on Ant Colony Algorithm［J］.Computer Integrated Manufacturing Systems，2010，16（1）：174－181.