錢偉偉，王有遠，張振華

(南昌航空大學 a.航空制造工程學院；b.工業(yè)工程研究所，南昌 330063)

0 引言

制造資源優(yōu)化分配是實現(xiàn)制造資源高效利用的關鍵。制造任務和資源分配的優(yōu)化可以解決多數(shù)制造企業(yè)面臨的資源閑置和資源利用率低等問題，對于企業(yè)優(yōu)化配置制造資源，提升服務質(zhì)量，降低成本具有重要意義。

近年來，圍繞制造任務和資源分配優(yōu)化的研究主要集中在：①求解資源優(yōu)化分配模型的方法研究；②服務策略研究；③資源匹配的穩(wěn)定性研究。例如：高一聰?shù)萚1]針對云制造中服務資源匹配缺少有效匹配方法的問題，提出服務資源匹配模型；Asato等[2]采用一種考慮設備功能柔性實時控制的動態(tài)資源分配方法來靈活分配資源；Zhang等[3]針對分布式制造資源的優(yōu)化配置具有多目標的特點，提出了一種改進的基于學習的優(yōu)化算法；安吉宇等[4]提出一種基于次優(yōu)服務選擇的服務系統(tǒng)運營策略來提高集群企業(yè)的資源利用率；Lin等[5]提出一種多中心結(jié)構(gòu)的制造資源和能力分配全局優(yōu)化模型來提升制造資源和能力分配效率和服務質(zhì)量；Thekinen等[6]針對資源配置方法只考慮服務需求者或服務提供者，影響匹配準確性的問題，提出了一種考慮所有代理私有偏好的匹配方法；趙道致等[7]建立制造資源的“多對多”匹配市場模型來提高資源匹配的穩(wěn)定性。以上研究為制造任務和制造資源分配奠定了基礎，但是較少關注資源優(yōu)化分配時任務與任務之間的相互影響以及資源被長期占用現(xiàn)象，存在任務分解不合理和資源利用率低等不足。

鑒于以上分析，考慮生產(chǎn)過程中任務與任務之間的相互依賴關系和資源的服務能力對于提高任務和資源分配模型的精度非常重要。因此，本文建立基于資源使用閾值的資源分配模型和基于時間有色Petri網(wǎng)的協(xié)同制造任務與資源分配模型，為制造任務和資源分配提供新的思路。

1 考慮任務間依賴關系的制造任務分解模型與步驟

1.1 基于依賴關系的任務描述

在產(chǎn)品制造過程中，各個制造任務(以下簡稱任務)間會存在一定的約束關系。因此，定義任務集 Ti= { t1，t2，…，tn} ，i = 1，2，…，n。如果 ti< tj，表示任務 tj受到任務 ti的優(yōu)先約束限制，其中“<”表示約束關系。任務的4種依賴類型如圖1所示。

(a) 線性依賴 (b)分流依賴

(c)匯合依賴 (d)混合依賴 圖1 制造任務的依賴關系

1.2 任務分解模型及步驟

在產(chǎn)品生產(chǎn)過程中，需要對任務進行細化分解，并對分解后的最小粒度任務進行合理分配，由各制造單元共同完成。同時，考慮各個制造單元的能力指標，將分解后的任務合理分配給合適的制造單元，確保任務的順利完成，任務分解模型如圖2所示。

圖2 制造任務分解模型

由圖2可知，通過匹配算法將任務與制造單元進行合理匹配，具體步驟如下：

Step 1：綜合考慮制造單元的生產(chǎn)能力，分別設定其任務的完成閾值i。

Step 2：對各個制造單元的能力指標、物流指標、裝備指標、興趣指標、客戶位置指標、負載指標等進行匹配度定義，給出綜合指標Ki=[0,1,2,3,4,5]，i={1，2，3，4，5}。

(1)

Step 4：由公式(2)計算產(chǎn)品協(xié)同制造分配的任務完成時所需求的能力閾值。

(2)

