基于批量分割的虛擬單元制造系統(tǒng)多階段動態(tài)調(diào)度

呂 潔，王 潔

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

虛擬單元制造系統(tǒng)(virtual cell manufacturing system，VCMS)［1］是單元制造模式的新發(fā)展，是近年來發(fā)達國家得到日益重視的一種先進制造方式.批量分割是虛擬單元管理活動中必須考慮的關(guān)鍵元素，是指將大的生產(chǎn)批量分割為小的子批量，使得同一產(chǎn)品的各工序在連續(xù)的加工中心上產(chǎn)生重疊(橫向分割)，從而加快產(chǎn)品加工的進程，減少完工時間和在制品庫存.它已經(jīng)廣泛用于減少流水車間和作業(yè)車間的完工時間.目前國內(nèi)外已經(jīng)存在一些關(guān)于批量分割的研究，文獻［2］中研究了混流生產(chǎn)條件下批量和提前期聯(lián)合確定問題，但仍缺乏對于虛擬單元下的批量分割的研究，而且關(guān)于大型復雜單件型企業(yè)的虛擬單元內(nèi)設(shè)備“一專多能”且同類設(shè)備有多臺這一問題所引起的批量分割研究不多.因此，文中針對虛擬單元下批量分割的特點研究設(shè)備“一專多能”及存在相同設(shè)備的批量分割調(diào)度問題.文獻［3-4］中研究了考慮批量分割的單元制造系統(tǒng)設(shè)計問題.還有一些學者對批量分割下的生產(chǎn)計劃［5］、成組布局設(shè)計［6］以及多目標優(yōu)化［7-8］進行了研究，文獻［9］和［10］中分別強調(diào)了VC 下批量分割的重要性和轉(zhuǎn)移批量的效果.另外，對于解決批量分割的啟發(fā)式算法需要進一步改進.一些文獻提出的算法可以解決調(diào)度問題［11-12］，但是部分存在計算時間過長，不利于解決大規(guī)模問題等缺陷.

由于多數(shù)研究都假設(shè)虛擬單元調(diào)度過程中不允許批量分割，因為批量分割的加入在很大程度上增加了調(diào)度的難度，而帶批量分割的調(diào)度問題在實際的虛擬單元調(diào)度過程中普遍存在.因此，為了解決這一問題，文中將一階段擴展為多階段，提出了一個多階段虛擬單元動態(tài)調(diào)度數(shù)學模型，來解決虛擬單元批量分割調(diào)度問題，并體現(xiàn)出批量分割帶來的降低成本的特點.所討論的批量分割還包含在具有同種功能的機器上同時進行分割(縱向分割)，考慮運輸距離并確定設(shè)備上的批量種類、大小和順序，最終達到總生產(chǎn)成本最小化的目標，其中總生產(chǎn)成本包括庫存成本、運輸成本和加工成本.

1 批量分割多階段動態(tài)調(diào)度模型

1.1 問題描述

模型中包含多個階段，多種類型的零件，多種類型設(shè)備，同種類型的設(shè)備可能不止一臺，設(shè)備的最大生產(chǎn)能力已知，并且在整個計劃期內(nèi)是不變的.每種類型的零件都有多條工藝路線進行選擇，設(shè)備在物理位置上是不移動的，并且機器間的距離是已知的.該模型考慮了虛擬單元設(shè)備負荷的均衡，資源利用情況，調(diào)整準備時間等因素來決定設(shè)備批量大小.模型中共包含 U 個工作區(qū)(u=1，2，3，…，U)，將一個計劃期分為P個階段(p=1，2，3，…，P)，可能存在 b個子批(b=1，2，3，…，B).

1.2 目標函數(shù)

文中針對生產(chǎn)車間的需要，將最小生產(chǎn)成本作為最終目標，其中包含運輸成本、庫存成本和加工成本.

