基于細胞自動機的大尺度制造4D調度模型

陳　勇,羊笑笑,王　成,王亞良

(浙江工業大學 特種裝備制造與先進加工技術教育部重點實驗室，浙江 杭州 310014)

基于細胞自動機的大尺度制造4D調度模型

陳勇,羊笑笑,王成,王亞良

(浙江工業大學 特種裝備制造與先進加工技術教育部重點實驗室，浙江 杭州 310014)

摘要：針對大型裝備生產過程中空間、時間和設備資源沖突問題，提出了基于細胞自動機的大尺度4D調度模型.用生產場地長、寬、零部件加工時間和設備資源四個維度構建4D調度概念.在時間維度上設定分割點劃分三維時空從而獲得有限個三維劃分層.在三維劃分層上建立基于規則的二維空間調度模型和基于層次遺傳算法的設備調度模型.層布局細胞和設備資源調度細胞通過自組織演化規則相互作用構成動態調度系統的演化，建立4D調度細胞自動機模型.通過實例演算驗證模型和算法的正確性和有效性。

關鍵詞：大尺度制造;4D調度;設備調度;細胞機;層次遺傳算法

4D Scheduling model for large-scale equipment manufacturing

based on cellular automata

CHEN Yong, YANG Xiaoxiao, WANG Cheng, WANG Yaliang

(Key Laboratory of Special Purpose Equipment and Advanced Processing Technology, Ministry of

Education, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:To resolve the conflict of the space, time and equipment resource in large-scale equipment manufacturing, a 4D scheduling model based on cellular automata was proposed. Taking length, breadth of the yard, processing time and equipment capabilities as four dimensions, the concept of 4D scheduling was imported. After dividing the three-dimensional workplace into layers, two-dimensional spatial scheduling and equipment scheduling based on hierarchical genetic algorithm in one layer was modeled. 4D scheduling model with layer spatial scheduling cells and equipment scheduling cells influencing each other by local self-evolution rules was built based on cellular automata. Example test was performed to validate the correctness and effectiveness of the 4D scheduling modeling。

Keywords:large-scale equipment manufacture; 4D scheduling; equipment scheduling; cellular automata; hierarchical genetic algorithm

大型裝備產品通常涉及船舶、航天和大型專用設備等，制造過程復雜而獨特，通常具有以下特點：1)采用定位生產；2)零件種類多達數萬種且工藝多樣；3)工序加工時間長，加工設備非唯一并且選擇不同加工設備所需加工時間不同；4)在制品尺寸很大，生產過程中空間場地受限明顯；5)物流設備無法及時響應搬運需求.在大型裝備生產過程中資源沖突明顯，將發生資源沖突的訂單進行優先排序，實現有限資源的合理分配.基于地理空間概念，將此類調度新問題定義為“大尺度制造調度”問題。

目前國內外關于大尺度調度問題的研究主要集中在考慮作業順序約束和空間約束的空間調度問題，以及考慮作業順序約束和共享資源約束的生產調度問題，而將兩者綜合考慮的調度研究很少.文獻[1-2]運用運籌學求解空間調度問題，其復雜性和NP-hard特性使數學模型變量多，約束多，優化求解的難度大，耗時長；文獻[3-4]采用經典的基于調度規則的算法求解空間調度問題，該方法需要特定的調度經驗和特殊環境支持，尋優效率低且無法闡述所得解同最優解的近似程度；文獻[5-6]采用的智能優化算法具有魯棒性強、通用性強等特點，在空間調度領域應用廣泛；文獻[7]中細胞機技術很好地模擬大型裝備空間調度的復雜性和柔性.筆者在三維空間調度基礎上構建4D調度概念，建立基于細胞機的4D調度模型，以期為一定優化目標下大型裝備制造企業生產調度提供有效的分析方法與工具。

14D調度細胞機模型建立

1.1模型抽象

部件在工作平臺上的放置位置、開工時間和加工時間等受交貨期約束、工序約束、空間約束以及設備資源約束等.空間調度涉及第一、第二維度場地二維平面，以及零部件加工時間.設備調度涉及第一、第二維度場地二維平面，零部件加工時間以及設備.由于調度目標存在沖突，兩者需通過博弈達到平衡構建4D調度.如圖1所示。

圖1　4D調度概念Fig.1　4D schduling definition

用三維空間調度的3個關鍵屬性(場地長、寬和時間)構造三維時空.以三維時空資源為對象，物流設備調度周期為劃分點，在時間維度上對其進行層劃分，如圖2所示.該劃分方式使每層所需調度的部件集合穩定，由此三維空間調度問題轉換為有限個二維的布局問題。

