考慮任務(wù)排序策略的艦船建造車間虛擬制造單元?jiǎng)討B(tài)調(diào)度

韓文民，孫曉梅，孔 鵬，呂 潔

(1．江蘇科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，江蘇 鎮(zhèn)江212003;2．大連船舶工業(yè)公司(集團(tuán))，遼寧 大連116001)

0 引 言

造船企業(yè)為了提高生產(chǎn)效率，縮短生產(chǎn)周期，也為了使其最終產(chǎn)品在今后使用過(guò)程中應(yīng)對(duì)技術(shù)的快速發(fā)展和提高，在加工對(duì)象的生產(chǎn)、建造方面，力圖實(shí)現(xiàn)模塊化和單元化。如發(fā)達(dá)國(guó)家艦船建造已普遍實(shí)現(xiàn)了模塊化，當(dāng)出現(xiàn)戰(zhàn)損或技術(shù)更新的時(shí)候，可以通過(guò)快速更換相應(yīng)模塊而迅速?gòu)?fù)原或提高其技術(shù)水平。但我國(guó)現(xiàn)有企業(yè)在生產(chǎn)加工中還基本采用傳統(tǒng)的工藝專業(yè)化的生產(chǎn)組織方式，或基于成組技術(shù)傳統(tǒng)的靜態(tài)生產(chǎn)單元的生產(chǎn)組織方式。這就造成了生產(chǎn)加工組織方式與加工對(duì)象要求不能很好匹配的現(xiàn)象，生產(chǎn)加工組織的較低效率難以適應(yīng)加工對(duì)象模塊化和單元化的需要，過(guò)早、過(guò)量的庫(kù)存與突擊趕工的不良生產(chǎn)狀況并存，影響了企業(yè)的生產(chǎn)效率和生產(chǎn)柔性的水平。

虛擬單元制造系統(tǒng)(Virtual Cell Manufacturing System，VCMS)［1］是單元制造模式的新發(fā)展，是近年來(lái)日益受到重視的一種先進(jìn)制造方式。在環(huán)境復(fù)雜多變，產(chǎn)品組合難以預(yù)測(cè)的情況下，它可以通過(guò)邏輯重構(gòu)，根據(jù)任務(wù)變化快速成組，共享資源，提高系統(tǒng)的柔性與效率。

艦船建造是動(dòng)態(tài)、復(fù)雜、規(guī)模龐大的系統(tǒng)，在船舶制造過(guò)程中各階段加工對(duì)象復(fù)雜性高且品種多，加工設(shè)備空間位置上常常不易移動(dòng)，關(guān)鍵資源的共享性高，容易造成混亂、利用率不高，但因其存在工藝相似性特點(diǎn)，采用虛擬制造單元生產(chǎn)組織方式，在車間層構(gòu)建單元，不改變?cè)O(shè)備的物理布局，而是邏輯上動(dòng)態(tài)重構(gòu)，來(lái)實(shí)現(xiàn)造船生產(chǎn)車間的協(xié)調(diào)調(diào)度，實(shí)時(shí)控制，可以提高系統(tǒng)的柔性和效率。其中，關(guān)鍵的問(wèn)題之一就是如何有效實(shí)施虛擬單元?jiǎng)討B(tài)調(diào)度。近年來(lái)，一些學(xué)者對(duì)單元調(diào)度方面的問(wèn)題進(jìn)行了積極地研究，Shiue和Guh［2］考慮了不確定需求下動(dòng)態(tài)生產(chǎn)單元內(nèi)的零部件調(diào)度，并運(yùn)用混合遺傳算法和人工神經(jīng)元網(wǎng)絡(luò)方法進(jìn)行求解。Gabried［3］等提出了基于TOC 思想的生產(chǎn)系統(tǒng)啟發(fā)式單元調(diào)度方法。白俊杰［4］等考慮了批量生產(chǎn)因素下的柔性作業(yè)車間多目標(biāo)優(yōu)化問(wèn)題。冷晟［5］和Kesen S.E.［6］等研究了工藝柔性和工件運(yùn)輸?shù)壬a(chǎn)因素下的虛擬單元調(diào)度問(wèn)題。Ye Hegui［7］和Aksoy［8］等考慮了虛擬制造單元調(diào)度問(wèn)題中的成本因素并采用混合算法來(lái)求解。Kesen和Güng r［9］研究了虛擬制造單元調(diào)度中的批量分割問(wèn)題。K.L.MAK，J.Ma.［10］考慮了在虛擬單元制造系統(tǒng)設(shè)計(jì)中存在多個(gè)時(shí)間階段的生產(chǎn)調(diào)度問(wèn)題。從這些研究可以看出，虛擬制造單元這一先進(jìn)組織方式應(yīng)用于生產(chǎn)制造方面已經(jīng)逐漸成為研究熱點(diǎn)問(wèn)題，虛擬單元下的調(diào)度可以優(yōu)化生產(chǎn)過(guò)程，降低生產(chǎn)成本，快速組織資源，提高市場(chǎng)響應(yīng)速度。但是目前具體研究虛擬單元?jiǎng)討B(tài)調(diào)度過(guò)程中，共享資源在各時(shí)間階段內(nèi)可能存在能力沖突或者任務(wù)重疊方面的研究還比較少，而實(shí)際生產(chǎn)中存在多個(gè)周期階段的動(dòng)態(tài)調(diào)度，虛擬單元的共享資源可能會(huì)存在沖突進(jìn)而影響調(diào)度的效率和系統(tǒng)的連續(xù)性。只有協(xié)調(diào)好共享資源的使用和生產(chǎn)能力，才能保證系統(tǒng)的連續(xù)生產(chǎn)、負(fù)荷均衡和高效產(chǎn)出。本文就是在已有研究的基礎(chǔ)上，從船舶制造系統(tǒng)調(diào)度動(dòng)態(tài)變化的角度出發(fā)，提出了基于計(jì)劃期的生產(chǎn)控制機(jī)制，為其提供了一種考慮共享資源協(xié)調(diào)和分配策略的虛擬單元?jiǎng)討B(tài)調(diào)度方法。

