呂 潔，趙金濤，韓文民

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

（江蘇科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，鎮(zhèn)江 212003）

0 引言

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

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

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

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

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

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

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

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

1.1 基于資源要素法的設(shè)備能力分析

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

表1給出了例子闡明FGSs與設(shè)備間的關(guān)系，包括5臺機(jī)器和7個(gè)FGSs。每一列需要與所有未聚集的列相比較。在這一表格中，第1列與第4列相同。因此，F(xiàn)1和F4構(gòu)成第一個(gè)RE，第二列與第三列相同，F(xiàn)2與F3聚集在一起生成第二個(gè)RE。以這種方式F5和F6構(gòu)成第三個(gè)RE，最后F7表示最后一個(gè)RE。

表1 設(shè)備--FGSs矩陣

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

下面給出了某一時(shí)間段[ti,ti+1]內(nèi)的資源沖突判別步驟：

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

步驟2：包含資源要素ri的資源要素設(shè)備集用Mi=（mi,mj,mk,…,ml）表示，根據(jù)第二步中集合間的關(guān)系，對資源要素設(shè)備集Mi進(jìn)行級別分類，并令資源要素ri的級別對應(yīng)資源要素設(shè)備集Mi的級別。

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

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

步驟5：匯總步驟3中得到的資源要素設(shè)備分配方案，得到該時(shí)間段內(nèi)的可行調(diào)整方案Qj。

2 資源沖突的消解

2.1 弱沖突的消解

在調(diào)度期的所有時(shí)間段中都沒有出現(xiàn)強(qiáng)沖突，則只需對其中出現(xiàn)弱沖突時(shí)間段內(nèi)的任務(wù)工序進(jìn)行調(diào)整，在1.2節(jié)資源沖突類型的判別中，輸出了消除時(shí)間段內(nèi)弱沖突的設(shè)備調(diào)整方案Qj，調(diào)度期內(nèi)的弱沖突消解方案即為時(shí)間段內(nèi)弱沖突的設(shè)備調(diào)整方案的集合{Qj}。

2.2 強(qiáng)資源沖突消解的數(shù)學(xué)模型

當(dāng)存在強(qiáng)沖突時(shí)，需要找出未完成任務(wù)的調(diào)度方案來消除沖突。調(diào)度問題可描述為：n個(gè)工件在m臺設(shè)備上加工；每個(gè)工件包含一道或多道工序；工序順序是預(yù)先確定的；每道工序可以在至少一臺機(jī)器上加工；調(diào)度目標(biāo)是確定每道工序的加工機(jī)器，以及每臺機(jī)器上各工序的加工順序和開始時(shí)間，使系統(tǒng)的生產(chǎn)總流程時(shí)間最小。

符號說明：

n：工件總數(shù)；

m：機(jī)器總數(shù)；

hj：第j工序的工序總數(shù)；

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

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

pijh：第j工件的第h道工序在機(jī)器i上的加工時(shí)間；

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

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

L：一個(gè)足夠大的數(shù)；

cmax：最大完工時(shí)間。

目標(biāo)函數(shù)：

滿足以下約束條件：

其中：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)表示每一個(gè)工件的工序先后順序約束；式(3)表示工件的完工時(shí)間的約束；式(4)和式(5)表示同一時(shí)刻同一機(jī)器只能加工一道工序；式(6)表示的是機(jī)器約束，即某一時(shí)刻某一工序僅能被一臺機(jī)器加工；式(7)表示各個(gè)參數(shù)變量必須是正數(shù)。

3 改進(jìn)的遺傳調(diào)度算法

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

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

圖4 染色體編碼

4 案例分析

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

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

表2 設(shè)備-資源要素矩陣

表3 加工任務(wù)的資源使用計(jì)劃表

根據(jù)調(diào)度計(jì)劃表4將時(shí)間劃分為t1=[1,2]，t2=[2,3], t3=[3,4]，t4=[4,5]，t5=[5,6]五個(gè)時(shí)間段。經(jīng)過沖突識別后得出：t1時(shí)間內(nèi)不存在資源沖突；t2時(shí)間內(nèi)存在弱資源沖突，并同時(shí)得出該時(shí)間段的弱沖突消解方案：O11-r1-m1，O32-r2-m2，O22-r3-m3；在t3時(shí)間內(nèi)存在強(qiáng)資源沖突。

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

表4 沖突消解結(jié)果分析表

圖5 考慮資源柔性的沖突消解調(diào)度甘特圖

圖6 未考慮資源柔性的沖突消解調(diào)度甘特圖

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

圖7 沖突的概率分布

5 結(jié)論

本文針對虛擬單元制造中存在的問題，結(jié)合其生產(chǎn)過程的動態(tài)性、資源沖突的不可預(yù)測性、存在柔性設(shè)備等特點(diǎn)，提出了以制造系統(tǒng)生產(chǎn)過程穩(wěn)定性和高效率為目標(biāo)的資源沖突檢測和消解模型。根據(jù)不同情況采取不同的消解策略，有效的消除了出現(xiàn)的沖突，并在一定程度上減少由于沖突引起的全局改變，有利于應(yīng)用于實(shí)際生產(chǎn)中。

[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] 王軍強(qiáng),等.作業(yè)車間區(qū)間型多屬性瓶頸識別方法[J].計(jì)算機(jī)集成制造系統(tǒng),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] 喬立紅,王超.多級協(xié)同項(xiàng)目執(zhí)行中的資源沖突檢測與管理[J]. 北京航空航天大學(xué)學(xué)報(bào),2008,34(11):1266-1270.

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

[7] 黃喜,于天飛.基于時(shí)間約束網(wǎng)絡(luò)的項(xiàng)目實(shí)施沖突識別算法[J]. 中國管理科學(xué),2008,16:0197-0201.

[8] 尚志.基于貝葉斯網(wǎng)絡(luò)的關(guān)鍵鏈項(xiàng)目管理模型[J].中國空間科學(xué)技術(shù),2011,6(3).

[9] 宋海權(quán),郭進(jìn),李耀.基于Petri網(wǎng)的分布式系統(tǒng)沖突消解[J].計(jì)算機(jī)工程與設(shè)計(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].制造業(yè)自動化,2014,36(1):51-64.