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

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

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

0 引言

柔性作業(yè)車間調(diào)度打破傳統(tǒng)作業(yè)車間調(diào)度問題中工序?qū)庸C器的限制，增加調(diào)度系統(tǒng)靈活性。近年來，隨著制造業(yè)信息化和智能化推進，以云制造為代表的智慧化制造模式將成為制造業(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ù)沖突，須同時綜合考慮兩種調(diào)度任務(wù)，建立多目標(biāo)模型，協(xié)同調(diào)度[3]。

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)碳排放量最小化

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

(2)

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

(3)

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

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

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

(4)

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

1.2.2 模型約束

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

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

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

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

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

(5)

eij≤Amax(1≤j≤gij)

(6)

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

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

(7)

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

(8)

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

(9)

(10)

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

sij≥0,eij≥0

(11)

2 模型求解

2.1 煙花算法

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

2.2 變鄰域搜索算法

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

2.3 動態(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)度最大值；ξ—一個最小量，避免出現(xiàn)除零；S—煙花爆炸產(chǎn)生的總火花數(shù)；A—表示最大爆炸半徑。

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

(14)

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

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

(15)

(16)

(17)

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

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

(18)

(19)

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

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

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

2.4 算法步驟

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

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

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

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

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

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

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

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

3 實驗仿真與結(jié)果分析

3.1 實驗環(huán)境

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

3.2 實驗結(jié)果

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

3.2.1 算法有效性驗證

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

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

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

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

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

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

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

所以，種群的增大對變鄰域動態(tài)煙花算法執(zhí)行時間影響不大，穩(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)度。以最大完工時間最小化，車間制造資源利用率最大，碳排放量最小化為目標(biāo)建立調(diào)度模型，在作業(yè)車間中進行批量劃分，協(xié)調(diào)云任務(wù)和作業(yè)車間自生產(chǎn)任務(wù)。得到以下結(jié)論：

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

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

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