式(1)為各階段作業(yè)j的庫存量;式(2)為生產(chǎn)路線的運輸距離的計算公式;N為作業(yè)j的總數(shù)量;Cj為單位距離單位作業(yè)j的移動成本;Vj，p為p階段作業(yè)j的客戶需求量;D(rj，p)為加工路線 rj，p的總距離;Ij，p為p階段作業(yè)j的庫存成本;Au為單位時間工作區(qū)u的加工成本;Kj為作業(yè) j的總工序數(shù)量;Yj，i，u(rj，p)，p=1表示如果p階段在u工作區(qū)rj，p路線下作業(yè)j的加工工序 i已經(jīng)在加工，否則為 0.PRj，i，u(rj，p)，p表示 p 階段在u工作區(qū)rj，p路線下作業(yè)j的加工工序i的加工率;ptj，i，u(rj，p)為在工作區(qū) u(rj，p)生產(chǎn)一個單位作業(yè) j的工序i的加工時間;Ej，p為p階段作業(yè)j的子批量大小;DDj，p為 p 階段作業(yè) j的截止日期;u(rj，p)為 p 階段作業(yè)j的加工路線所使用的工作區(qū)u;du1，u2為兩個工作區(qū)之間的距離.

1.3 約束條件

約束(3)表示當作業(yè)j的工序i完成之后，作業(yè)j的工序i+1立即開始加工;約束(4)表示同一作業(yè)的后一個工序的加工率等于前一個工序的加工率;約束(5)表示所有作業(yè)的開始時間都在計劃期內(nèi);約束(6)表示保證批量分割后作業(yè)的所有子程序的批量大小和等于該作業(yè)最初的批量大小;約束(7)表示加工率大于等于0;約束(8)表示p階段工作區(qū)u的剩余能力;約束(9)和(10)表示加工的開始時間和結(jié)束時間;約束(11)表示所有作業(yè)都要在交貨截止日期前完成;約束(12)表示所有作業(yè)被分配到到設(shè)備上可以按時完成;約束(13)表示在計劃期初任何作業(yè)沒有庫存;約束(14)表示模型中各變量都是二進制的.

式中:PL為一個階段的長度;H為計劃期;rj，p為p 階段工作 j的加工路線;Oj，i為作業(yè) j的工序 i;MCu，p為p階段工作區(qū)u的最大生產(chǎn)能力;D(rj，p)為加工路線 rj，p的總距離;Qj，i，u(rj，p)，b為工作區(qū) u(rj，p)生產(chǎn)單位作業(yè)j的工序i的第b個子批的調(diào)整時間;RCu(rj，p)，p表 示 p 階 段 工 作 區(qū) u 的 剩 余 能 力;stj，i，u(rj，p)，p，b表示 p 階段在 u 工作區(qū) rj，p路線下作業(yè) j的加工工序 i的第 b 子批的開始時間;ftj，i，u(rj，p)，p表示p階段在u工作區(qū)rj，p路線下作業(yè)j的加工工序i的結(jié)束時間;Xj，i，u(rj，p)，p=1 表示如果 p 階段在 u 工作區(qū)rj，p路線下作業(yè)j的加工工序i開始加工.否則為0.

2 混合優(yōu)化算法

2.1 約束規(guī)劃

約束規(guī)劃是解決約束滿足問題的有效方法.約束滿足問題通常包含多個變量和變量值域.它的基本操作是一次挑選一個變量，并且在其值域中選出一個值，確保其與目前已有的解相兼容.如果這個解不滿足約束則用新的解來替代它，如果沒有可以使用的不違反任何約束的解，那就回溯到最近的已有變量，不斷重復直至所有可行解都找到或所有可能的結(jié)合都考慮過.

2.2 離散粒子群算法

粒子群優(yōu)化算法基本思想是通過共享種群內(nèi)個體之間的信息對最優(yōu)解或近似最優(yōu)解進行定位［13］.種群指搜索空間內(nèi)一組粒子，每個粒子代表一個可行解，穿梭于超空間內(nèi)，并且有對自己最佳位置和對全局及臨近解最佳位置記憶的能力.種群內(nèi)的粒子相互交換信息并按下面的公式調(diào)整自己最佳的位置和速度.

