虛擬制造單元條件下考慮資源柔性的資源沖突檢測與消解

呂 潔，趙金濤，韓文民

LV Jie, ZHAO Jin-tao, HAN Wen-min

（江蘇科技大學 經濟管理學院，鎮江 212003）

0 引言

虛擬單元制造（Virtual Cellular Manufacturing，VCM）是在邏輯上對資源進行的動態配置和重置，不需在物理位置上進行重新安排[1]。VCM結合了單元式布局的調整時間高效性以及工藝化布局的路線靈活性[2]。在常規生產系統中，當完成生產計劃后，根據系統中的設備能力根據靜態調度方法進行資源平衡，從不同調度規則中選取最優調度策略，并得到最終調度結果。如果整個過程能按計劃進行，那么這是提高系統效率和設備利用率的理想辦法。但由于虛擬單元制造（VCM）環境中的復雜性、動態性和突變性，在調度的實施過程中可能出現多種突發情況并引起資源沖突問題，當在生產過程中有臨時需插入的急件或某設備發生故障時，就可能引起資源的沖突[3]。虛擬單元中通常包含柔性資源，沖突發生時的外在表現是資源的沖突，實際上是同時使用資源的某種功能造成的沖突。當資源沖突出現時，明晰沖突發生的類型，對發生的沖突進行及時識別和消解有很大的現實意義。系統效率和穩定性通常會表現出一定的矛盾[4]。在實際生產中，反復調整調度計劃會擾亂生產的實施，因此，沖突消解應兼顧效率和穩定性。

目前，一般生產條件下的資源沖突檢測與消解方法已有部分研究。喬立紅 、王超針對多級協同項目中的資源沖突問題，利用基于時間約束網絡的沖突檢測算法實現了多級協同項目中的資源沖突檢測，該算法建立了任務關系的時間約束網絡模型[5]。楊萍基于Agent協商理論，從資源最優配置的角度，論證了最優的協商策略，提出了可重復利用的不可分享型資源的沖突消解算法，但沒有說明沖突識別的機制，而且在確定任務優先級時需要設置參數，不能完全反應生產系統的真實性[6]。黃喜等提出了一種基于時間約束網的項目沖突識別方法，運用時間約束網絡對項目實施過程中的沖突展開研究，建立了項目實施網絡，并對項目沖突進行了定量分析，提出基于時間約束網的項目沖突識別算法。但沒有考慮多個資源的情況[7]。針對項目進度問題，尚志在關鍵鏈管理方法和貝葉斯網絡模型的基礎上，提出了關鍵鏈項目管理的貝葉斯網絡模型（CCPMBN） 。并給出了CCPMBN的定義，描述了模型中的節點、有向邊以及節點的條件概率分布；然后，提出了以貝葉斯網絡為基礎的關鍵鏈工序分解方法及建模方法；最后，證明了該模型在項目進度管理方面的應用前景。但沒有給出具體的沖突識別和消解方法[8]。宋海權提出了混合Petri網模型及沖突判斷的規則，然后根據規則對Petri網進行沖突檢測，并得到考慮優先級的消解方案。但沒有考慮可替代路線的情況[9]。F. Liang, Baykasoglu et al. 指出基于資源要素的能力分析在為某加工工序選擇可替代設備時更具靈活性[10,11]。Saad et al.采用資源要素法對CMSs進行重構[12]。F. Liang研究了在VCM系統中基于資源要素法的資源建模和效果分析，提高了制造系統的靈活性和適應性，但未運用于沖突消解中[13]。從上面的研究中可以看出，針對虛擬制造單元沖突檢測和消解過程中關于資源柔性、路徑柔性的考慮不足。

本文提出了以制造系統生產過程穩定性和高效率為目標的資源沖突檢測和消解機制。首先，在沖突檢測階段，將可能發生的沖突類型分為兩種：強沖突和弱沖突，根據各個工序的加工計劃將調度期劃分為若干時間段，以時間段為單位進行沖突識別；在沖突消解階段，對不同類型的沖突采取不同的消解策略，若所有時間段內不含強沖突，只需調整存在弱沖突時間段內的任務安排，無需對整個調度期重新安排，這在保證工期不發生延遲的情況下提高了生產系統的穩定性；當出現強沖突時，采用改進的遺傳算法對調度期內的所有工序進行重調度，以保證完工時間不會出現延誤或使延誤最小化。通過實例和仿真表明，本文提出的沖突識別和消解方法能夠在兼顧生產系統過程穩定的同時保持生產的高效率。

