任務分解結(jié)構下的虛擬企業(yè)制造伙伴選擇優(yōu)化算法

［摘 要］ 為構建高效且具有市場競爭力的虛擬企業(yè)，根據(jù)各項子任務的需要，在進行任務分解的基礎上對合作伙伴進行優(yōu)化選擇。通過對任務完成的交貨期、質(zhì)量、成本和服務對候選企業(yè)進行評價，在此基礎上建立數(shù)學模型，并針對此問題，提出了基于Dijkstra 方法的改進優(yōu)化算法，且以實例說明了算法的有效性。

［關鍵詞］ 虛擬企業(yè)；伙伴選擇；任務分解；Dijkstra方法

［中圖分類號］F270.7；F224.0［文獻標識碼］A［文章編號］1673-0194（2008）18-0065-03

0 引 言

虛擬企業(yè)的組建是通過選擇構成虛擬企業(yè)的各成員來確定其基本結(jié)構和運作方式的，合作伙伴的選擇在很大程度上決定了虛擬企業(yè)運行的平穩(wěn)性和運作效能。關于虛擬企業(yè)合作伙伴的選擇方法，S. Talluri和R. C. Baker［1］提出了兩階段的伙伴選擇過程模型，并提出了一種設計經(jīng)營聯(lián)盟的定量分析框架，在用數(shù)據(jù)包絡分析法（DEA）初選合作伙伴的基礎上，用整體目標規(guī)劃法終選伙伴組合方案但DEA分析只是一個局部搜索的優(yōu)化方法，可操作性差，而且該模型僅考慮了伙伴選擇過程中的定量因素，忽略了其中大量存在的非定量因素，如信任、文化融合性、通訊可能性等。另外，它對所有的潛在合作伙伴都要進行定量分析，這樣不僅造成模型可操作性差，而且應用過程復雜。陳菊紅、汪應洛等［2］分析了虛擬企業(yè)伙伴選擇過程中應考慮的因素及應遵循的原則，在此基礎上給出了伙伴選擇過程的三階段模型及其實現(xiàn)方法。L． Mikhailov等［3］在層次分析法（AHP）［4］的基礎上，對其進行改進，提出了模糊層次分析法（F－AHP），給出了伙伴選擇的定性分析方法和定量分析方法。

影響伙伴選擇的因素太多，人們常常不能直接做出決策，而必須借助于有效的決策工具來做出正確的選擇。目前，大多數(shù)文獻中對于伙伴選擇問題沒有考慮到任務分解后各子任務的特性，而是默認在所有的指標體系下不同子任務間的指標權重是相同的［5，6］，因此，相應的決策模型也就無法針對具體的子任務給出科學合理的結(jié)果。為此，本文在虛擬企業(yè)組建之初對任務進行分解，然后重點探討一種基于任務分解結(jié)構下的制造伙伴選擇的優(yōu)化算法。

1 問題描述

某個企業(yè)因具有敏銳的市場洞察力而迅速抓住一個市場機會，獲得一個由多個任務組成的大項目。以該企業(yè)本身的能力和資源不足以完成整個任務，因此必須通過組建虛擬企業(yè)來完成此項目。所以，先對整個任務進行分解，再針對各個子任務進行招標。將制造任務分解成若干子任務，制造任務由n項子任務組成，這些子任務由先后銜接關系構成一個活動網(wǎng)絡（如圖1所示），圖中箭頭順序表示任務之間的約束關系，前一任務必須比后一任務提前一段時間完成，但并不意味著前一任務完成之后，后一任務才能開始。每一個子任務都有若干個候選企業(yè)參與競爭，且每個子任務只能選擇一個企業(yè)作為合作伙伴。

2 數(shù)學模型

在運用數(shù)學方法描述問題前，先給出描述該問題所要用到的數(shù)學符號。

（1）所有制造子任務的集合為i，{i=1，2，…，n}；

（2）圖1中所有弧的集合為A，A={（i， j）| i，j=1，2，…，n}表示任務間的時序關系，即（i， j）表示任務i是任務j的緊前任務；

（3）子任務i的候選企業(yè)的集合為E（E={e| j∈[1，m]}），競標子任務i的候選企業(yè)數(shù)量為m；

（4）候選企業(yè)P完成任務i的各種參數(shù)：制造費用為

c，產(chǎn)品質(zhì)量為q，能夠成功完成子任務i的概率為r；

（5）該項目的總工期為T，項目的持續(xù)時間為T。

該問題的優(yōu)化目標是確定將子任務i分配給第j個候選企業(yè)e，使該項目以最小的費用C，最好的質(zhì)量Q和最大的成功率R如期完成。

目標函數(shù)：minC=cy。

maxQ=qy/y。

maxR=ry/y。

約束條件：T≤T，y=1，候選企業(yè)

e中標；

0，候選企業(yè)

e未中標。

3 Dijkstra方法改進下的優(yōu)化算法［7，8］

3. 1有向網(wǎng)絡圖的描述

圖2是一個有向網(wǎng)絡圖，圖中每一個圓圈代表一個子任務，圓圈中的數(shù)字表示制造任務的編號。如果j是i的緊后任務，則i和j之間由始于i并指向j的有向弧聯(lián)結(jié)，并用（i， j）表示。所以，這里可以借鑒在一個賦權有向網(wǎng)絡圖中尋求最短路徑的方法——Dijkstra法來確定候選企業(yè)的組合優(yōu)化問題。為了推導出Dijkstra法改進下的優(yōu)化算法，這里先用有向網(wǎng)絡圖來描述要求解的問題。

