基于改進(jìn)粒子群算法的跨組織資源鏈構(gòu)建研究

王正成 咸 達(dá)

浙江理工大學(xué)，杭州，310018

0 引言

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

1 研究思路

本文提出了跨組織資源鏈概念以及通過(guò)該資源鏈的構(gòu)建實(shí)現(xiàn)跨組織協(xié)同制造中資源集成共享與優(yōu)化配置的思路，如圖1所示。

圖1 通過(guò)資源服務(wù)鏈構(gòu)建與運(yùn)行實(shí)現(xiàn)資源集成共享

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

跨組織制造資源鏈?zhǔn)紫雀鶕?jù)產(chǎn)品形成過(guò)程分解協(xié)同制造總?cè)蝿?wù)，形成時(shí)序與約束關(guān)聯(lián)的一系列原子任務(wù)鏈，在此基礎(chǔ)上原子任務(wù)鏈驅(qū)動(dòng)制造資源需求形成由跨地域的資源組成的動(dòng)態(tài)、復(fù)雜和基于時(shí)序的有向網(wǎng)絡(luò)圖，如圖2所示。

圖2 跨組織資源鏈有向網(wǎng)絡(luò)結(jié)構(gòu)示意圖

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

基于上述考慮，把跨組織資源鏈構(gòu)建問(wèn)題轉(zhuǎn)化為時(shí)序約束限制的路徑尋優(yōu)問(wèn)題。在實(shí)際的跨組織協(xié)同制造中，影響跨組織資源服務(wù)鏈構(gòu)建的因素很多，如時(shí)間、成本、服務(wù)能力、質(zhì)量、生產(chǎn)能力、環(huán)境、信譽(yù)等，這些因素都會(huì)影響全局最優(yōu)的跨組織制造服務(wù)鏈的構(gòu)建。由于企業(yè)間競(jìng)爭(zhēng)激烈，內(nèi)外部環(huán)境變化迅速，因此建立一個(gè)綜合各種因素的復(fù)雜數(shù)學(xué)模型并進(jìn)行求解非常困難，也無(wú)現(xiàn)實(shí)必要性。為此本文不失一般性地將問(wèn)題抽象化，把協(xié)同制造組織最為關(guān)注的時(shí)間、成本、服務(wù)能力作為服務(wù)鏈構(gòu)建的評(píng)價(jià)指標(biāo)，由此定義跨組織資源服務(wù)鏈的數(shù)學(xué)模型如下。

定義決策變量：

跨組織協(xié)同制造的時(shí)間構(gòu)成主要是各個(gè)原子任務(wù)生產(chǎn)制造時(shí)間和各個(gè)時(shí)序原子任務(wù)之間的協(xié)調(diào)連接時(shí)間，因此定義時(shí)間目標(biāo)函數(shù)為

其中，tij表示第i個(gè)原子任務(wù)在第j個(gè)候選資源服務(wù)所進(jìn)行的生產(chǎn)制造時(shí)間，t′iu表示從原子任務(wù)i轉(zhuǎn)移到原子任務(wù)u的連接時(shí)間。將跨組織協(xié)同制造任務(wù)鏈中每個(gè)并行任務(wù)轉(zhuǎn)移到下一任務(wù)所需要時(shí)間的最大值進(jìn)行累加，符合現(xiàn)實(shí)生活對(duì)跨組織協(xié)同制造過(guò)程時(shí)間的構(gòu)成。

同樣地，跨組織協(xié)同制造資源服務(wù)鏈的制造成本是由原子任務(wù)生產(chǎn)制造成本和各個(gè)原子任務(wù)之間的連接成本組成的。定義成本目標(biāo)函數(shù)為

其中，cij表示第i個(gè)原子任務(wù)在第j個(gè)候選企業(yè)所進(jìn)行的生產(chǎn)制造成本，diu表示從原子任務(wù)i轉(zhuǎn)移到原子任務(wù)u所需的成本，類(lèi)似于現(xiàn)實(shí)生活中的運(yùn)輸成本。

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

很明顯這是一個(gè)多目標(biāo)優(yōu)化函數(shù)的問(wèn)題，為此引入權(quán)重μ，對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化處理：

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

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

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