當Xi≤i時，則表示協(xié)同制造單元能夠完成所分配的生產(chǎn)任務，任務分解、分配成功。當有兩個或兩個以上符合要求的制造單元時，將生產(chǎn)任務分配給Xi與i最接近的制造單元；當Xi>i時，則表示分配的生產(chǎn)任務超出制造單元的能力范圍，轉(zhuǎn)Step 5。

Step 5：設定任務的分解粒度△i，判斷任務分解的粒度是否超過制造單元的加工范圍。如果分解粒度△i超過制造單元的能力范圍，表示可進一步分解任務，轉(zhuǎn)Step 2重新進行任務分解。

2 基于使用閾值和時間有色Petri網(wǎng)的任務與資源分配模型

2.1 基于資源使用閾值的資源分配模型

由于制造資源(以下簡稱資源)的有限性，任務間出現(xiàn)資源競爭現(xiàn)象不可避免，目前較多采用優(yōu)先級策略的方法加以解決，容易導致低優(yōu)先級任務陷入長期等待的現(xiàn)象，造成資源分配不均衡。因此，本文提出一種考慮資源使用閾值的資源分配方法，以提高資源分配的均衡性。

假設在生產(chǎn)過程中，有n個任務Ti= { t1，t2，…，tn} ，i = 1，2，…，n。共享r種資源Zj(j=1,2, …，r)，每種資源的數(shù)量為rj，規(guī)定第i個任務Ti對第j種資源Zj的使用閾值為Yij。當?shù)趖個任務Tt提交資源需求申請時，首先對資源申請量btj按照公式(3)進行判斷。

(3)

如果滿足，則表示在整個制造過程中，在對第t個任務Tt限定其對第j種資源Zj的使用閾值為Yij的情況下，當資源申請量為btj時，第j種資源Zj的剩余分配量等于或大于系統(tǒng)已經(jīng)使用的資源量時，可以滿足任務Tt的需求，將Zj分配給任務Tt。如果不滿足，則延遲給任務Tt分配資源Zj。規(guī)定：第i個任務Ti對第j種資源Zj的使用閾值為yij時，則表示任務使用該資源沒有約束限制，使用閾值為yj時，則表示全部任務對資源具有相同的使用權(quán)限。

2.2 基于時間有色Petri網(wǎng)的任務與資源分配模型

Petri網(wǎng)是一種基于狀態(tài)、面向圖形、支持并發(fā)活動的建模語言，在任務與資源分配中使用時間有色Petri網(wǎng)(Timed Colored Petri Nets，TCPN)進行建模，可有效避免構(gòu)造目標函數(shù)的繁瑣過程[8-10]。

定義：TCPN=(Σ，P，T，A，V，C，G，E，I)為一個多元組。其中：

(1)Σ為由顏色集組成的有限非空集合。

(2)P為由庫所組成的有限集合。

(3)T為由變遷組成的有限集合。

(4)A為有限弧集，且滿足

P∩T=P∩A=A∩T=?。

(5)V為變量集。?v∈V:Type[v]∈Σ。

(6)C為顏色集函數(shù)，定義為C:P→Σ。

(7)G為守衛(wèi)函數(shù)，是定義在T上的表達式，即：

?t∈T: [Type(G(t))={true,false} ∧

Type(Var(E(a)))?Σ]，

Type為類型函數(shù)，Var為變量函數(shù)。

(8)E為弧表達式函數(shù)。定義為：E:A→EXPRv，?a∈A:Type[E(A)]=C(p)MS。

(9)I為初始化函數(shù)，定義庫所中的初始標記。定義為：

I:P→EXPRΦ，?p∈P:Type[I(p)]=C(p)MS。

建立基于時間有色Petri網(wǎng)的產(chǎn)品協(xié)同制造任務與資源分配模型，如圖3所示。

圖3 基于時間有色Petri網(wǎng)的分配模型

其中變遷Xn表示為任務Tn分配的資源，變遷Yn表示任務Tn歸還的資源。為了方便資源的統(tǒng)一管理及分配，需建立一個制造資源管理庫，用于存儲所有可分配的資源。