圖1 虛擬制造單元資源沖突檢測與消解模型

1 基于資源要素法的沖突檢測

定義一：多個任務在同一臺設備上存在時間重疊，則存在使用該設備資源的沖突；若在不改變計劃加工時間（如：工序ojh的計劃加工時間Ti=[ti,ti+1]）的前提下，通過更換其他設備可以消除沖突，那么該沖突為弱沖突，否則，稱之為強沖突。

根據初期調度計劃中時間節點，按先后分為若干時間段，如：Ti=[ti,ti+1]；經過分析所有時間段內設備上不同加工工序是否存在時間上的重疊，判斷存在資源沖突的時間段；然后對存在沖突的時間段進行沖突類型的識別；若存在某時間段是強沖突，那么，該調度期內的資源沖突類型為強沖突，否則為弱沖突。 其中，對調度期內的沖突類型作出判斷是資源沖突檢測的關鍵，其判斷流程如圖2所示。

圖2 資源沖突類型判別流程

1.1 基于資源要素法的設備能力分析

在資源要素（Resource Element,RE）理論中，資源要素是機械加工設備特有的能力單位，最早是用來定義機器設備的共有和獨有能力，并用來輔助車間分布式布局的一種方法[12]。把設備的切削成形模式叫做Form Generating Schema（FGS），具備一定關系的多種FGS集合叫做一個資源要素，這三者間的關系如圖3所示。

表1給出了例子闡明FGSs與設備間的關系，包括5臺機器和7個FGSs。每一列需要與所有未聚集的列相比較。在這一表格中，第1列與第4列相同。因此，F1和F4構成第一個RE，第二列與第三列相同，F2與F3聚集在一起生成第二個RE。以這種方式F5和F6構成第三個RE，最后F7表示最后一個RE。

表1 設備--FGSs矩陣

1.2 資源沖突類型的判別步驟

下面給出了某一時間段[ti,ti+1]內的資源沖突判別步驟：

步驟1：定義二：設集合A，B，C，D，如果A? C，B?C，C?D，A?B，B?A，那么稱A、B為一級集合，C、D分別為二、三級集合。

步驟2：包含資源要素ri的資源要素設備集用Mi=（mi,mj,mk,…,ml）表示，根據第二步中集合間的關系，對資源要素設備集Mi進行級別分類，并令資源要素ri的級別對應資源要素設備集Mi的級別。

步驟3：首先對一級資源要素進行檢測，根據該級別下的各資源要素需求數量，在該級別設備集下遍歷所有可能（每當對某資源要素分配某種設備時，就需要對含該設備的資源要素設備集更新，在更新后的資源要素設備集中去掉該設備），若不存在一種滿足各資源要素需求的情況，則存在強沖突，輸出強沖突并終止；否則，輸出使用該資源要素的設備分配方案并轉下一步。

步驟4：對下一級資源要素使用情況進行檢測，方法同上一步。直到完成對所有層級資源要素的檢測。

步驟5：匯總步驟3中得到的資源要素設備分配方案，得到該時間段內的可行調整方案Qj。

2 資源沖突的消解

2.1 弱沖突的消解

在調度期的所有時間段中都沒有出現強沖突，則只需對其中出現弱沖突時間段內的任務工序進行調整，在1.2節資源沖突類型的判別中，輸出了消除時間段內弱沖突的設備調整方案Qj，調度期內的弱沖突消解方案即為時間段內弱沖突的設備調整方案的集合{Qj}。

2.2 強資源沖突消解的數學模型

當存在強沖突時，需要找出未完成任務的調度方案來消除沖突。調度問題可描述為：n個工件在m臺設備上加工；每個工件包含一道或多道工序；工序順序是預先確定的；每道工序可以在至少一臺機器上加工；調度目標是確定每道工序的加工機器，以及每臺機器上各工序的加工順序和開始時間，使系統的生產總流程時間最小。

符號說明：

n：工件總數；

m：機器總數；

hj：第j工序的工序總數；

ojh：第j工件的第h道工序；

Mijh：第j工件的第h道工序在機器i上加工；

pijh：第j工件的第h道工序在機器i上的加工時間；

sjh：第j工件的第h道工序加工開始時間；