1 問(wèn)題描述及建模

1.1 問(wèn)題描述

基于以上背景研究和可行性分析，本文采用階段性變動(dòng)的方法將艦船制造計(jì)劃期劃分為多個(gè)時(shí)間階段，每個(gè)時(shí)間階段內(nèi)的調(diào)度模型如圖1所示。統(tǒng)一管理和分配制造單元內(nèi)的加工任務(wù)和共享資源，生成可行的調(diào)度方案。具體而言，通過(guò)檢測(cè)車間資源在各個(gè)時(shí)間階段內(nèi)的使用情況，如果出現(xiàn)任務(wù)重疊則結(jié)合調(diào)度排序策略進(jìn)行協(xié)調(diào)，同時(shí)記錄資源的使用和釋放時(shí)間階段以及資源的加工剩余能力，實(shí)現(xiàn)動(dòng)態(tài)可行的調(diào)度。最終調(diào)度結(jié)果反映的信息包括:作業(yè)的機(jī)器分配、作業(yè)在每臺(tái)機(jī)器上的開(kāi)始和完成時(shí)間、各階段的機(jī)器剩余能力及計(jì)劃期內(nèi)各任務(wù)的加工率等。

圖1 各時(shí)間階段內(nèi)的調(diào)度模型Fig.1 Scheduling model within each time period

1.2 虛擬單元?jiǎng)討B(tài)調(diào)度模型

模型中考慮艦船制造車間包含多種類型的零件作業(yè)，多種類型的機(jī)器，且同種類型的機(jī)器不只一臺(tái)，機(jī)器的最大生產(chǎn)能力已知且不變。機(jī)器在物理位置上常常是難以移動(dòng)的，機(jī)器間的距離也是已知且不變的?；炯僭O(shè):1)虛擬單元構(gòu)建已完成;2)任意時(shí)刻每臺(tái)設(shè)備只加工一項(xiàng)任務(wù);3)每項(xiàng)任務(wù)都有已知的加工路徑;4)任務(wù)在設(shè)備上一旦開(kāi)始加工則不允許中斷;5)所有調(diào)度作業(yè)在0 時(shí)刻都已經(jīng)就緒可以進(jìn)行加工;6)每項(xiàng)任務(wù)可以選擇同種類型設(shè)備的任一臺(tái)進(jìn)行加工;7)設(shè)備調(diào)整時(shí)間忽略不計(jì)。

