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

(浙江工業(yè)大學(xué) 特種裝備制造與先進(jìn)加工技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310014)

基于細(xì)胞自動機(jī)的大尺度制造4D調(diào)度模型

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

(浙江工業(yè)大學(xué) 特種裝備制造與先進(jìn)加工技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310014)

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

關(guān)鍵詞：大尺度制造;4D調(diào)度;設(shè)備調(diào)度;細(xì)胞機(jī);層次遺傳算法

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

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

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

14D調(diào)度細(xì)胞機(jī)模型建立

1.1模型抽象

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

圖1　4D調(diào)度概念Fig.1　4D schduling definition

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

圖2　層劃分Fig.2　Layers division

大尺度制造4D調(diào)度元胞機(jī)二維網(wǎng)格系統(tǒng)共有2行n列，n為三維空間的劃分層數(shù)，如圖3所示.每一個網(wǎng)格代表一個元胞，第一行代表每一層所對應(yīng)的層布局元胞，第二行代表每一層所對應(yīng)的設(shè)備資源調(diào)度元胞。

圖3　元胞機(jī)網(wǎng)絡(luò)結(jié)構(gòu)Fig.3　Network structure of the cellular automata

圖4　模型演化Fig.4　Model evolution

1.2細(xì)胞狀態(tài)

層布局細(xì)胞的鄰域是該層內(nèi)所布置部件在時(shí)間維度上直接影響的層的布局方案以及該層的設(shè)備資源調(diào)度方案.只有該層及其鄰域?qū)硬季殖晒Γ以搶觾?nèi)設(shè)備資源調(diào)度成功時(shí)，該層的布局才算成功.某層內(nèi)設(shè)備資源調(diào)度細(xì)胞的鄰域是其對應(yīng)的層布局細(xì)胞.只有當(dāng)該層設(shè)備調(diào)度成功且該層布置成功時(shí)，該層的設(shè)備調(diào)度才算成功。

層布局細(xì)胞t時(shí)刻的狀態(tài)屬性表示為

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

層內(nèi)設(shè)備資源調(diào)度細(xì)胞t時(shí)刻的狀態(tài)屬性表現(xiàn)為

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

層布局細(xì)胞初始條件設(shè)置如下：初始狀態(tài)下時(shí)間規(guī)則設(shè)置為先到先服務(wù)規(guī)則，部件簡化規(guī)則設(shè)置為矩形規(guī)則，定位規(guī)則設(shè)置為邊策略.相似工序分散布置使設(shè)備資源調(diào)度難度增加，因此某層內(nèi)設(shè)備資源調(diào)度細(xì)胞初始規(guī)則為選取非相似工序分散布置.邊界條件為定值型，即當(dāng)所有部件決策變量以及工序決策變量都取0值。

1.3演化規(guī)則

當(dāng)細(xì)胞及其鄰域的決策變量db，do任意一值非零時(shí)，其對應(yīng)的db，do為非零的部件或工序的屬性值需要調(diào)整，直至細(xì)胞及其鄰域中的決策變量都取0，且下一時(shí)刻的細(xì)胞中的決策變量db，do都取0.此時(shí)各個集合狀態(tài)屬性保持不變，狀態(tài)穩(wěn)定。

1.4評價(jià)函數(shù)

模型多目標(biāo)函數(shù)為

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

(1)

式中：α,β,γ為評價(jià)系數(shù)；EI1為任務(wù)延遲指標(biāo)；EI2為時(shí)空利用率指標(biāo)；EI3為設(shè)備利用率指標(biāo)，且有

(2)

式中：Cmax為企業(yè)在部件制造上所能承受的最大成本；Db為制作完成時(shí)間延遲和進(jìn)行外協(xié)制作的部件數(shù)目；C1為每個部件的延遲成本，同理：

(3)

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

(4)

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

2層模型建立

2.1層布局

2.2層內(nèi)設(shè)備資源調(diào)度

2.2.1數(shù)學(xué)模型

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)表示最小化最大完工時(shí)間；式(6，7)表示每道工序占用一臺可用設(shè)備；式(8)表示設(shè)備加工完當(dāng)前部件后才能加工下一部件；式(9)表示部件工序約束；式(10，11)表示部件當(dāng)前工序有效完工時(shí)間是有效開始與有效處理時(shí)間之和.式(12)表示搬運(yùn)工序的有效處理時(shí)間為搬運(yùn)延遲時(shí)間。

將xy平面網(wǎng)格化處理，使每小格長Δy等于寬Δx.普通物流設(shè)備運(yùn)行速率為vg.有效與實(shí)際時(shí)間的關(guān)系如圖5所示，其計(jì)算式為