式中:Xi表示粒子i的位置，Vi表示粒子的速度，Pi是i之前訪問過的最佳位置.G是全局的最佳位置，ω是控制之前速度對當前情況影響的慣性權(quán)重，通常隨著搜索區(qū)域的減小而動態(tài)降低.

式中:ωmax和ωmin分別為慣性權(quán)重的最大值和最小值，tmax為最大重復次數(shù).

在現(xiàn)實情況中，許多優(yōu)化問題例如生產(chǎn)調(diào)度問題的空間集是離散的或性質(zhì)上分散的.為了滿足這一要求，便提出了離散粒子群優(yōu)化算法.首先種群是由二進制變量構(gòu)成的.其次，速度轉(zhuǎn)變?yōu)楦怕首兓?，表示變量取值?的機會.這一轉(zhuǎn)化通過以下公式完成:s(Vi)表示相應位取值為1的可能性.

2.3 混合算法

1)初始化

初始化粒子規(guī)模為K，最大重復次數(shù)tmax;隨機初始化各個粒子的位置，和速度;評價每個粒子的目標值，初始化和

2)過程反復

while(t≤tmax)

for k=1 to K

更新粒子k的速度

for p=1 to P

更新p階段粒子k的調(diào)度順序

while p階段的生產(chǎn)調(diào)度不為空

在生產(chǎn)順序中挑選第一個工作j

更新工作j所在工作區(qū)的任務(wù)

Check一致性

while(不一致)

檢測關(guān)鍵設(shè)備并添加到?jīng)_突集

if關(guān)鍵設(shè)備有可替代資源

換一項新任務(wù)

Check一致性

else隨機分配一個合適的機器

設(shè)置一致性

endwhile

計算p階段工作j的產(chǎn)出及數(shù)量大小

從生產(chǎn)調(diào)度中檢測該工作

endwhile

endfor

endfor

重復計數(shù)t=t+1

endwhile

3)從種群中找出目標值最好的解和相應的目標值

如果一項工作不能在截止日期前完成，或在用完上一階段的額外能力后還是不能滿足需求，那么會按不一致處理，并且檢測出關(guān)鍵機器重新分配任務(wù)，約束規(guī)劃在此處是單層回溯.當出現(xiàn)不一致時，該算法會檢測出關(guān)鍵資源并檢查該資源是否有替代資源.如果有，將會分配替代資源的單元來完成該工序.否則該算法不回溯，且在不考慮一致性的情況下用離散粒子群算法隨機分配一個合適的工作區(qū)，接著調(diào)度下一工作，直至所有的工作都完成.

3 案例

3.1 問題及參數(shù)

為驗證模型的有效性及算法的優(yōu)越性，文中以中國內(nèi)地某船廠舾裝作業(yè)為例進行研究.文中選取了該工廠10個比較典型的管子加工作業(yè)和6類典型的工作區(qū)為例來進行應用分析，驗證文中建立的模型效果.工作區(qū)信息如表1，各工藝的加工工藝信息如表2，表3描述的是各機器間的運輸距離.

混合算法中用到的參數(shù)值如下:粒子規(guī)模為100;循環(huán)最大次數(shù)為100;最大慣性權(quán)重為0.8;最小慣性權(quán)重為0.2;c1和c2都等于2;粒子速度范圍為［-4，4］;每周期包含32個階段，每階段時間是300min;每個作業(yè)需要3～5個工序;每周期生產(chǎn)作業(yè)的數(shù)量隨機生成［50，80］.

表1 工作區(qū)信息Table 1 Workspace information

表2 各作業(yè)的加工工藝信息Table 2 Processing information of jobs

表3 工作區(qū)間的運輸距離信息Table 3 Transport distance information of workspace m

