基于最小費用網絡流的快速擴散制造任務分配算法

摘 要：針對武器裝備快速擴散制造環境下的任務分配問題，提出了一種基于最小費用網絡流的任務分配方法。本方法以完成任務的時間及費用最少為目標，首先計算出各個零件的最大產量，其次根據零件最大產量計算出產品的最大產量；然后根據產品最大產量反算出各個零件的分配產量，針對每個步驟提出了相應的計算方法；最后，以航空發動機壓氣機機匣中的某級機匣殼體和靜子葉片為例，給出了算法驗證。實例表明，該方法在解決擴散制造任務分配上是合理的、實用的。

關鍵詞：快速擴散制造； 任務分配； 最小費用網絡流

中圖分類號：TH165文獻標志碼：A

文章編號：1001-3695(2009)06-2314-05

doi:10.3969/j.issn.1001-3695.2009.06.095

Method of task assignment based on theory of minimum cost network flow forrapid proliferating manufacturing

SU Ting-ting， MO Rong， ZHAO Yan， GAO Bo

(Key Laboratory of Contemporary Design Integrated Manufacturing Technology for Ministry of Education， Northwestern Polytechnical University， Xian 710072， China)

Abstract:

To solve the problem of task assignment in rapid proliferating manufacturing， this paper proposed the method of task assignment based on the theory of minimum cost network flow which aimed at less cost and time. Firstly， calculated the max output of each part， and secondly based on this the max output of whole product was computed， and thirdly calculated the allocated output of each part. For these three steps proposed three methods. Finally， took the aero-engine compressor shell casing and static-blisk as the calculated objects， studied a case. The fact proves that this method can efficiently solve the task assignment problem in rapid proliferating manufacturing.

Key words：rapid proliferating manufacturing(RPM); task assignment; minimum cost network flow

0 引言

快速擴散制造^[1，2]（RPM）是為提升國防動員體系的快速應變能力而提出的一種國防—民用企業的新型生產方式。RPM需要充分利用民用產品生產企業的制造能力，如何合理地分配民用產品生產企業的任務，是實現RPM的關鍵環節。

學術界在任務分配的算法問題上進行了大量研究。文獻[3]提出了在產品開發過程中任務分解的原則，給出了任務到團隊及基于均衡—適度原則的任務到團隊內各個參與人員分配的數學模型。文獻[4]結合隨機規劃機理，提出了并行設計中任務到團隊分配的分層多目標、動態模糊隨機優化數學模型，并討論了模型的求解方法。文獻[5] 結合虛擬企業總體任務的任務分解結構和任務導向特性對其利益分配的原則進行了討論；構建了基于任務分解結構的虛擬企業利益分配動態過程模型；建立了基于任務分解結構和合作對策論的虛擬企業利益分配模型，并采用對策二次規劃方法進行求解。文獻[6]提出了一種英式多議題拍賣協商協議，采用改進的有記憶模擬退火算法，有效求解single-unit組合拍賣問題，實現了多議題任務分配自動協商，并成功應用于一個后勤物資調度多智能體決策系統中的多議題任務分配。

從上述文獻可以看出，其研究重點主要集中在：a）承擔任務的物理載體是確定的，可根據每個載體的具體情況進行任務分配；b)這些算法的應用領域主要集中在任務的并行執行、任務的協同等方面。而對于本文所研究的面向RPM的任務分配問題來說，其核心問題是如何在規定時間內以最小的費用完成規定的生產任務。為此，本文提出了基于最小費用網絡流的任務分配方法。

由于軍工產品的生產準入制度非常嚴格，本文只從技術角度討論擴散制造中的任務分配問題。關于民用企業如何取得軍工產品生產資格的問題，不屬于本文討論范圍。

1 面向RPM的任務分配問題描述

RPM的生產方式中，如果需要快速擴散制造某個軍工產品Product-A，則軍工企業需要向適當的民用產品生產企業分配適當的生產任務，這就涉及到兩個方面的問題：a)民用產品生產企業的選擇問題，即依據特定的評價體系，在盡可能廣的范圍內考察民用產品生產企業，從而選擇出一些企業，其中的每個企業都可承擔Product-A的某些生產任務，稱這些企業中可以完成某一特定生產任務的制造資源構成的制造體系為邏輯制造單元（logical manufacturing cell， LMC），這些LMC便構成一個集合ALMC；b)根據Product-A的生產任務量，不一定需要ALMC中的所有企業都參與生產，而是從中選擇一些來共同完成Product-A的生產任務，被選出來的這些企業都承擔了特定任務量。限于篇幅，本文的前提是問題a)已解決，即已有了符合約束條件的LMC集合ALMC；在此基礎上重點解決問題b)，即從ALMC中應該選擇哪些LMC，被選出的這些LMC應該分配多少任務量。

