云制造模式下基于變鄰域動(dòng)態(tài)煙花算法的柔性車間調(diào)度*

董 海，戴 瑤，張?zhí)烊?/p>

(沈陽大學(xué) a.應(yīng)用技術(shù)學(xué)院；b.機(jī)械工程學(xué)院，沈陽 110044)

0 引言

柔性作業(yè)車間調(diào)度打破傳統(tǒng)作業(yè)車間調(diào)度問題中工序?qū)庸C(jī)器的限制，增加調(diào)度系統(tǒng)靈活性。近年來，隨著制造業(yè)信息化和智能化推進(jìn)，以云制造為代表的智慧化制造模式將成為制造業(yè)發(fā)展的必然趨勢[1]。云制造利用網(wǎng)絡(luò)信息，構(gòu)建存在云制造任務(wù)的虛擬云平臺，基于車間自生產(chǎn)調(diào)度，結(jié)合云制造任務(wù)，為提升閑置資源利用率，提供制造服務(wù)的網(wǎng)絡(luò)化制造新模式[2]。協(xié)調(diào)云制造任務(wù)和自生產(chǎn)任務(wù)，避免二者調(diào)度任務(wù)沖突，須同時(shí)綜合考慮兩種調(diào)度任務(wù)，建立多目標(biāo)模型，協(xié)同調(diào)度[3]。

李伯虎等[4]提出一種智慧化制造新模式—云制造，它是云計(jì)算在制造業(yè)的延伸，它將面向設(shè)備、面向生產(chǎn)、面向制造的制造模式演化成面向需求、面向服務(wù)、面向信息的新形式。王軍強(qiáng)等[5]面向云制造建立作業(yè)車間機(jī)器能力限定模型。何林燕[6]在云制造模式的基礎(chǔ)上，提出車間生產(chǎn)和資源調(diào)度問題。魯建廈等[7]綜合考慮云制造環(huán)境下混流混合作業(yè)車間調(diào)度，建立以最小化完工時(shí)間、均衡化零部件生產(chǎn)和最大化機(jī)器利用率為優(yōu)化目標(biāo)的調(diào)度模型。

綜上，本文嘗試在云制造大環(huán)境下，以最大完工時(shí)間最小，車間機(jī)器利用率最大，碳排放量最小為指標(biāo)，探索云制造模式下柔性車間協(xié)同調(diào)度模型和算法求解，以提升制造資源整體利用率。

1 問題描述

1.1 云制造模式下柔性車間調(diào)度模型描述

圖1 調(diào)度框架圖

云制造模式下柔性車間調(diào)度模型是以車間自生產(chǎn)任務(wù)為基礎(chǔ)，以最大完工時(shí)間最小化，車間機(jī)器利用率最大化，碳排放量最小為目標(biāo)，建立如圖1所示調(diào)度框架。

步驟1：尋找閑置制造資源。柔性作業(yè)車間按照車間自生產(chǎn)任務(wù)進(jìn)行優(yōu)化調(diào)度，同時(shí)尋找可利用的機(jī)器，確定柔性作業(yè)車間的閑置制造資源，即車間的剩余生產(chǎn)能力，等待外協(xié)云平臺調(diào)度任務(wù)。

步驟2：云平臺任務(wù)調(diào)度。柔性作業(yè)車間的閑置制造資源已知，插入外協(xié)云平臺的制造任務(wù)，進(jìn)行云任務(wù)調(diào)度，以機(jī)器利用率最大化為目標(biāo)，選取最優(yōu)的云平臺調(diào)度方案。

步驟3：確定最終調(diào)度方案。如果云平臺調(diào)度方案符合外協(xié)云平臺任務(wù)要求，則此方案為最終調(diào)度方案；反之，需要與柔性作業(yè)車間自生產(chǎn)任務(wù)進(jìn)行協(xié)同重調(diào)度，若作業(yè)車間自生產(chǎn)任務(wù)已經(jīng)開始生產(chǎn)，云調(diào)度任務(wù)無法完成，則轉(zhuǎn)至下一個(gè)生產(chǎn)周期進(jìn)行再次調(diào)度。

1.2 多目標(biāo)優(yōu)化云制造調(diào)度模型建立