模型符號(hào)說(shuō)明:

j 表示作業(yè)(j=1，2，…，n);

Vj表示作業(yè)j 的加工數(shù)量;

m 表示車間工作區(qū)類型(m=1，2，…，M);

rj表示作業(yè)j 的加工路線;

Oj，i表示作業(yè)j 的第i 個(gè)工序;

Kj表示作業(yè)j 的操作工序總數(shù)量;

MCm，p表示j 階段工作區(qū)i 的最大加工能力;

PH 表示計(jì)劃期;

L 表示時(shí)間階段的長(zhǎng)度;

D(rj)表示作業(yè)j 的生產(chǎn)路徑r 的總物料運(yùn)輸距離;

決策變量為:

PRj，i，m(rj)，p表示p 階段，在工藝路線r 下使用m 工作區(qū)時(shí)，作業(yè)j 的第i 個(gè)工序的加工率(加工數(shù)量);

Pj，i表示作業(yè)j 的工序i 的總批量加工時(shí)間段;

Sj，i，m(rj)，p表示作業(yè)j 的工序i 的開(kāi)始加工時(shí)間;

Fj，i，m(rj)，p表示作業(yè)j 的工序i 的完成時(shí)間;

RCm，p表示p 階段工作區(qū)m 的剩余加工能力。

1.3 模型建立

通過(guò)充分利用虛擬單元的共享資源，以設(shè)備生產(chǎn)能力為約束，依據(jù)排序調(diào)度策略，最終達(dá)到最大完工時(shí)間和總物料運(yùn)輸距離最小的目標(biāo)。則虛擬單元多階段動(dòng)態(tài)調(diào)度的非線性數(shù)學(xué)模型如下:

滿足約束:

當(dāng)Xj，i，m(rj)，p=1 時(shí)，Yj，i，m(rj)，p+t′=1。

即滿足

在模型中，式(1)表示一旦作業(yè)j 的i 操作完成，下一個(gè)操作i+1 立即開(kāi)始;式(2)保證每個(gè)階段內(nèi)作業(yè)j 的每個(gè)工序的加工率是相同的;式(3)保證所有操作的開(kāi)始時(shí)間必須在計(jì)劃的周期里;式(4)保證作業(yè)j 的操作i 可以在階段［p，p+θ］內(nèi)完成;式(5)表明每個(gè)工作區(qū)m 在階段p 的剩余加工能力，且取值是大于等于0 的;式(6)表示p 階段的工作區(qū)m的加工能力約束;式(7)表示作業(yè)α=1，β=3 的操作i 的開(kāi)始加工時(shí)間;式(8)表示作業(yè)α=1，β=3的操作i 的總批量加工時(shí)間階段;式(9)表示作業(yè)α=1，β=3 的操作i 的完成時(shí)間;式(10)保證加工率是大于等于0 的;式(11)確保決策變量是二進(jìn)制變量。

1.4 排序調(diào)度策略

考慮虛擬單元調(diào)度的動(dòng)態(tài)性特點(diǎn)，傳統(tǒng)調(diào)度規(guī)則有其一定的局限性。因此針對(duì)虛擬單元多階段動(dòng)態(tài)調(diào)度，本文考慮將時(shí)間階段與任務(wù)排序策略相結(jié)合的啟發(fā)式規(guī)則，可以在各個(gè)時(shí)間階段合理分配共享資源加工能力，避免任務(wù)重疊，同時(shí)能確定出加工任務(wù)的使用時(shí)間階段和調(diào)度次序，實(shí)現(xiàn)虛擬單元的動(dòng)態(tài)調(diào)度、高效產(chǎn)出和物流平衡。排序調(diào)度策略設(shè)計(jì)如下:

1)計(jì)算出各項(xiàng)作業(yè)的開(kāi)始加工的時(shí)間階段。