圖2　層劃分Fig.2　Layers division

大尺度制造4D調度元胞機二維網格系統共有2行n列，n為三維空間的劃分層數，如圖3所示.每一個網格代表一個元胞，第一行代表每一層所對應的層布局元胞，第二行代表每一層所對應的設備資源調度元胞。

圖3　元胞機網絡結構Fig.3　Network structure of the cellular automata

圖4　模型演化Fig.4　Model evolution

1.2細胞狀態

層布局細胞的鄰域是該層內所布置部件在時間維度上直接影響的層的布局方案以及該層的設備資源調度方案.只有該層及其鄰域層布局成功，且該層內設備資源調度成功時，該層的布局才算成功.某層內設備資源調度細胞的鄰域是其對應的層布局細胞.只有當該層設備調度成功且該層布置成功時，該層的設備調度才算成功。

層布局細胞t時刻的狀態屬性表示為

其中：Bi為第i層待布置部件編號的集合；R1為對應部件時間規則r1的集合，r1∈{0,1}，0表示先到先服務規則，1表示非先到先服務規則；R2為對應部件形狀簡化規則r2的集合，r2∈{0,1}，0表示矩形規則，1表示非矩形規則；R3為對應部件布置策略規則r3的集合，r3∈{0,1}，0表示邊規則，1表示最大剩余空間規則；Db為對應部件決策變量db的集合，db∈{0,1}，0表示部件布置成功，1表示布置失敗。

層內設備資源調度細胞t時刻的狀態屬性表現為

其中：Oi,j為第i層已布置部件bi,j在該層內的工序集合；R4為對應部件定位規則r4的集合，r4∈{0,1}，0表示非相似工序分散布置規則，1表示相似工序分散布置規則；R5為對應搬運工序時間規則r5的集合，r5∈{0,1}，0表示工序在該層完成，1表示工序推遲到下一層完成；R6為對應加工工序時間規則r6的集合，r6∈{0,1}，0表示工序在該層完成，1表示將工序分成前后兩部分，后一部分推遲到下一層完成；Do為是對應工序決策變量do的集合，do∈{0,1}，0表示工序完工，1表示工序未完工。

層布局細胞初始條件設置如下：初始狀態下時間規則設置為先到先服務規則，部件簡化規則設置為矩形規則，定位規則設置為邊策略.相似工序分散布置使設備資源調度難度增加，因此某層內設備資源調度細胞初始規則為選取非相似工序分散布置.邊界條件為定值型，即當所有部件決策變量以及工序決策變量都取0值。

1.3演化規則

當細胞及其鄰域的決策變量db，do任意一值非零時，其對應的db，do為非零的部件或工序的屬性值需要調整，直至細胞及其鄰域中的決策變量都取0，且下一時刻的細胞中的決策變量db，do都取0.此時各個集合狀態屬性保持不變，狀態穩定。

1.4評價函數

模型多目標函數為

EI=αEI1+β(1-EI2)+γ(1-EI3)

(1)

式中：α,β,γ為評價系數；EI1為任務延遲指標；EI2為時空利用率指標；EI3為設備利用率指標，且有

(2)

式中：Cmax為企業在部件制造上所能承受的最大成本；Db為制作完成時間延遲和進行外協制作的部件數目；C1為每個部件的延遲成本，同理：

(3)

式中：Sbi為部件i的占地面積；tbi為部件i的制作周期；Sp為場地的可用面積；T為布置解在時間上的寬度；C2為實際時空利用率每降低一個百分點所帶來的成本，同理：

(4)

式中：tn為每臺設備用于改性任務和運輸任務的時間；to為每臺設備的開動時間；C3為指實際設備有效利用率每降低一個百分點所帶來的成本。

2層模型建立

2.1層布局

2.2層內設備資源調度

2.2.1數學模型

Obj.minmax(tei,j,k)

(5)

(6)

∑l∈Ei,j,kei,j,k,l=1

(7)

(8)

tsi,j,k+1≥tei,j,k

(9)

tei,j,k=ti,j,k+tsi,j,k

(10)

(11)

ti,j,k=Δtl?oi,j,k∈ER∪EX

(12)

模型中：式(5)表示最小化最大完工時間；式(6，7)表示每道工序占用一臺可用設備；式(8)表示設備加工完當前部件后才能加工下一部件；式(9)表示部件工序約束；式(10，11)表示部件當前工序有效完工時間是有效開始與有效處理時間之和.式(12)表示搬運工序的有效處理時間為搬運延遲時間。