假設(shè)參與云制造的某柔性作業(yè)車間有M臺機(jī)器，X種車間自生產(chǎn)產(chǎn)品，Y種云平臺制造產(chǎn)品，將所有制造產(chǎn)品分成若干生產(chǎn)批次，已知所有產(chǎn)品的工藝順序，每一生產(chǎn)批次可作為整體處理。云平臺制造任務(wù)柔性分批，批量不定；作業(yè)車間自生產(chǎn)任務(wù)不做要求，以滿足最大完工時(shí)間最小，車間機(jī)器利用率最大，碳排放量最小為目標(biāo)，進(jìn)行優(yōu)化調(diào)度。

1.2.1 目標(biāo)函數(shù)的確定

云制造模式下柔性作業(yè)車間調(diào)度問題中，為體現(xiàn)整個(gè)作業(yè)車間生產(chǎn)系統(tǒng)的效率，取最大完工時(shí)間作為目標(biāo)函數(shù)，其影響著每個(gè)工件的生產(chǎn)周期。此外，考慮制造業(yè)能源消耗日益嚴(yán)重，引入最小化碳排放，使調(diào)度在解決作業(yè)車間和云任務(wù)調(diào)度的同時(shí)，也減少實(shí)際生產(chǎn)的碳排放(機(jī)器加工和空閑時(shí)的碳排放)。隨著能源消耗過度，節(jié)能減排的需求不斷加大，而車間是制造能源消耗的主要場所，低碳問題已經(jīng)成為調(diào)度問題的拓展。云制造任務(wù)和傳統(tǒng)柔性作業(yè)車間協(xié)同調(diào)度的目的為了最大限度地增加整體制造資源的利用率，故選取最大化資源利用率作為云制造模式下柔性車間調(diào)度的優(yōu)化目標(biāo)。

(1)最大完工時(shí)間最小化

云制造模式下柔性作業(yè)車間調(diào)度模型中存在兩種生產(chǎn)任務(wù)，分別為作業(yè)車間自生產(chǎn)任務(wù)和外協(xié)云平臺制造任務(wù)。最小化最大完工時(shí)間即從工件加工開始到最后一個(gè)工序加工完成所消耗最長的時(shí)間最小，這也是評價(jià)作業(yè)車間生產(chǎn)效率的主要形式。建立最小化最大完工時(shí)間模型：

F(A)=min(max(Aij,Aeq))

(1)

Aij—作業(yè)車間自生產(chǎn)產(chǎn)品i在工位j上的完工時(shí)刻；Aeq—云平臺任務(wù)產(chǎn)品e在q機(jī)器上的完工時(shí)刻；其中Aij和Aeq中偏大的值即為調(diào)度系統(tǒng)的最大完工時(shí)間。

(2)碳排放量最小化

調(diào)度模型引入碳排放為優(yōu)化目標(biāo)，在實(shí)現(xiàn)作業(yè)車間調(diào)度任務(wù)的同時(shí)，也達(dá)到減少生產(chǎn)作業(yè)車間碳排放量的目標(biāo)，降低整體作業(yè)車間消耗。即使協(xié)同調(diào)度車間調(diào)度方案的總碳排放量最小，實(shí)現(xiàn)低碳排放，避免不必要的碳排放，減少能源消耗。由此建立以下模型：

(2)

單位時(shí)間內(nèi)總排放函數(shù)模型為：

(3)

其中，i—機(jī)器工序號；s—表示機(jī)器的狀態(tài)；A—最大完工時(shí)間；B—機(jī)器的碳排放函數(shù)。

(3)最大化柔性車間資源利用率。

最大化柔性車間資源利用率，即最小化機(jī)器閑置時(shí)間，故將其轉(zhuǎn)化成最小化機(jī)器閑置時(shí)間，即：

(4)

其中，F(xiàn)m—機(jī)器m的閑置時(shí)間；Am—機(jī)器m的最大加工時(shí)間。

1.2.2 模型約束

云制造模式下的柔性作業(yè)車間調(diào)度指在外協(xié)云平臺任務(wù)和作業(yè)車間自生產(chǎn)任務(wù)協(xié)同調(diào)度的系統(tǒng)中，存在n個(gè)待加工工件，表示為J=(J1,J2,···,Jn)；集合中有m臺機(jī)器，表示為M=(M1,M2,···,Mm)；每個(gè)工件有若干的工序，用Pijk表示工件i在機(jī)器k上加工第j道工序。