表4給出了測試問題的方案.表中，(p，n，d，m)表示參數(shù)集.p為周期數(shù)，n為各周期作業(yè)數(shù)，d為截止日期，m為工作區(qū)數(shù)量.例如，方案1表示有5個周期，該周期的作業(yè)數(shù)在［5，10］中隨機產(chǎn)生，截止日期在［αp，βp］中隨機產(chǎn)生，其中 α =0.4，β =0.7，工作區(qū)為12個.

表4 方案參數(shù)列表Table 4 List of scheme parameter

每個方案隨機產(chǎn)生5個問題，每個問題運行5次，從均值來比較混合算法和單獨的離散粒子群算法的績效.兩種方法循環(huán)100次后，比較其成本差異和時間差異，計算方法如式(18)和(19).

3.2 批量調(diào)度結(jié)果及分析

文中使用混合算法在Matlab軟件中對上述模型進行了計算.圖1給出了10項作業(yè)的批量調(diào)度信息.然后，將混合算法和離散粒子群算法對表4中的10項方案進行測試，得到最終目標成本及計算時間的比較，體現(xiàn)了混合算法及批量模型的優(yōu)越性.

從圖1可以看出，一個周期被分為32個階段，每個階段的時間長度為300 min，系統(tǒng)的最大完工時間為150h，而10個作業(yè)均是在交貨周期160h內(nèi)完成，無作業(yè)延遲.在子批量調(diào)度的過程中一個子批量可能需要多個階段來完成，但是在每個階段都進行調(diào)度的檢測，以滿足設(shè)備的充分利用.其中作業(yè)5，7，8被分割為子批，在不同的加工路線下進行生產(chǎn).作業(yè)5的加工批量為25，路線A1-B3-C7-F12-D10上的加工批量為17，路線A1-B3-C7-F12-D9上的加工批量為8.作業(yè)7加工批量為60，路線B3-C7-D9的加工批量為45，在同一工作區(qū)的另一設(shè)備上的加工批量為15.作業(yè)8加工批量為48，將其分為了兩個相等的批量，路線A1-B3-C7-D9的加工批量為24，相同工作區(qū)的另一設(shè)備上的加工批量也為24.

圖1 最終調(diào)度信息Fig.1 Final scheduling information

從此調(diào)度信息可以看出，在虛擬單元中進行批量分割可以縮短完工時間.在確定子批量的大小時要考慮設(shè)備的資源利用狀況、調(diào)整時間和成本等因素，并且在調(diào)度的過程中需要不斷的檢驗調(diào)度現(xiàn)狀，在各個不同的階段，對剩余資源進行重調(diào)度，從而提高設(shè)備的利用率.

表5為兩種算法循環(huán)100次后的比較結(jié)果，與單純的DPSO相比，混合算法能給出更好的解.對于相同的問題，混合算法所消耗的成本更少，但是所消耗的計算時間較長，因此進一步比較了在相同時間長度的情況下兩種算法的績效.比較結(jié)果如表6，其中Tops表示的是循環(huán)100次離散粒子群算法的計算時間.從調(diào)度結(jié)果可以看出，與單純的離散粒子群算法相比，約束規(guī)劃和離散粒子群算法的混合算法在求解模型時能給出更好的解.當問題的規(guī)模擴大時，或是截止日期更近時，這一混合算法的優(yōu)越性更加明顯.

表5 離散粒子群算法與混合算法計算結(jié)果比較Table 5 Comparison of DPSO and hybrid algorithm

表6 兩算法在相同計算時間下的成本差異Table 6 Cost difference of the two algorithms under thesame computing time

4 結(jié)論

文中主要討論了制造系統(tǒng)內(nèi)的設(shè)備“一專多能”，同類設(shè)備不止一臺情況下的虛擬單元批量分割調(diào)度問題.由于批量分割調(diào)度的復雜性，文中構(gòu)建了一個多階段動態(tài)調(diào)度數(shù)學模型，根據(jù)當前系統(tǒng)的生產(chǎn)狀態(tài)對作業(yè)進行排序，計算總生產(chǎn)成本，彌補了現(xiàn)有文獻對虛擬單元內(nèi)批量分割調(diào)度模型研究的不足.