將xy平面網格化處理，使每小格長Δy等于寬Δx.普通物流設備運行速率為vg.有效與實際時間的關系如圖5所示，其計算式為

圖5　普通物流設備作業有效與實際時間關系圖Fig.5　The relation between effective and real operation time of general logistics equipment

(13)

(14)

(15)

(16)

tsi,j,k=tei,j,k-1

(17)

(18)

(19)

式(13~19)均需滿足ei,j,k,l=1，?l∈P.式(13，14)分別定義普通物流設備搬入、搬出工序實際處理時間.式(15，16)定義普通運輸工序有效處理時間；式(17)定義普通物流設備有效開始時間；式(18)定義普通物流設備當前任務結束才能處理下一任務；式(19)表示普通物流設備有效時間關系。

行車作業有效與實際時間的關系如圖6所示，對于任意l∈C，其計算式為

圖6　行車作業有效與實際時間關系圖Fig.6　The relation between effective and real operation time of crane

(20)

(21)

(22)

(23)

式(20，21)定義行車搬出工序有效處理時間；式(22，23)定義行車搬入工序有效處理時間。

圖7　行車調度時空網絡圖Fig.7　The network diagram of crane scheduling

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

(33)

(34)

(35)

式(24)表示行車調度目標函數；式(25)定義節點是否在行車行駛路徑中；式(26，27)保證行車運行路徑可行；式(28)表示行車運行安全距離約束和不可跨越約束；式(29)定義行車初始位置；式(30)保證分配給行車的任務得到處理；式(31)表示每臺行車當前任務結束才能處理下一任務；式(32)定義任務優先級；式(33，34)分別表示加工任務和重車任務不可打斷；式(35)定義格點權重。

2.2.2層次遺傳算法

現構建層次遺傳算法求解大尺度制造設備調度問題.用外層算法確定設備集成調度方案，每一個設備集成調度方案對應一個最優的行車調度方案，通過內層得到后傳遞到外層得到最優設備集成調度方案。

外層遺傳算法采用分段編碼，染色體由設備選擇和工序排序兩部分組成，如圖8所示.設備選擇部分保證了后續遺傳操作后產生的解仍是可行解；工序排序部分編碼柔性高，在解碼過程中可以產生活動調度。

圖8　外層遺傳算法染色體編碼Fig.8　Chromosome coding of the outer genetic algorithm

外層遺傳算法種群初始化方式：將全局選擇、局部選擇和隨機選擇有機結合提高初始解在設備選擇部分中解的質量.全局選擇保證優先選擇最短加工機器和平衡機器工作負荷，局部選擇保證選擇負荷最小的機器，隨機選擇保證初始種群多樣性.工序排序部分染色體采用隨機生成初始種群的方法。

外層遺傳算法的遺傳操作方式：選擇操作采用錦標賽方法.設備選擇部分采用均勻交叉法，以保證每位基因的先后順序保持不變.工序排序部分采用POX交叉法.設備選擇部分變異方法為在染色體基因串中隨機選擇一個位置，在此工序的可選設備集中選擇加工時間最短的設備替換當前的基因.工序排序部分采用進行互換變異法，即從染色體中隨機選擇兩個位置的基因，然后將它們進行位置的互換。

內層遺傳算法的染色體編碼：若車間配置n臺行車，則染色體由n段組成，每段長相等為imax，代表相應行車運行軌跡.如圖9所示，基因座代表節點ni,j中i，基因值代表j。

圖9　內層遺傳算法染色體編碼Fig.9　Chromosome coding of the inner genetic algorithm

內層遺傳算法的種群初始化方式：將分配給c1處理的工序按先后排列，每個工序對應生成一條最短基因鏈，當工序任務優先級為2或3時，基因鏈抱團成基因塊，在其它基因座之間均可插入基因使染色體長度為imax，如圖10所示.該方法保證行車有順序地經過各個任務格點，同時縮短了染色體長度。

圖10　內層遺傳算法種群初始化Fig.10　Population initialization of the inner genetic algorithm

內層遺傳算法的遺傳操作方式：選擇操作采用錦標賽方法，從種群中隨機選擇k個個體，選擇最好的個體放到交叉池中，同時被選擇的個體還放回到種群中，可以重新參與選擇.每段染色體交叉方式：選擇在同一可插入基因點插入基因的兩條染色體作為母體，插入基因鏈中的等位基因前后是可選交叉點(圖11所示灰色基因)；隨機選擇其中兩個交叉點，交換兩條交叉點之間的部分染色體；進行可行性判斷與處理.每段染色體變異方式：隨機刪除某段插入的基因鏈，選擇另一尚未插入基因鏈的可插入基因點插入相等長度的基因鏈；進行可行性判斷與處理.交叉及變異方法同樣保證了行車軌跡有順序地經過各個任務節點。