外協(xié)云平臺產(chǎn)品和車間自生產(chǎn)產(chǎn)品工序的加工路徑并非唯一，一個(gè)工序可在不同機(jī)器上完成加工，且不同機(jī)器的完工時(shí)間不同。其中：

i(i=1,2,···,n)—工序號；i(i=1,2,···,n)—機(jī)器序號；j—加工工序號；gij—工件i的加工工序數(shù)j；tijk—工件i的第j道工序在機(jī)器k上加工時(shí)間；sij—工件i的第j道工序的起始時(shí)間；eij—工件i第j工序的完工時(shí)間；Pij—工件i的第j道工序的加工時(shí)間；W—無窮大的正整數(shù)；Ci—工件i的全部工序完工時(shí)間；Amax—為最大完工時(shí)間；Xijk—工件i的第j道工序在機(jī)器k上加工；Yijefk—Pij早于Pef在機(jī)器k上加工。具體約束如下：

(1)工序約束：按照已確定調(diào)度系統(tǒng)中工藝順序加工，下一道工序須在前一道工序加工完再進(jìn)行加工，即：

Sij+Xijk+tijk≤eif(1≤j≤gij)

(5)

eij≤Amax(1≤j≤gij)

(6)

(2)加工時(shí)間約束：同一時(shí)間同一機(jī)器只能加工一道工序，工件后一個(gè)工序的起始時(shí)間一定大于等于上一個(gè)工序的結(jié)束時(shí)間，即：

eij+eijk≤sef+W(1-yijkefk) (1≤j≤gij)

(7)

eij≤sj(j+1)+W(1-yefi(j+1)k)

(8)

(3)完工時(shí)間：每個(gè)工件的完工時(shí)間都小于全部工件的完工時(shí)間，即：cij≤Amax(1≤j≤gij)

(9)

(10)

(5)約束中各項(xiàng)參數(shù)均是大于等于零的正數(shù)，即：

sij≥0,eij≥0

(11)

2 模型求解

2.1 煙花算法

煙花算法(Firework Algorithm，F(xiàn)WA)是譚營等受煙花爆炸的啟發(fā)提出的一種群體智能算法[8]。在FWA中，通過爆炸、變異、選擇等進(jìn)行爆炸式搜索，爆炸過程視為鄰域搜索過程，爆炸隨機(jī)產(chǎn)生的煙花，視為解空間的一個(gè)解[9]。每個(gè)煙花適應(yīng)度值不同，爆炸產(chǎn)生的半徑和火花數(shù)不同。適應(yīng)度值好，產(chǎn)生子代火花的數(shù)目越多，爆炸半徑越小，局部搜索能力越強(qiáng)；反之，爆炸半徑越大，具有全局搜索能力。為保證種群的多樣性，在搜索過程中，要對煙花進(jìn)行適當(dāng)變異，平衡全局搜索和局部搜索[10]。

2.2 變鄰域搜索算法

變鄰域搜索(Variable Neighborhood Search，VNS)是一種元啟發(fā)式算法，將這種算法應(yīng)用于演化算法，來增強(qiáng)煙花算法的全局搜索能力，利用改變鄰域搜索方式提高收斂速度和尋優(yōu)精度。VNS在爆炸搜索過程中，引入交換、逆序和插入三種變鄰域結(jié)構(gòu)來擴(kuò)展搜索范圍，使之具有更好的全局尋優(yōu)能力和收斂速度。①交換。隨機(jī)交換執(zhí)行工序順序中任兩個(gè)不同工件的順序；②逆序。隨機(jī)選擇工序執(zhí)行順序中的某一段工件，將其逆序；③插入。選擇隨機(jī)位置插入隨機(jī)工件。將3種變鄰域結(jié)構(gòu)引入到煙花算法的全局尋優(yōu)過程，從而有效避免在求解云制造模式下柔性車間調(diào)度模型過程中陷入局部最優(yōu)。

2.3 動(dòng)態(tài)煙花算法

煙花爆炸產(chǎn)生火花總數(shù)與爆炸半徑：

(12)

圖2 算法步驟

(13)

其中，i(i=1,2,···,N)—煙花序號(N為總煙花數(shù))；fi—適應(yīng)度值；fmin—當(dāng)前適應(yīng)度最小值；fmax—當(dāng)前適應(yīng)度最大值；ξ—一個(gè)最小量，避免出現(xiàn)除零；S—煙花爆炸產(chǎn)生的總火花數(shù)；A—表示最大爆炸半徑。