圖5　普通物流設(shè)備作業(yè)有效與實(shí)際時(shí)間關(guān)系圖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)分別定義普通物流設(shè)備搬入、搬出工序?qū)嶋H處理時(shí)間.式(15，16)定義普通運(yùn)輸工序有效處理時(shí)間；式(17)定義普通物流設(shè)備有效開始時(shí)間；式(18)定義普通物流設(shè)備當(dāng)前任務(wù)結(jié)束才能處理下一任務(wù)；式(19)表示普通物流設(shè)備有效時(shí)間關(guān)系。

行車作業(yè)有效與實(shí)際時(shí)間的關(guān)系如圖6所示，對于任意l∈C，其計(jì)算式為

圖6　行車作業(yè)有效與實(shí)際時(shí)間關(guān)系圖Fig.6　The relation between effective and real operation time of crane

(20)

(21)

(22)

(23)

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

圖7　行車調(diào)度時(shí)空網(wǎng)絡(luò)圖Fig.7　The network diagram of crane scheduling

(24)

(25)

(26)

(27)

(28)

(29)

(30)

(31)

(32)

(33)

(34)

(35)

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

2.2.2層次遺傳算法

現(xiàn)構(gòu)建層次遺傳算法求解大尺度制造設(shè)備調(diào)度問題.用外層算法確定設(shè)備集成調(diào)度方案，每一個設(shè)備集成調(diào)度方案對應(yīng)一個最優(yōu)的行車調(diào)度方案，通過內(nèi)層得到后傳遞到外層得到最優(yōu)設(shè)備集成調(diào)度方案。

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

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

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

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

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

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

內(nèi)層遺傳算法的種群初始化方式：將分配給c1處理的工序按先后排列，每個工序?qū)?yīng)生成一條最短基因鏈，當(dāng)工序任務(wù)優(yōu)先級為2或3時(shí)，基因鏈抱團(tuán)成基因塊，在其它基因座之間均可插入基因使染色體長度為imax，如圖10所示.該方法保證行車有順序地經(jīng)過各個任務(wù)格點(diǎn)，同時(shí)縮短了染色體長度。

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

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

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

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

3實(shí)例驗(yàn)證

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

表1　部件基礎(chǔ)數(shù)據(jù)表

表2　工序信息表

圖12　4D調(diào)度甘特圖Fig.12　The gantt chart of the 4D scheduling

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

圖14　11.10層設(shè)備調(diào)度甘特圖Fig.14　The gantt chart of the equipment scheduling in 11.10

圖15　11/10層行車運(yùn)行軌跡Fig.15　The path of the cranes in 11/10

方案部件延遲指標(biāo)EI1時(shí)空利用率指標(biāo)EI1設(shè)備利用率指標(biāo)EI3綜合評價(jià)指標(biāo)EI實(shí)際方案0.27780.14810.08020.5064D調(diào)度方案0.41670.16510.13240.714

4結(jié)論

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

參考文獻(xiàn)：

[1]張志英,陳潔.空間調(diào)度問題的非線性規(guī)劃分析求解方法[J].計(jì)算機(jī)集成制造系統(tǒng),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]張志英,曾燕慧,陳潔.基于多規(guī)則的船體分段建造空間調(diào)度方法[J].工業(yè)工程,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]王蕾,張志英.基于規(guī)則的船體曲面分段空間調(diào)度方法[J].上海交通大學(xué)學(xué)報(bào),2009,43(11):1709-1714。

[7]陳勇,陳亮.基于細(xì)胞機(jī)的造船企業(yè)分段車間空間調(diào)度模型的建模方法:中國,CN102968523A[P].2013-03-13。

[8]陳勇,阮幸聰,王亞良.基于元胞機(jī)的大型機(jī)械構(gòu)件生產(chǎn)車間柔性調(diào)度求解[J].浙江工業(yè)大學(xué)學(xué)報(bào),2011,39(4):433-439。

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

[10]黃亞平,王萬良,熊婧.基于改進(jìn)蟻群算法的智能調(diào)度系統(tǒng)設(shè)計(jì)與開發(fā)[J].浙江工業(yè)大學(xué)學(xué)報(bào),2010,38(3):251-256。

(責(zé)任編輯：陳石平)

中圖分類號：TB497

文獻(xiàn)標(biāo)志碼：A

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

作者簡介：陳勇(1973—)，男，湖南湘潭人，教授，博士，研究方向?yàn)樯a(chǎn)系統(tǒng)建模與仿真，E-mail：cy@zjut.edu.cn。

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(71371170，71301148)

收稿日期：2014-06-05