產(chǎn)品制造過程中的資源描述為：MR=(ID，N，S，C，F(xiàn))，其中，MR表示資源，ID、N、S、C和F分別表示資源的編號、名稱、狀態(tài)、能力和特征；S={忙碌，空閑}兩種狀態(tài)，F(xiàn)={共享性，復制性，…}等特征。為了簡化模型描述，將MR描述為：

Zi=bi1×Z1+bi2×Z2+…+bim×Zm(i=1,2,…,n)。

資源分配流程：

Step 1：任務Ti向制造資源管理庫提出資源請求。

Step 2：利用基于資源使用閾值的資源分配模型判斷資源是否滿足申請需要。假如滿足，則轉(zhuǎn)Step3；否則，進入申請等待狀態(tài)，待其它任務釋放資源時，再予以分配。

Step 3：將資源組合Zi分配給任務Ti。

Step 4：任務Ti將資源使用完畢后，提出歸還申請，歸還制造資源。

以上模型，考慮了任務對資源的使用閾值，并對任務的完成時間進行了限定，避免資源的長期占用，確保資源的有序使用。通過調(diào)整資源組合，實現(xiàn)任務與資源的合理分配。

3 實例分析

以某型號單級離心壓氣機的制造為例， 為了簡化分析過程，只將整個壓氣機的制造任務分為7個子任務，分別是進氣道制造、輪盤制造、葉片制造、擴壓器制造、蝸殼制造、整體裝配和性能測試。整個制造主體可分為4個制造單元。制造資源包括：測試設備、制造設備、圖紙、文檔數(shù)據(jù)、技術資料、專業(yè)軟件等6大類資源，用Zj(j=1,2,3,4,5,6)表示。任務分解如表1所示。

表1 某型號單級離心壓氣機制造任務分解

分解后子任務之間的依賴約束關系如圖4所示。

圖4 離心壓氣機制造任務依賴約束關系

其中，T1、T2、T3、T4、T5、T6和T7分別表示制造任務進氣道、輪盤、葉片、擴壓器、蝸殼、整體裝配和性能測試。由圖4可知，任務T1、T2、T3、T4、T5、之間沒有約束關系，互不影響；T6和T7依賴前幾個任務的完成情況，受制于前階段任務。

建立基于時間有色Petri網(wǎng)的產(chǎn)品協(xié)同制造任務與資源分配模型，如圖5所示。

圖5 基于時間有色Petri網(wǎng)的分配模型

其中，所有的資源全部存儲于制造資源管理庫中，根據(jù)任務需求提供相應的資源，資源使用完成后，迅速歸還。由于篇幅所限，只對任務T3進行簡要說明，其余任務類似。設定任務T3對資源Z2的使用閾值為Y32=3，當任務T3需要調(diào)用資源Z2時，首先，需要判斷是否滿足公式(3)，即：

如果滿足，則資源管理器將資源Z2分配給任務T3，否則，進入等待狀態(tài)。表達式“Δ+”表示任務執(zhí)行所用的時間，用Tim[Ti]表示任務Ti的制造時間，以整個單級離心壓氣機的制造完成時間最短為目標，通過模型可知整個制造的耗費時間為MAX{Time[T1], Time[T2], Time[T3], Time[T4], Time[T5]} + Time[T6] +Time[T7]=80+20+24=124h。

4 結(jié)束語

本文在協(xié)同制造任務與資源分配問題的研究中，考慮任務與任務之間的相互依賴關系以及制造主體的能力指標，建立考慮資源使用閾值的資源分配模型，從全局保證資源分配的均衡性。通過建立基于時間有色 Petri 網(wǎng)的任務與資源分配模型，并對任務的完成時間進行限定。在實際應用中，將兩個模型有效結(jié)合，解決任務與資源分配中的資源競爭現(xiàn)象，確保資源分配均衡，實現(xiàn)資源的有序使用。