在群體優(yōu)化算法中，種群多樣性越大，個(gè)體的分布情況越廣，找到算法最優(yōu)值的可能性越大，故保證種群多樣性至關(guān)重要，同時(shí)也不會(huì)對算法的收斂性產(chǎn)生明顯的影響。所以在算法中，適應(yīng)度好的煙花不易過多爆炸，避免對子代煙花有較大影響，引發(fā)種群多樣性減弱。但適應(yīng)度較差的煙花數(shù)也要保證，所以對煙花數(shù)進(jìn)行以下約束：

(14)

其中，smin—最小爆炸火花數(shù)(smin=0.4×s)；

smax—最大爆炸火花數(shù)(smax=0.9×s)。

(15)

(16)

(17)

在算法迭代過程中，下一次迭代由距離概率取(l-1)個(gè)個(gè)體與最優(yōu)個(gè)體作為父代煙花選取群體中最優(yōu)個(gè)體，且根據(jù)距離概率取(l-1)個(gè)個(gè)體與最優(yōu)個(gè)體作為下一代的父代煙花。此外，本文針對維度K的選擇問題，引入動(dòng)態(tài)煙花算法進(jìn)行動(dòng)態(tài)更新維度。K維度過大，種群多樣性削弱，算法易陷入局部最優(yōu)；K維度過小，算法優(yōu)化速度減慢，收斂能力減弱。

爆炸煙花的進(jìn)化速度：v，在第t次迭代計(jì)算時(shí)，前(t-1)次迭代計(jì)算中最優(yōu)值線性函數(shù)為：

(18)

(19)

其中,μ,λ∈(0,1)—調(diào)整因子；

v0—初始時(shí)刻設(shè)定起始速度值。

在算法求解過程中，為加快收斂速度，增強(qiáng)全局尋優(yōu)能力，動(dòng)態(tài)調(diào)整維度K。

2.4 算法步驟

算法具體步驟如圖2所示。

(1)初始化，產(chǎn)生n個(gè)初始煙花；

(2)煙花爆炸，計(jì)算爆炸半徑和產(chǎn)生火花個(gè)數(shù)；

(3)根據(jù)爆產(chǎn)生爆炸火花和高斯變異火花，計(jì)算進(jìn)化速度；

(4)動(dòng)態(tài)更新維度K；

(5)調(diào)整搜索鄰域；

(6)選擇父代煙花進(jìn)行下次迭代；

(7)判斷是否滿足終止條件，若滿足，輸出最優(yōu)值；反之，返回第(2)步。

3 實(shí)驗(yàn)仿真與結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

為檢驗(yàn)變鄰域搜索動(dòng)態(tài)煙花算法的性能，選取粒子群優(yōu)化算法和遺傳算法，在MATLAB平臺分別進(jìn)行仿真對比實(shí)驗(yàn)。變鄰域搜索動(dòng)態(tài)煙花算法初始參數(shù)設(shè)置：高斯火花個(gè)數(shù)= 5；火花總數(shù)= 25；參數(shù)A= 0.8；參數(shù)B= 0.04；最大爆炸幅度= 25。粒子群優(yōu)化算法初始參數(shù)設(shè)置：粒子個(gè)體跟蹤自己歷史最優(yōu)值的權(quán)重= 2；粒子個(gè)體跟蹤群體最優(yōu)值的權(quán)重= 2；慣性權(quán)重= 0.8。遺傳算法初始參數(shù)設(shè)置：個(gè)體編碼長度 = 30；變異率= 0.05。

3.2 實(shí)驗(yàn)結(jié)果

三種算法在運(yùn)算步驟上有所不同，其中粒子群優(yōu)化算法是通過更新粒子的歷史最好位置和速度；遺傳算法則進(jìn)行選擇、交叉和變異；變鄰域動(dòng)態(tài)煙花算法是通過改變鄰域、執(zhí)行爆炸、變異和動(dòng)態(tài)更新維度等優(yōu)化操作。上述算法在結(jié)構(gòu)上都經(jīng)過初始化種群，計(jì)算個(gè)體適應(yīng)度值，直到滿足終止條件，算法結(jié)束，反之繼續(xù)計(jì)算個(gè)體適應(yīng)度值，進(jìn)行再次迭代。三種算法運(yùn)算步驟雖有差異，但其結(jié)構(gòu)極其相似，對三種算法進(jìn)行仿真對比實(shí)驗(yàn)，使實(shí)驗(yàn)結(jié)果更具有說服力。