cjh：第j工件的第h道工序加工完成時間；

L：一個足夠大的數；

cmax：最大完工時間。

目標函數：

滿足以下約束條件：

其中：i=1,2,…,m; j=1,2,…,n; h=1,2,…,hj。

其中：j=1,2,…,n; h=1,2,…,hj-1。

其中：j=1,2,…,n。

其中：j=0,1,…,n；k=1,2,…,n；h=1,2,…,hj；l=1,2, …,hk；i=1,2,…,m。

其中：j=1,2,…,n；k=0,1,…,n；h=1,2,…,hj-1；l=1,2, …,hk；i=1,2,…,m。

其中：h=1,2,…,hj；j=1,2,…,n。

其中：j=0,1,…,n；h=1,2,…,hj。

式(1)和式(2)表示每一個工件的工序先后順序約束；式(3)表示工件的完工時間的約束；式(4)和式(5)表示同一時刻同一機器只能加工一道工序；式(6)表示的是機器約束，即某一時刻某一工序僅能被一臺機器加工；式(7)表示各個參數變量必須是正數。

3 改進的遺傳調度算法

遺傳算法（GA）在1975年由美國Michigan大學的John Holland教授首先提出，是一種模擬生物進化的優化算法。遺傳算法是一種通用的優化算法[14]，優化過程不受限制性條件的約束，能夠在復雜空間中進行全局優化搜索，并具有較強的魯棒性。染色體編碼過程是將問題的解用染色體的形式表示出來，是該算法的關鍵。本文采用整數編碼，可滿足調度規模變化的情況，也保證了交叉、變異時產生的是可行解，提高執行效率。

本文中的沖突消解調度過程包括兩個子問題：機器選擇和工序排序。本文結合了分段編碼易操作、易表現等特點對普通編碼方法進行改進，設計一種整數編碼（MSOS）方法。染色體由兩部分組成：機器選擇部分（MS）及工序排序部分（OS），染色體的結構如圖4所示。機器選擇部分的染色體長度為所有任務的工序數之和T0，每個基因用整數表示。按任務的工序順序排列，每個整數代表當前工序所選的機器在可選機器集合中的順序編號，而不是機器號。工序排序部分染色體長度也是T0，每個基因用任務號編碼，任務號出現的順序表示該工序工序間的先后順序。

圖4 染色體編碼

4 案例分析

AEF公司電梯產品中的核心部件是PM曳引機，該公司曳引機目前共有四個品種，每個品種根據電梯速度、載重量的不同，選配的曳引輪、制動器、電磁線圈的規格型號都不盡相同，形成了PM曳引機擁有四個品種，二十幾種型號的產品組。根據不同訂單的要求，所需生產數量和型號是不斷變化的。傳統的單元生產不能很好的應對這一情況，虛擬單元以生產任務為中心，根據生產任務的不斷變化來調整生產計劃或是生產過程中的調度方案，從而能夠及時的滿足生產要求。本文選取了PM曳引機組件的零部件加工車間中10個具有代表

單元內作業工序分別是O11-O12-O13,O21-O22-O23,O31-O32-O33，并在時間t=3時，加入了新任務O*，并有設備m1從單元中分離出去。設備信息如前表1所述，經過能力分析得出設備-資源要素矩陣（如表2所示），下面是加工任務的資源使用計劃表（如表3所示）。

表2 設備-資源要素矩陣

表3 加工任務的資源使用計劃表

根據調度計劃表4將時間劃分為t1=[1,2]，t2=[2,3], t3=[3,4]，t4=[4,5]，t5=[5,6]五個時間段。經過沖突識別后得出：t1時間內不存在資源沖突；t2時間內存在弱資源沖突，并同時得出該時間段的弱沖突消解方案：O11-r1-m1，O32-r2-m2，O22-r3-m3；在t3時間內存在強資源沖突。

因此，采用強沖突的消解策略，考慮資源柔性導致的可替代加工路線，以總完工時間最短為目標，設置種群規模為60，最大迭代次數為100，得到消除強沖突的調度方案，調度結果甘特圖如圖5所示，并與沒有考慮資源柔性的沖突消解調度策略（圖6）進行了對比，根據表4分析可知，該解調度方案有效消除了沖突縮短了總延遲時間和總流程時間，提高了系統效率，具有一定的可行性及有效性。