案例研究結(jié)果表明，該調(diào)度模型能夠在完工時間內(nèi)完成作業(yè)調(diào)度，縮短了完工時間，并且通過對比體現(xiàn)了其成本優(yōu)勢.另外，由于虛擬單元下的批量調(diào)度更符合實際，說明在虛擬單元條件下討論批量分割的調(diào)度問題是十分必要的.

在實際生產(chǎn)中，含有瓶頸的虛擬單元批量分割調(diào)度也可能發(fā)生，可以進一步研究相關(guān)啟發(fā)式算法的優(yōu)化，從而得到更好的調(diào)度模型.

References)

［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］ 韓文民，葉濤鋒.混流條件下基于TOC制定生產(chǎn)作業(yè)計劃的關(guān)鍵問題:研究現(xiàn)狀及發(fā)展探討［J］.江蘇科技大學學報:自然科學版，2005，19(6):92-96.Han Wenmin，Ye Taofeng.Critical problems on determining production scheduling for hybrid flow shop based on TOC:a survey［J］.Journal of Jiangsu University of Science and Technology:Natural Science Edition，2005，19(6):92-96.(in Chinese)

［3］ Lockwood W T，Mahmoodi F，Ruben R A，et al.Scheduling unbalanced cellular manufacturing systems with lot splitting［J］.International Journal of Production Research，2000，38:951 -965.

［4］ Defersha F M，Chen M.A comprehensive mathematical model for the design of cellular manufacturing systems［J］.International Journal of Production Economics，2006，103:767 -83.

［5］ Ahkioon S，Bulgak A A，Bektas T.Integrated cellular manufacturing systems design with production planning and dynamic system reconfiguration［J］.European Journal of Operational Research，2009，192:414 -428.

［6］ Kia R，Baboli A，Javadian N，et al.Solving a group layout design model of a dynamic cellular manufacturing system with alternative process routings，lot splitting and flexible reconfiguration by simulated annealing［J］.Computers and Operations Research，2012，39(11):2642 -2658.

［7］ 白俊杰，龔毅光，王寧生，等.多目標柔性作業(yè)車間分批優(yōu)化調(diào)度［J］.計算機集成制造系統(tǒng)，2010，16(2):396-403.Bai Junjie，Gong Yiguang，Wang Ningsheng，et al.Multi-objective flexible job shop scheduling with lot-splitting［J］.Computer Integrated Manufacturing Systems，2010，16(2):396 -403.(in Chinese)

［8］ 曾強，楊育，沈玲，等.基于準時交貨的批量生產(chǎn) FJSP多目標優(yōu)化［J］.計算機集成制造系統(tǒng)，2011，17(8):1780-1789.Zeng Qiang，Yang Yu，Shen Ling，et al.Multiobjective optimization for batch production FJSP based on just in time delivery［J］.Computer Integrated Manufacturing Systems，2011，17(8):1780 -1789.(in Chinese)

［9］ Kesen S E，Gungor Z.How important is the batch splitting activity in scheduling of virtual manufacturing cells［J］.International Journal of Production Research，2011，49(6):1645-1667.

［10］ Ye Taofeng.Analysis on multi-stage lot streaming:The effect of transfer［J］.Computers ＆ Industrial Engineering，2012，62:1046 -1054.

［11］ Defersha F M，Chen M.A hybrid genetic algorithm for flowshop lot streaming with setups andvariable sublots［J］.International Journal of Production Research，2010，48(6):1705-1726.

［12］ Pan Q K，Suganthan P N，Liang J J，et al.A local-best harmony search algorithm with dynamic sub-harmony memories for lot-streaming flow shop scheduling problem［J］.Expert Systems with Applications，2011，38:3252 -3259.

［13］ Kenndey J，Eberhart R C.Particle swarm optimization［J］.IEEE International Conference on Neural Network，1995:1942-1948.