3.2.1 算法有效性驗(yàn)證

將種群規(guī)模都為100的三種算法設(shè)置相同數(shù)據(jù)進(jìn)行200次迭代，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 三種算法求得的最優(yōu)適應(yīng)度值

由此看來，三種算法在求解云制造模式下柔性作業(yè)車間調(diào)度問題時(shí)，變鄰域動(dòng)態(tài)煙花算法的種群中，每個(gè)煙花在一次迭代中產(chǎn)生多個(gè)個(gè)體，而其他兩種算法通常只產(chǎn)生一個(gè)個(gè)體，在產(chǎn)生子代個(gè)體方面，煙花算法遠(yuǎn)優(yōu)于粒子群優(yōu)化算法和遺傳算法，實(shí)驗(yàn)數(shù)據(jù)可以看出，變鄰域動(dòng)態(tài)煙花算法求得最優(yōu)適應(yīng)度值次數(shù)達(dá)到實(shí)驗(yàn)總次數(shù)的95%，同時(shí)也證明在相同的環(huán)境下，變鄰域動(dòng)態(tài)煙花算法的變鄰域、執(zhí)行爆炸、變異和動(dòng)態(tài)更新維度等機(jī)制搜索更徹底，尋優(yōu)能力更強(qiáng)。

3.2.2 算法執(zhí)行效率驗(yàn)證

三種算法的種群規(guī)模設(shè)置為50、100、150、200、250、300、350、400、450、550。分別進(jìn)行200次迭代。如圖4所示三種算法在相同條件下執(zhí)行時(shí)間的對比情況。

通過實(shí)驗(yàn)可以看出，隨著種群規(guī)模的增大，粒子群優(yōu)化算法和遺傳算法的執(zhí)行時(shí)間明顯增加，而變鄰域動(dòng)態(tài)煙花算法受種群規(guī)模影響不明顯，表現(xiàn)出良好的優(yōu)越性。變鄰域動(dòng)態(tài)煙花算法通過選擇機(jī)制、爆炸半徑和產(chǎn)生火花數(shù)、變異的變鄰域搜索體系保證種群的多樣性。也保證超出可行域范圍的煙花映射到鄰域搜索范圍內(nèi)，體現(xiàn)了算法強(qiáng)大的局部搜索能力。

圖4 種群規(guī)模對三種算法執(zhí)行時(shí)間的影響

所以，種群的增大對變鄰域動(dòng)態(tài)煙花算法執(zhí)行時(shí)間影響不大，穩(wěn)定性良好，適用于大規(guī)模種群的調(diào)度作業(yè)。

4 結(jié)論

結(jié)合云制造模式，以工序級為最小調(diào)度粒度，關(guān)注傳統(tǒng)柔性作業(yè)車間閑置資源問題，協(xié)同考慮外協(xié)云平臺任務(wù)和作業(yè)車間自生產(chǎn)任務(wù)調(diào)度。以最大完工時(shí)間最小化，車間制造資源利用率最大，碳排放量最小化為目標(biāo)建立調(diào)度模型，在作業(yè)車間中進(jìn)行批量劃分，協(xié)調(diào)云任務(wù)和作業(yè)車間自生產(chǎn)任務(wù)。得到以下結(jié)論：

(1)研究云制造模式下柔性車間調(diào)度問題，提出最小化最大完工時(shí)間的最低碳排放為指標(biāo)的多目標(biāo)柔性車間調(diào)度模型，通過建立低碳排放的柔性作業(yè)車間，提升車間整體效率。

(2)設(shè)計(jì)變鄰域動(dòng)態(tài)煙花算法，引入3個(gè)鄰域結(jié)構(gòu)，為減輕預(yù)先生成工件的加工路線計(jì)算負(fù)擔(dān)，采用集成型調(diào)度，有效解決全部工件的加工路線和最終的調(diào)度方案。

(3)三種算法對比實(shí)驗(yàn)表明，在相同的環(huán)境下變鄰域動(dòng)態(tài)煙花算法搜索更徹底，尋優(yōu)能力強(qiáng)，穩(wěn)定性好，更適用大規(guī)模種群的調(diào)度。