化簡(jiǎn)后的無(wú)約束方程的表達(dá)式為

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

3 構(gòu)建算法

3.1 二進(jìn)制粒子群優(yōu)化算法

3.2 改進(jìn)的粒子群優(yōu)化算法

3.2.1 粒子位置編碼

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

圖3 粒子位置編碼構(gòu)造圖

3.2.2 粒子的參數(shù)設(shè)置

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

其中，wmax、wmin分別為慣性權(quán)重的最大值和最小值，Tmax為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。將粒子的初始速度設(shè)為

這樣在迭代開(kāi)始時(shí)，可以很快地進(jìn)行全局搜索，定位最優(yōu)解的大致位置，隨著w的減小，粒子速度減小，開(kāi)始進(jìn)行局部搜索，尋找最精確的最優(yōu)解。

如果粒子的速度超出vmax，可能會(huì)使粒子飛過(guò)最優(yōu)解；若粒子的速度太小，則導(dǎo)致粒子收斂速度過(guò)小，可能被局部最優(yōu)解所吸引，無(wú)法找到最優(yōu)解，因此對(duì)［vmin，vmax］范圍外的粒子速度進(jìn)行修正：

3.2.3 粒子的位置更新

將式（20）進(jìn)行歸一化處理：

位置的更新公式如下：

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

3.2.4 算法實(shí)現(xiàn)

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

4 算例仿真

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

圖4 仿真算例跨組織協(xié)同制造鏈網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)示意圖

表1 候選企業(yè)的服務(wù)能力、成本、時(shí)間參數(shù)表

表2 具有時(shí)序性的候選企業(yè)的連接時(shí)間

表3 具有時(shí)序性的候選企業(yè)的連接成本

表4 服務(wù)鏈中最后轉(zhuǎn)移到目的地的參數(shù)表

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

圖5 最優(yōu)的跨組織資源服務(wù)鏈構(gòu)造圖

圖6 算法仿真比較示意圖

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

本文通過(guò)對(duì)跨組織協(xié)同制造資源服務(wù)鏈的研究，構(gòu)建了以時(shí)間、成本和服務(wù)能力為評(píng)價(jià)指標(biāo)體系的數(shù)學(xué)模型，通過(guò)罰函數(shù)法將約束問(wèn)題轉(zhuǎn)變成無(wú)約束優(yōu)化問(wèn)題，并利用改進(jìn)的粒子群算法進(jìn)行求解，提出了粒子的編碼方法，并對(duì)粒子的速度進(jìn)行處理，歸一化后的概率可以決定粒子的位置，直接對(duì)候選資源的選擇進(jìn)行判定。該算法具有收斂速度快、全局優(yōu)化能力強(qiáng)、不易陷入局部最優(yōu)的優(yōu)點(diǎn)。最后通過(guò)仿真算例驗(yàn)證了算法的高效性，為解決跨組織協(xié)同制造資源服務(wù)鏈的研究問(wèn)題提供了一種切實(shí)可行的方法。

［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］齊二石，李輝，劉亮.基于遺傳算法的虛擬企業(yè)協(xié)同資源優(yōu)化問(wèn)題研究［J］.中國(guó)管理科學(xué)，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］孫忠良，吳文武，洪軍，等.基于數(shù)據(jù)包絡(luò)分析的網(wǎng)絡(luò)化制造聯(lián)盟企業(yè)制造資源配置評(píng)價(jià)研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，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ìn)蟻群算法的多供應(yīng)商選擇問(wèn)題求解［J］.計(jì)算機(jī)集成制造系統(tǒng)，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］蘇世彬，黃瑞華.基于模擬退火算法的動(dòng)態(tài)聯(lián)盟盟員的動(dòng)態(tài)選擇［J］.中國(guó)管理科學(xué)，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ìn)蟻群算法的網(wǎng)絡(luò)化制造資源鏈構(gòu)建研究［J］.中國(guó)機(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］王正成，潘曉弘，潘旭偉.基于蟻群算法的網(wǎng)絡(luò)化制造資源服務(wù)鏈構(gòu)建［J］.計(jì)算機(jī)集成制造系統(tǒng)，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.