表4 沖突消解結果分析表

圖5 考慮資源柔性的沖突消解調度甘特圖

圖6 未考慮資源柔性的沖突消解調度甘特圖

下面通過蒙特卡洛模擬仿真，驗證弱沖突消解時對虛擬單元生產系統內調度過程穩定性的影響。假設虛擬單元某生產周期內劃分為5個時間段，強沖突與弱沖突的發生相互獨立，每個時間段內發生弱沖突和強沖突的概率都為5%，在95%的置信度下，模擬10000次后得出調度期內出現沖突的分布情況，如圖7所示，橫坐標上0表示沒有發生沖突；-1表示發生了強沖突；1、2和3分別表示在1、2和3個時間段上發生了弱沖突 ，而沒有發生強沖突。從仿真結果可以得出：沒有發生沖突的概率約為59%；發生沖突的概率約為41%，其中強沖突的概率為24%，弱沖突的概率為17%；并且在弱沖突的情況中，沖突發生的次數呈指數減少，出現的沖突次數主要是1次，還有少量的2次，幾乎沒有3次以上的情況。根據沖突發生的概率可以估計出發生弱沖突時的系統調整即僅需對局部時間段內的生產任務作出調整，約占全部時間段的22.35%。仿真結果表明本文提出的資源沖突檢測與消解方法能夠較好的應對虛擬單元制造中的不確定擾動情況，消除資源沖突并保持整個生產過程的穩定性。

圖7 沖突的概率分布

5 結論

本文針對虛擬單元制造中存在的問題，結合其生產過程的動態性、資源沖突的不可預測性、存在柔性設備等特點，提出了以制造系統生產過程穩定性和高效率為目標的資源沖突檢測和消解模型。根據不同情況采取不同的消解策略，有效的消除了出現的沖突，并在一定程度上減少由于沖突引起的全局改變，有利于應用于實際生產中。

[1] Nitesh Khilwani et al. A methodology to design virtual cellular manufacturing systems[J].Journal of Intelligent Manufacturing, 2011,22:533-544.

[2] Saadettin Erhan Kesen. A mixed integer programming formulation for scheduling of virtual manufacturing cells (VMCs)[J].Int J Adv Manuf Technol,(2010) 47:665-678.

[3] 王軍強,等.作業車間區間型多屬性瓶頸識別方法[J].計算機集成制造系統,2013,19(2):0429-0437.

[4] Wang, Shuang-Xi. Flexible job shop dynamic scheduling under different reschedule periods[J].Computer Integrated Manufacturing Systems,2014,20(10):2470-2478.

[5] 喬立紅,王超.多級協同項目執行中的資源沖突檢測與管理[J]. 北京航空航天大學學報,2008,34(11):1266-1270.

[6] 楊萍,龍正平,王桐.基于協商的Agent資源沖突消解算法研究[J].指揮控制與仿真,2011,33(1):27-30.

[7] 黃喜,于天飛.基于時間約束網絡的項目實施沖突識別算法[J]. 中國管理科學,2008,16:0197-0201.

[8] 尚志.基于貝葉斯網絡的關鍵鏈項目管理模型[J].中國空間科學技術,2011,6(3).

[9] 宋海權,郭進,李耀.基于Petri網的分布式系統沖突消解[J].計算機工程與設計,2013,34(4):1351-1355.

[10] F. Liang, R.Y.K. Fung,Z.Jiang.Modelling approach and behaviour analysis of manufacturing resources in virtual cellular manufacturing systems using resource element concept[J]. International Journal of Computer Integrated Manufacturing, 2011,24(12):1168-1182.

[11] Adil Baykasoglu, Mustafa G?ken.Capability-based distributed layout and its simulation based analyses[J].Journal of Intelligent Manufacturing,2010,21(4):471-485.

[12] Saad, S. M.et al.An integrated framework for reconfiguration of cellular manufacturing systems using virtual cells[J].Production Planning & Control,2002,13(4):381-393.

[13] F. Liang , R.Y.K. Fung,Z.Jiang.Modelling approach and behaviour analysis of manufacturing resources in virtual cellular manufacturing systems using resource element concept[J]. International Journal of Computer Integrated Manufacturing, 2011,24(12):1168-1182.

[14] 歐陽浩.用遺傳算法解決物流中的倉庫選址問題[J].制造業自動化,2014,36(1):51-64.