零件的制造是依據工藝完成，工藝由一系列工序按順序組成，而每道工序所需要的制造資源類型不盡相同。對于從ALMC中隨機抽取的一個LMC來說，不一定完全擁有生產一個完整零件所需的所有資源，所以，必須綜合起來考慮，按照制造工藝路線將多個LMC聯合起來形成邏輯生產線（logical production line， LPL）。

基于以上所述，問題b)就轉換成了以下等價問題：在給定產品產量的約束條件下，以最短時間和最小費用完成任務為目標，如何從ALMC中挑選適當的LMC，并合理分配每個LMC的生產任務。

上述所形成的最終問題具有四個特點：

a)要求完成任務的時間最短。充分考慮LPL的生產平衡問題，既要滿足產品在單位時間內的產量最大，又要保證充分利用LMC的制造資源。

b)要求完成任務的費用最少。在生產過程中，應該盡量降低生產費用與運輸費用。

c)承擔任務的LMC不是事先確定的。需要首先從ALMC中選擇出恰當的LMC，而后才涉及到被選擇出來的這些LMC的任務分配情況。

d)不能造成資源制造能力的浪費。RPM的目的是實現武器裝備在短時間內的變批量生產。為達到這個目的，需要盡可能充分地利用民用產品生產企業的制造能力。

通過以上分析，本文采用最小費用流^[7]來解決所提出的問題。

2 面向RPM的任務分配算法

2.1 面向RPM的任務分配問題分析

如果要解決產品某個批次生產任務中LMC的任務分配問題，必須要確定LMC所服務的相應零件在這個批次生產任務中所需生產的數量，而這個數量需要與產品其他零件的生產數量綜合考慮，這就涉及到產品中各個零件之間的生產平衡問題。為解決這個問題，本文借鑒約束理論（theory of constraints， TOC）^[8]的某些思想，即任何系統至少存在著一個約束，否則它就可能有無限產出，而系統的產出就取決于這個約束。基于此，確定一個產品的產量可以這樣認為：一個產品是由多個零件裝配而成，裝配體對于不同的零件所需數量是不同的，因此，在零件之間以裝配為基準存在數量上的比例關系；整個產品的產量就是由在比例數量上最少的那個零件來決定；這個比例數量上產出少的零件就是整個產品產量的約束，本文稱之為瓶頸零件（bottlenecks part， BNP），而其他零件的產量皆由BNP的產量決定。用如下例子解釋上述內容：

假設一個產品由A、B、C三個零件裝配組成，三個零件所需要的數量分別為2、10、6個，這三個零件之間存在的裝配數量比例就是A:B:C=1:5:3。三個零件分別對應三個制造體系，如果這三個體系在單位時間內分別的產量為：A產出4個， B產出30個，C產出24個。根據三個零件的裝配數量比例關系計算：零件A為4/1=4；零件B為30/5=6；零件C為24/3=8。由此可以看出，零件A是在比例數量上最少的那個零件，即整個產品的瓶頸零件，產品只能按照零件A的產量而裝配成2件產品，因此零件B在單位時間內的最終產量為20個，零件C為12個。

依據同樣的道理，在單位時間內某個零件的產量取決于這個零件中瓶頸工序（bottlenecks step， BNS）所能完成的數量。零件的瓶頸工序指的是：承擔這道工序的制造體系在單位時間內所能完成的任務量在整個零件所有工序對應的制造體系在單位時間內完成的任務量中最小。

基于上述分析，給出面向LMC任務分配的三個定義：

定義1 零件最大產量。在單位時間內，ALMC中能夠承擔該零件加工的所有LMC合作所能完成的該零件的最大產出數量，即單位時間完成該零件BNS的最大量。

定義2 產品最大產量。在單位時間內，ALMC中的所有LMC合作所能完成的該產品的最大產出數量，即單位時間完成該產品BNP的最大數量。

定義3 零件最終產量。在單位時間內，按照產品零件裝配數量比例關系，由產品的BNP產量所決定的零件最終產量。

綜上所述，提出一種面向RPM的任務分配算法。基本步驟如下：

a)根據零件最終產量計算方法計算單位時間內每個零件的零件最大產量與產品最大產量，并計算出每個零件的零件最終產量。

b)根據確定下來的零件最終產量，將每個零件對應的所有LMC按照工藝路線劃分為幾條LPL進行并行生產。按照最小費用流算法進行計算，選擇出恰當的LMC并分配其生產任務量。