圖2中P表示子任務i的候選企業(yè)，H表示所有有向弧的集合。由此得到一個不完全的多部分圖G（P，H），由圖形可知，問題求解轉(zhuǎn)化為在圖G（P，H）中求得一個頂點集合S=S

，S

，…，S

，使之滿足目標函數(shù)的要求。

3. 2Dijkstra法的改進

考慮一個給定的候選制造企業(yè)集合的序列P，P，…，P，先選擇S∈P，然后選擇S∈P，…，最后選擇S∈P，由此構成問題的解S=S

，S

，…，S

。具體步驟如下：

步驟1 令S= oslash;，k=1。

步驟2 選擇S∈P，則：①對于起始節(jié)點：C= C，#8704;P∈P，k∈i使得S∈P為上式最小；②對于其他節(jié)點：C= C+ ω，#8704;P∈P，P∈S，（i，k）∈A使得S∈P為上式最小。

步驟3 令S= S+{S}，如果k=n，計算終止，否則令k←k+1，轉(zhuǎn)入步驟2。

4 實例分析

假設虛擬企業(yè)有4個制造子任務需要尋求合作伙伴來進行加工制造，每個子任務完成后交由下一個子任務完成，每個子任務都有若干候選企業(yè)。子任務1有P11、P12、P13共3個候選企業(yè)可供挑選，且各自的制造費用分別為2個單位、1.2個單位和1.1個單位；子任務2有P21、P22共2個候選企業(yè)可供選擇，它們的制造費用分別是1個單位和1.1個單位；子任務3有P31、P32、P33共3個候選企業(yè)，它們的制造費用分別是1個單位、1.2個單位和1.1個單位；子任務4有P41、P42共2個候選企業(yè)，它們的制造費用分別是2個單位和1.5個單位，如圖3所示，制造費用以小括號內(nèi)的數(shù)字表示，邊上的權表示兩個制造地點間的運輸費用。

按照上面介紹的方法求解制造加工地點集{S1，S2，S3，S4}。

首先，確定起始節(jié)點，在P11、P12、P13中選擇制造費用最小的節(jié)點，因C11=2，C12=1.2，C13=1.1，顯然P13的制造費用最小，因此，S1= P13。其次，確定S2。由于S2的緊前節(jié)點只有一個S1，故S2由式C2＝C2 i＋TC132 i（i＝1，2）來比較求出，C2 i為頂點P2 i的制造費用，TC132 i表示已經(jīng)選好的頂點P13到P2內(nèi)不同頂點的運輸費用。可得C21＝1＋2＝3，C22＝2＋2＝4，據(jù)此選擇P21，即S2 ＝ P21。確定S2后，S3由C3＝ C3 i＋TC213 i（i＝1，2，3）來比較求出，C3 i為C3 i的制造費用，TC213 i表示頂點P21到P3內(nèi)不同頂點的運輸費用。C31＝1＋2＝3，C32＝1．2＋3＝4．2，C33＝1．5＋4＝5．5，據(jù)此選擇P31。同理可得，C41＝2＋3＝5，C42＝1．5＋2＝3．5，據(jù)此選擇P42，即S4＝ P42。

所以，最后的結(jié)果{S1，S2，S3，S4}={P13，P21，P31，P42}，即應選擇P13、P21、P31、P42為制造伙伴。

5 結(jié) 語

由于虛擬企業(yè)大多數(shù)采用的是異地聯(lián)合設計、制造，因此，如何從成千上萬的企業(yè)中選擇最優(yōu)的合作伙伴結(jié)成聯(lián)盟，以最低的成本、最快的速度響應市場的個性化需求，這是每一個虛擬企業(yè)想要獲取成功需首先考慮的問題，合作伙伴的選擇至關重要。基于此，本文在對虛擬企業(yè)進行任務分解的基礎上，定義其制造子任務，并建立虛擬企業(yè)制造伙伴選擇的數(shù)序模型，同時給出基于Dijkstra方法的改進優(yōu)化算法。算例結(jié)果表明，該優(yōu)化算法簡單易行，用于求解虛擬企業(yè)制造伙伴選擇優(yōu)化問題具有很好的效果。

主要參考文獻

［1］ S Talluri，R C Baker． A Quantitative Framework for Designing Efficient Business Process Alliance［C］． International Conference on Engineering Management and Control（IEMC），1996：656－660．

［2］ 陳菊紅，汪應諾，孫林巖． 虛擬企業(yè)伙伴選擇過程與方法研究［J］． 系統(tǒng)工程理論與實踐，2001，21（7）：48－52．

［3］ L Mikhailov． Fuzzy Analytical Approach to Partnership Selection in Formation of Virtual Enterprises［J］． The International Journal of Management Science，2002，30（5）：393－401．

［4］ T L Saaty． The Analytic Hierarchy Process ［M］． New York：McGraw Hill，1980．

［5］ 葉飛，孫東川，張紅． 面向虛擬企業(yè)合作伙伴選擇的新過程框架結(jié)構研究［J］． 系統(tǒng)工程理論與實踐，2003（11）：88－94．

［6］ 葉永玲，周亞慶． 虛擬企業(yè)合作伙伴的優(yōu)化選擇研究［J］． 軟科學，2004，18（2）：79－82．

［7］ 錢頌迪 等． 運籌學［M］． 北京：清華大學出版社，2002．

［8］ 尚耀華，萬威武． 基于圖論的虛擬企業(yè)制造伙伴選擇優(yōu)化算法［J］． 系統(tǒng)工程學報，2006，21（4）：375－380．

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