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

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

0 引 言

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

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

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

1 問題描述及建模

1.1 問題描述

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

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

1.2 虛擬單元動態(tài)調(diào)度模型

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

模型符號說明:

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

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

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

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

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

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

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

PH 表示計劃期;

L 表示時間階段的長度;

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

決策變量為:

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

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

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

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

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

1.3 模型建立

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

滿足約束:

當Xj，i，m(rj)，p=1 時，Yj，i，m(rj)，p+t′=1。

即滿足

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

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

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

1)計算出各項作業(yè)的開始加工的時間階段。

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

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

情形2:如果σ(m，i)→(m，i′)＜0 而且σ(m，i′)→(m，i)≥0，則優(yōu)先級排序為(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)先級，每種排序均可。

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

2 混合算法求解

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

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

步驟2:任取一只螞蟻，令a=1。任務(wù)的開始加工時間和完成時間分別對應(yīng)開始、完成時間矩陣，螞蟻最初可選的工序集合Da為所有待加工任務(wù)的第一個工序組成的集合。

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

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

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

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

4)如果該工序i 為某任務(wù)的最后一個工序，則從Da中將其刪除，否則將同屬于該任務(wù)的緊后工序放入Da中，替換掉該工序i。Da中與工序i 不在同一設(shè)備上的工序，在下一次為任務(wù)j+1 選擇工序時，不需要再次計算。若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:比較各螞蟻的搜索路徑，采用精英螞蟻策略進行全局信息素的更新。

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

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

3 案 例

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

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

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

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

3.1 虛擬單元動態(tài)調(diào)度的結(jié)果

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

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

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

3.2 結(jié)果分析

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

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

4 結(jié) 語

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