在上述算法中，需要解決兩個關鍵技術，即零件最終產量計算方法和LMC選擇與任務分配算法。

2.2 零件最終產量計算方法

根據上述原理，零件最終產量計算方法的具體步驟如下：

a）數學描述。一個產品中待加工的零件構成一個集合P={pi | i=1，2，…，α;α是正整數}。零件pi向外擴散的工序形成該零件的工序集合Si={sij| j=1，2，…，β;β是正整數}，sij表示零件pi的第j道工序。工序sij對應的LMC集合為Hij={hijl|l=1，2，…，χ;χ是正整數}，hijl表示sij對應的第l個LMC，它在單位時間內的產量為qijl 。

b）零件最大產量的計算方法。根據前面分析，零件pi的產量取決于該零件的瓶頸工序sBNSi，則pi在單位時間內的最大產量qmaxi為

qmaxi=∑χBNSk=1qiBNSk（1）

其中：χBNS為工序sBNSi對應的LMC的數量。

c）產品最大產量的計算方法。由于零件之間以裝配為基準存在數量上的比例關系，不能僅憑qmaxi來確定產品的最大產量。鑒于此，本文提出零件的數量比例因子ε，該因子的數值是其對應零件在產品中所需裝配數量的倒數。ε這樣取值的基本思想是：將零件數量映射成產品的數量，參見2.1節例子中的描述。為此，產品在單位時間內的最大產量Q為

Q=min(εi qmaxi)（2）

其中：εi為零件pi的數量比例因子。

d）零件最終產量的計算方法。根據產品最大產量，可以確定出零件pi在單位時間內的最終產量qi為

qi= Q /εi （3）

2.3求解模型

依據時間最短費用最小的原則，對LMC的選擇需要根據其不同的制造能力和彼此之間的空間位置來確定。因此，這個問題可以抽象為最小費用流問題。建立一個網絡模型：

N=(source，sink，V，E，C，F，B) （4）

其中:N為一個網絡。

Source為網絡的源點。網絡的定義^[7]規定一個網絡有且僅有一個起點，所以在本問題中每條LPL都虛設一個獨立的起點source，稱為超點。

sink為網絡的匯點，與source同樣的道理，虛擬的一個終點，亦為超點。

V為網絡中除了源點和匯點之外的節點的集合。假定節點表示LMC，則節點具有了容量與流量的屬性，而在經典網絡模型中，具有容量與流量屬性的元素只有連接弧，因此不符合經典網絡模型，這個假定不成立。為解決此問題，本文采用如下方法：將LMC用節點對表示，該節點對由一個入口節點和一個出口節點組成。每個節點對中兩個節點之間有且僅有惟一連接弧，稱為內部有向連接弧，表示物料在LMC內部的流動，此類連接弧上的費用為LMC的生產費用。每對節點中的出口節點與下一道工序中所有節點對中的入口節點間存在有向連接弧，稱為外部有向連接弧，表示不同LMC間的物料流動，此類連接弧上的費用為LMC間物料的運輸費用（詳見圖1）。根據以上所述，viikI∈V，表示邏輯制造單元hiik的入口節點；viikO∈V，表示邏輯制造單元hiik的出口節點。

E為節點之間的有向連接弧集合，表示物料的流動途徑，包括外部有向連接弧和內部有向連接弧。viikI∈V，稱所有指向viikI的有向連接弧為viikI的入弧；稱所有從viikI出發的有向連接弧為viikI的出弧。eiik-ijl表示連接viikO和vijlI的有向連接弧，是外部有向連接弧，是節點viikO的出弧，是節點vijlI的入弧。eiik-iik表示viikI和viikO的有向連接弧，是內部有向連接弧。同一工序中不同LMC對應的節點之間不存在有向連接弧。E還包含以源點為起點或者以匯點為終點的有向連接弧。有向連接弧的方向規定如下：對于內部有向連接弧，由入口節點指向出口節點為正向，反之為反向；對于外部有向連接弧，由出口節點指向入口節點為正向，反之為反向；對于與source或sink連接的有向連接弧，source的出弧方向為正向，反之為反向，sink的入弧方向為正向，反之為反向。

C表示有向連接弧上的容量函數，eiik-ijl∈E，c(eiik-ijl)表示eiik-ijl所連接的節點之間單位時間內最大物料流動量。

在經典網絡模型中，兩個節點之間物料的流動量由節點代表的企業運輸能力以及兩個企業之間的交通狀況決定，但對于快速擴散制造來說，在國防動員體系下完全可以克服上述約束因素。一個LMC在單位時間內的最大產量是確定的，即該LMC向下游節點輸送的物料量不會超過這個量；同樣，其在單位時間內該LMC所能處理的物料量也取決于這個量。基于此，任一有向連接弧eiik-ijl容量的確定方法如下：