2)比較工作區(qū)每臺(tái)機(jī)器上各個(gè)操作的時(shí)間階段，如果在給定機(jī)器上加工的2 個(gè)操作的時(shí)間階段并不重疊，則這2 個(gè)操作的優(yōu)先順序可以確定;如果2 個(gè)操作的時(shí)間階段出現(xiàn)重疊，則要計(jì)算每個(gè)操作對(duì)的時(shí)間間隔以確定優(yōu)先級(jí)排序。同一機(jī)器m 上的操作(m，i)和(m，i′)之間的時(shí)間間隔，σ(m，i)→(m，i′)=dm，i′- sm，i- pm，i- pm，i′，dm，i′表示操作i′ 的交貨期，sm，i表示i 的開(kāi)始加工時(shí)間，pm，i和pm，i′分別表示操作i和i′ 的加工時(shí)間。σ(m，i)→(m，i′)可能會(huì)出現(xiàn)下面4 種情形:

情形1:如果σ(m，i)→(m，i′)≥0 而且σ(m，i′)→(m，i)＜0，則優(yōu)先級(jí)排序?yàn)?m，i)→(m，i′);

情形2:如果σ(m，i)→(m，i′)＜0 而且σ(m，i′)→(m，i)≥0，則優(yōu)先級(jí)排序?yàn)?m，i′)→(m，i);

情形3:如果σ(m，i)→(m，i′)＜0 而且σ(m，i′)→(m，i)＜0，則不成立;

情形4:如果σ(m，i)→(m，i′)≥0 而且σ(m，i′)→(m，i)≥0，則具有同樣的優(yōu)先級(jí)，每種排序均可。

3)當(dāng)出現(xiàn)情形3 時(shí)需要回溯修改條件;當(dāng)滿足情形1、2 、4 時(shí)，則加入新的操作優(yōu)先級(jí)排序，生成調(diào)度方案，再更新時(shí)間直至所有任務(wù)動(dòng)態(tài)調(diào)度完成。

2 混合算法求解

蟻群算法具有原理簡(jiǎn)單、通用性強(qiáng)、受限制約束較小等特點(diǎn)，在動(dòng)態(tài)調(diào)度中的應(yīng)用前景較好［11］。但傳統(tǒng)的蟻群算法搜索時(shí)間過(guò)長(zhǎng)且易陷入局部最優(yōu)解中。因此，本文采用改進(jìn)蟻群算法與啟發(fā)式分配規(guī)則相結(jié)合的混合算法來(lái)實(shí)現(xiàn)優(yōu)化的動(dòng)態(tài)調(diào)度求解。改進(jìn)蟻群算法中的精英策略和最大最小螞蟻算法可以加快收斂速度，增強(qiáng)更新能力，更好地找到全局最優(yōu)解?；旌纤惴ㄓ帜苓M(jìn)一步提高改進(jìn)蟻群算法的全局和局部搜索效率和質(zhì)量，達(dá)到優(yōu)勢(shì)互補(bǔ)，優(yōu)化搜索過(guò)程，混合算法流程圖如圖2所示。

步驟1:參數(shù)初始化。任務(wù)j 與任意設(shè)備mk間信息素的初始值設(shè)為τmax;Nant為螞蟻數(shù)量，Nd為迭代次數(shù)，N 為任務(wù)總數(shù)，令迭代項(xiàng)I 為1。

步驟2:任取一只螞蟻，令a=1。任務(wù)的開(kāi)始加工時(shí)間和完成時(shí)間分別對(duì)應(yīng)開(kāi)始、完成時(shí)間矩陣，螞蟻?zhàn)畛蹩蛇x的工序集合Da為所有待加工任務(wù)的第一個(gè)工序組成的集合。

圖2 混合算法流程圖Fig.2 Hybrid algorithm flow chart

1)螞蟻a 依據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇工序集合Da中任務(wù)j 的工序i 對(duì)應(yīng)的設(shè)備，螞蟻每次走完一步，其路徑上的信息素便開(kāi)始蒸發(fā)。

2)將該工序安排給所選的設(shè)備，并時(shí)時(shí)更新開(kāi)始、完成時(shí)間矩陣，并將與該任務(wù)工序的緊后工序放入Da中，替換掉該工序，令j=j+1。

3)對(duì)于集合Da中的每一個(gè)工序選擇相應(yīng)的設(shè)備，同時(shí)計(jì)算每臺(tái)機(jī)器上時(shí)間間隔，確定出操作排序，并更新已分配的工作區(qū)的剩余能力。