圖11　內層遺傳算法交叉方式Fig.11　Crossover operator of the inner genetic algorithm

內層遺傳算法的可行性判斷與處理方式：在種群初始化、遺傳操作等階段對每個染色體進行可行性判斷，包括不可跨越檢查、安全距離檢查，如果某相對應的染色體段無法滿足要求，則選擇可變動基因較多的那段重新生成染色體，直至滿足要求。

3實例驗證

以某大型裝備企業部件加工車間為例對模型進行檢驗.該部件加工車間由2塊長寬均為60m×12m的區域組成.部件基礎數據如表1所示，部件工序信息如表2所示.車間配備加工設備M1，M2，M3，M4各3臺，行車C共2臺，普通物流設備P1，P2各3臺.行車和普通物流設備的運行速率分別為1，1.5m/s.Cmax=100，C1=0.3，C2=0.3，C3=0.3，α=0.3，β=0.5，γ=0.2.通過模型進行求解.4D調度甘特圖如圖12所示，二維布局圖如圖13所示，Aug8層內的設備資源調度情況見圖14，15.表3顯示改善方案優于原方案，證實基于細胞機的大尺度制造4D調度模型可行、有效。

表1　部件基礎數據表

表2　工序信息表

圖12　4D調度甘特圖Fig.12　The gantt chart of the 4D scheduling

圖13　4D調度二維空間布局Fig.13　The two dimensional space layout of the 4D scheduling

圖14　11.10層設備調度甘特圖Fig.14　The gantt chart of the equipment scheduling in 11.10

圖15　11/10層行車運行軌跡Fig.15　The path of the cranes in 11/10

方案部件延遲指標EI1時空利用率指標EI1設備利用率指標EI3綜合評價指標EI實際方案0.27780.14810.08020.5064D調度方案0.41670.16510.13240.714

4結論

基于細胞機的大尺度制造4D調度模型在改善空間利用率、延遲部件數和設備有效利用率數等關鍵指標上效果明顯.但目前關于大尺度4D調度的研究尚不成熟，模型運行效率有待提高，采用啟發式調度規則尋求二維布局最優效率低效果差，在基礎上尋求設備調度最優易使模型陷入局部最優.因此提高4D調度模型的運行速率和尋優性能是后續研究重點。

參考文獻：

[1]張志英,陳潔.空間調度問題的非線性規劃分析求解方法[J].計算機集成制造系統,2010,16(6):1272-1278。

[2]CHRISTOPHER G, GHAITH R. Exact and approximate methods for parallel multiple-area spatial scheduling with release times[J]. OR Spectrum,2013,35:639-657。

[3]CAPRACE J D, PETCU C, VELARDE M G. Optimization of shipyard space allocation and scheduling using a heuristic algorithm[J]. Journal of Marine Science and Technology,2013,18:404-417。

[4]張志英,曾燕慧,陳潔.基于多規則的船體分段建造空間調度方法[J].工業工程,2011,14(3):96-100。

[5]VALLS V, BALLESTIN F, QUINTANILLA S. A hybrid genetic algorithm for the resource-constrained project scheduling problem[J]. European Journal of Operational Research,2008,85:495-508。

[6]王蕾,張志英.基于規則的船體曲面分段空間調度方法[J].上海交通大學學報,2009,43(11):1709-1714。

[7]陳勇,陳亮.基于細胞機的造船企業分段車間空間調度模型的建模方法:中國,CN102968523A[P].2013-03-13。

[8]陳勇,阮幸聰,王亞良.基于元胞機的大型機械構件生產車間柔性調度求解[J].浙江工業大學學報,2011,39(4):433-439。

[9]陳超,魯建廈.重型機械加工車間物流協調調度問題研究[J].浙江工業大學學報,2011,39(4):452-457。

[10]黃亞平,王萬良,熊婧.基于改進蟻群算法的智能調度系統設計與開發[J].浙江工業大學學報,2010,38(3):251-256。

(責任編輯：陳石平)

中圖分類號：TB497

文獻標志碼：A

文章編號：1006-4303(2015)02-0168-07

作者簡介：陳勇(1973—)，男，湖南湘潭人，教授，博士，研究方向為生產系統建模與仿真，E-mail：cy@zjut.edu.cn。

基金項目：國家自然科學基金資助項目(71371170，71301148)

收稿日期：2014-06-05