c(eiik-ijl) = min (qiik， qijl ) （5）

F表示有向連接弧上的流量函數，eiik-ijl∈E，f(eiik-ijl)表示eiik-ijl所連接的節點之間單位時間內實際流動的物料量。

B表示有向連接弧上單位流量的費用函數，eiik-ijl∈E，b(eiik-ijl)表示eiik-ijl所連接的節點之間流動單位數量物料所需的費用。

至此，LMC選擇與任務分配的網絡模型N已經完全建立，其具體形式參見圖1。

2.4 算法描述

網絡流算法主要應用于優化網絡，解決實際網絡問題。目前廣泛采用Ford-Fulkerson法解決最大流問題，最短路徑法和對偶變量法處理最少費用問題。根據2.1節所述，本文采用對偶算法，該算法的基本原理是^[7]：在保持費用最少的前提下，逐步增加流量，直到達到規定流量為止。在計算過程中，每一步迭代均對應一個輔助有向圖D(N)。

根據上文所述建立初始網絡N(0)。在N(0)中所有有向連接弧上的流量數值均為0，因此，其對應的D(N(0))與N(0)完全相同。

步驟1 采用遞歸算法求D(N(i))從源點source到匯點sink的最少費用通路。首先定義k表示遞歸的層次，g表示第k層遞歸中目前處理的弧的編號，ekg表示第k層遞歸中的第g條弧，vk表示第k層遞歸中遍歷起始節點，c(ekg)表示第k層遞歸中的第g條弧的容量，cost表示費用寄存變量，costListi是以cost為元素的鏈表。

a）設初始值k=0，v0=source，cost=0.0。

b）輸入遍歷起始節點vk和費用寄存變量cost。

c）獲取vk的所有出弧，設g=0。

d）獲取ekg，以ekg為入弧的節點vg，判斷vg是否為匯點sink。如果vg是匯點則執行步驟e）；如果vg不是匯點則執行f)；

e）判斷所有的有向連接弧是否遍歷完畢，如果遍歷完畢則執行步驟j）；如果未遍歷完畢則執行步驟g)。

f）判斷vg是否被遍歷過，被遍歷過則執行步驟h）;如果沒有被遍歷過則執行步驟i)。

g）將cost記錄在鏈表costListi中，回溯到上一層嵌套k=k-1，令g=g+1，返回步驟d)。

h）令g=g+1，返回步驟d）。

i）獲取c(ekg)與ekg的代號，令cost=cost+c(ekg)，進入下一層嵌套k=k+1，返回步驟b）。

j）找出costListi中費用數值最小的節點，該節點中記錄的有向連接弧及其相關節點組成的有向路即為D(N(i))中從source到sink的費用最小路徑。如果圖D(N(i))中已無最小費用路徑，則搜索結束，其所對應的N(i)即為最終結果。

步驟2 由D(N(i))生成N(i+1)。在費用最小路徑中，ARCi表示有向連接弧從source的出弧至sink的入弧形成的有序集合，c(arcj)表示弧arcj的容量，f(arcj)表示弧arcj的流量，j表示循環控制變量。

a）輸入D(N(i))，設j=1，Δ=carc0－farc0。

 b）取arcj屬于ARCi，Δj=carcj－farcj。

c）判斷Δ<Δj是否成立，如果Δ<Δj執行下一步；如果Δ>Δj則令Δ=Δj，然后執行下一步。

d）令j=j+1。

e）判斷ARCi中的元素是否遍歷完，如果遍歷完則執行下一步；如果沒有遍歷完則執行步驟b）。

f）根據最終的Δ計算ARCi中各個弧的流量，其他有向連接弧上的流量不變，形成N(i+1)。

步驟3 由D(N(i))與N(i+1)生成D(N(i+1))。經過步驟b)后，集合ARCi中對應的各個有向連接弧上的流量已經改變，從而形成了新集合ARCi+1。以D(N(i))為基礎，修改該圖中ARCi+1所涉及到的有向連接弧的相關信息，從而生成D(N(i+1))，b(arck)表示弧arck的費用。

a）輸入D(N(i))與ARCi+1，設k=0；

b）取D(N(i))中與arck對應的有向連接弧arck(D)，取arck 屬于ARCi+1。

c）令

c(arck(D))=c(arck)

f(arck(D))=f(arck)

b(arck(D))=b(arck)

d）判斷f(arck(D))是否等于c(arck(D))，如果等于則執行步驟e）；如果不等于則執行j）。