4)如果該工序i 為某任務(wù)的最后一個(gè)工序，則從Da中將其刪除，否則將同屬于該任務(wù)的緊后工序放入Da中，替換掉該工序i。Da中與工序i 不在同一設(shè)備上的工序，在下一次為任務(wù)j+1 選擇工序時(shí)，不需要再次計(jì)算。若j=N，轉(zhuǎn)到步驟3，否則，令j=j+1，轉(zhuǎn)步驟2 中的3)。

步驟3:若a ＜Nant，令a=a+1，轉(zhuǎn)到步驟2的1)，否則，轉(zhuǎn)到步驟4。

步驟4:比較各螞蟻的搜索路徑，采用精英螞蟻策略進(jìn)行全局信息素的更新。

步驟5:如果出現(xiàn)新的全局最優(yōu)解，則更新信息素濃度區(qū)間，同時(shí)更新τmin，τmax，否則，轉(zhuǎn)到步驟6。

步驟6:若迭代項(xiàng)I 小于Nd，令I(lǐng)=I+1，轉(zhuǎn)到步驟2，否則，結(jié)束求解。

3 案 例

為驗(yàn)證動(dòng)態(tài)調(diào)度模型的有效性，本文以某船廠舾裝車間的某班組作業(yè)數(shù)據(jù)為例進(jìn)行研究，調(diào)研數(shù)據(jù)整理如下:車間內(nèi)共享的工作區(qū)有6 類，每個(gè)工作區(qū)中的設(shè)備數(shù)量已給出，具體情況如表1所示，零件的具體加工信息如表2所示，表3 描述的是各工作區(qū)之間的運(yùn)輸距離。

表1 工作區(qū)的設(shè)備信息Tab.1 The workspace machine information

表2 各作業(yè)任務(wù)的基本加工信息Tab.2 Job processing information

表3 各工作區(qū)之間的運(yùn)輸距離矩陣(單位:m)Tab.3 Travelling distance matrix between each workspace

3.1 虛擬單元?jiǎng)討B(tài)調(diào)度的結(jié)果

本文采用改進(jìn)蟻群算法與啟發(fā)式規(guī)則，具體參數(shù)為:螞蟻的數(shù)量Nant=50，迭代次數(shù)Nd=50，信息素蒸發(fā)速率為0.1，信息素參數(shù)α=1，β=3。圖3 表示的是7 項(xiàng)作業(yè)的最終調(diào)度結(jié)果，表4給出了虛擬單元共享工作區(qū)下的作業(yè)調(diào)度時(shí)間安排。從圖3 中可知計(jì)劃期被分為30 個(gè)階段，每個(gè)階段的長(zhǎng)度設(shè)為240 min，系統(tǒng)的最大完工時(shí)間為76 h(4 560 min)，無(wú)作業(yè)延遲，所有作業(yè)的總物料運(yùn)輸距離為2 671 m，與原有制造數(shù)據(jù)相比有了很大的改進(jìn)。

表4 虛擬單元作業(yè)調(diào)度時(shí)間階段安排Tab.4 Job scheduling time arrangement of virtual cells

圖3 調(diào)度甘特圖Fig.3 Schedule gantt chart

3.2 結(jié)果分析

與原船廠舾裝作業(yè)車間相應(yīng)制造指標(biāo)進(jìn)行比較得到表5，可以看出虛擬單元系統(tǒng)的平均作業(yè)完工時(shí)間明顯短于現(xiàn)有制造車間。進(jìn)一步比較系統(tǒng)的產(chǎn)出(產(chǎn)品加工率)如表6所示，可以看出總體來(lái)說(shuō)虛擬制造系統(tǒng)的產(chǎn)出效率是顯著高于現(xiàn)有車間的，可見(jiàn)虛擬單元系統(tǒng)的資源共享和邏輯重構(gòu)特點(diǎn)能顯著地提高效率和生產(chǎn)加工率，且總的完工時(shí)間也明顯縮短。

表5 作業(yè)完工時(shí)間對(duì)比Tab.5 Completion time comparison

4 結(jié) 語(yǔ)