e）判斷arck(D)是否為與source或sink連接的有向弧，如果不是則執行步驟f）；如果是則執行g）。

f）建立或修改其反向弧-arck(D)，令

c(－arck(D))=c(arck(D))

f(－arck(D))=0

b(－arck(D))=－b(arck(D))

g）剔除arck(D)。

h）判斷ARCi+1是否遍歷完，如果遍歷完，本次修改的D(N(i)) 轉換為D(N(i+1))；如果沒有遍歷完則執行下一步。

i）令k=k+1，返回b）。

j）判斷arck(D)是否為反向弧，如果不是則執行步驟k）；如果是則執行l）。

k）建立或修改其反向弧-arck(D)，令

c(－arck(D))=f(arck(D))

f(-arck(D))=0

b(-arck(D))=－b(arck(D))

l）判斷c(arck(D))是否等于c(-arck(D))?如果等于，剔除其反向弧-arck(D)，返回h）；如果不等于修改其反向弧-arck(D)的流量，令

f(－arck(D))=c(arck(D))

返回h）。

以D(N(i+1))為新一次迭代的遍歷對象，返回步驟1。

通過以上三個步驟，可以同時完成LMC的選擇與任務分配兩項內容。

3 算法例證

以航空發動機壓氣機機匣中的某級機匣殼體和靜子葉片組合為例闡述本文提出的方法。由于機匣殼體和靜子葉片實際生產中的工藝步驟較多，限于篇幅，本文只以兩個零件的典型工藝步驟為例進行說明。本例中所采用的數據是將實際數據處理后形成的。其步驟如下：

a）構建初始網絡圖。根據式（4）構建圖1和2，有向連接弧上的數值依次為容量、流量、費用，圖中viiiI和viiiO分別為邏輯制造單元hiii的入口和出口節點。



b)計算零件最大產量。根據圖1分析得出，機匣殼體的瓶頸工序為s13，根據式（1）算出p1的最大產量 qmax1=9。同理，葉片的瓶頸工序為s23， qmax2=1 030。



c)計算產品最大產量。由表1知零件p1、p2的數量比例因子ε1=1，ε2=1/108，根據式（2）計算出產品最大產量Q=9，零件p1為產品的BNP。

d)計算零件最終產量。產品中BNP對應的LMC的最大產量與零件分配產量一致，根據式（3）計算出零件p2分配到的產量q2 =972。

e)LMC選擇及任務分配。根據圖1按照任務分配算法進行計算，在規定時間內以最小費用生產九個機匣殼體的承制LMC與其任務分配情況如圖3所示。各個LMC根據連接弧的方向，形成了5條并行運行的LPL，弧上的數字表示其所指向的LMC所承擔的任務量。

同理，根據圖2按照任務分配算法進行計算，在規定時間內以最小費用生產972個葉片的承制LMC及其任務分配情況如圖4所示。各個LMC根據連接弧的方向，形成了14條并行運行的LPL，弧上的數字表示其所指向的LMC所承擔的任務量。

4 結束語

本文利用最小費用網絡流算法在求解動態流問題方面的優勢，將其應用于解決快速擴散制造中的邏輯制造單元選擇與任務分配問題；分析了面向快速擴散制造的任務分配問題，提出了以最小費用流為基礎的任務分配算法，詳細闡述了算法的求解模型與求解步驟，并以機匣殼體與葉片為例給出了算法的實例驗證。該算法已成功應用于筆者參與開發的“武器裝備快速擴散制造系統”中。

參考文獻：

[1]房亞東.支持快速擴散制造的制造資源配置技術研究[D]. 西安:西北工業大學， 2006.

[2]俞烽，廖文和，郭宇，等. 工藝快速擴散系統的研究[J].中國機械工程，2007，18(19):2322-2325.

[3]楊波，黃克正，孫紅衛.面向并行工程的任務分配與規劃[J].計算機集成制造系統， 2002，8(7):542-545.

[4]任東鋒，豐樹謙，李體紅，等.并行設計中任務動態分配問題的研究[J].計算機工程與應用，2004，40(32):5-7.

[5]胡欣悅.基于任務分解結構的虛擬企業利益分配機制[J].計算機集成制造系統， 2007，13(11):2211-2216.

[6]胡晶晶，曹元大，胡軍.基于英式拍賣協商協議的多智能體任務分配[J].計算機集成制造系統，2006，12(5):795-799.

[7]殷劍宏，吳開亞.圖論及其算法[M]. 合肥:中國科技大學出版社，2003.

[8]王麗亞，陳友玲，馬漢武，等.生產計劃與控制[M].北京:清華大學出版社，2007.