考慮造船企業(yè)實(shí)際生產(chǎn)環(huán)境的復(fù)雜性和動(dòng)態(tài)需求的多變性，基于計(jì)劃期的虛擬制造單元?jiǎng)討B(tài)調(diào)度控制機(jī)制的研究有著較大的理論意義和應(yīng)用價(jià)值。本文具體針對(duì)虛擬單元?jiǎng)討B(tài)調(diào)度過(guò)程中的任務(wù)資源選擇及共享資源的協(xié)調(diào)和分配問(wèn)題進(jìn)行了研究，提出了虛擬單元多階段動(dòng)態(tài)調(diào)度的數(shù)學(xué)模型，其中設(shè)計(jì)了排序調(diào)度策略，對(duì)于共享資源中存在的任務(wù)重疊問(wèn)題給予了一定的優(yōu)先級(jí)解決策略，實(shí)現(xiàn)了虛擬制造單元?jiǎng)討B(tài)調(diào)度過(guò)程中共享資源的協(xié)調(diào)和負(fù)荷的平衡。并且提出了改進(jìn)蟻群算法和啟發(fā)式規(guī)則求解。船廠應(yīng)用實(shí)例結(jié)果表明，虛擬單元?jiǎng)討B(tài)調(diào)度應(yīng)用于船舶制造系統(tǒng)可以明顯提高作業(yè)效率、系統(tǒng)產(chǎn)出并能保證共享資源的合理有效分配。未來(lái)應(yīng)根據(jù)艦船建造特點(diǎn)，進(jìn)一步開(kāi)展虛擬制造單元下周期驅(qū)動(dòng)與事件驅(qū)動(dòng)相結(jié)合的動(dòng)態(tài)調(diào)度問(wèn)題的研究與應(yīng)用。

［1］MAK K L，LAU J S K，WANG X X．A genetic scheduling methodology for virtual cellular manufacturing systems:an industrial application［J］．International Journal of Production Research，2005，43(12):2423－2450．

［2］SHIUE Y R，GUH R S．Learning-based multi-pass adaptive scheduling for a dynamic manufacturing cell environment［J］．Roboties and Computer-Integrated Manufacturing，2006，22(3):203－216．

［3］GABRIED G C，SADAMI S，TAKAO E．A proposal for the scheduling of cell manufacturing through TOC［J］．Journal of Japanese Industry Manage Associate，2007，57(6):503－510．

［4］白俊杰，龔毅光，王寧生，等．多目標(biāo)柔性作業(yè)車間分批優(yōu)化調(diào)度［J］．計(jì)算機(jī)集成制造系統(tǒng)，2010，16(2):396－403．

BAI Jun-jie，GONG Yi-guang，WANG Ning-sheng，et al．Multi-objective flexible job shop scheduling with lotsplitting［J］．Computer Integrated Manufacturing Systems，2010，16(2):396－403．

［5］LENG Sheng，WEI Xiao-bin，ZHANG Wen-yi．Improved ACO scheduling algorithm based on flexible process［J］．Transactions of Nanjing University of Aeronautics and Astronautics，2006，23(2):154－160．

［6］SAADETTIN E K，SANCHOY K D，Zülal Güngr．A genetic algorithm based heuristic for scheduling of virtual manufacturing cells(VMCs)［J］．Computers and Operations Research，2010，37(6):1148－1156．

［7］YE He-gui，LIANG Ming．Simultaneous modular product scheduling and manufacturing cell reconfiguration using a genetic algorithm［J］．Journal of Manufacturing Science and Engineering，Transactions of the ASME，2006，128(4):984－995．

［8］AKSOY，ASLIOZTURK，NURSEL．Simulated annealing approach in scheduling of virtual cellular manufacturing in the automotive industry［J］．International Journal of Vehicle Design，2010，52:82－95．

［9］KESEN，SAADETTIN E，Güng r，Zülal．How important is the batch splitting activity in scheduling of virtual manufacturing cells(VMCs)［J］．International Journal of Production Research，2011，49(6):1645－1667．

［10］MAK K L，MA J．A Novel hybrid algorithm for multi-period production scheduling of jobs in virtual cellular manufacturing systems［J］．Proceeding of the Word Congress on Engineering，2011(1):978－988．

［11］ARNAOUT J P，RABADI G，MUSA R．A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times［J］．Journal of Intelligent Manufacturing，2010，21:693－701．