黃海松，劉 凱，初光勇

(1.貴州大學(xué) 現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴陽 550025；2. 銅仁職業(yè)技術(shù)學(xué)院 工學(xué)院，貴州 銅仁 554300)

0 引言

現(xiàn)代制造方式不僅追求快速、高效地完成加工任務(wù)，更加追求低碳生產(chǎn)[1]。合適的車間調(diào)度策略不僅可以提高產(chǎn)品質(zhì)量、縮短生產(chǎn)時間，優(yōu)化加工方案，從而減少加工過程中的能源消耗，進(jìn)而控制碳排放。

在傳統(tǒng)作業(yè)車間調(diào)度問題中，對加工機(jī)器的數(shù)量進(jìn)行限制，柔性作業(yè)車間調(diào)度問題(Flexible job-shop scheduling problem ,FJSP)是其擴(kuò)展，增加了車間調(diào)度的靈活性，使其更加貼近生活領(lǐng)域[2]。但由于FJSP減少對加工設(shè)備的約束，擴(kuò)大搜索范圍，故問題的求解更加復(fù)雜。針對FJSP的復(fù)雜性，目前常用的求解方法有:遺傳算法(GA)[3]、粒子群優(yōu)化算法(PSO)[4]、模擬退火算法(SA)[5]等智能優(yōu)化算法。其中模擬退火算法穩(wěn)定性好，應(yīng)用范圍廣闊。Laarhoven等[6]于1992年最早將模擬退火算法應(yīng)用于求解車間作業(yè)(Job Shop)調(diào)度問題。Dai等[7]將遺傳算法與退火算法結(jié)合對柔性作業(yè)車間的能源消耗進(jìn)行優(yōu)化。蔣增強(qiáng)等[8]使用改進(jìn)的NSGA-II算法求解多目標(biāo)，求解過程中考慮到設(shè)備狀態(tài)和能耗分布。Xia等[9]采用了混合例子群算法來優(yōu)化FJSP中的生產(chǎn)管理和組合優(yōu)化問題，通過引入模擬退火的思想實(shí)現(xiàn)局部搜索，避免算法陷入局部最優(yōu)解。張其亮等[10]等利用基于NEH算法解決工件加工順序問題。劉愛軍等[11]針對客戶滿意度和完工時間為目標(biāo)求解FJSP問題。梁旭等[12]提出一種求解車間調(diào)度問題的新遺傳退火算法。

本文以某工廠生產(chǎn)車間為例，建立了以最大完工時間和碳排放為目標(biāo)的柔性作業(yè)車間調(diào)度模型，運(yùn)用改進(jìn)的模擬退火算法進(jìn)行求解，驗(yàn)證了所提出的算法在加入低碳要求的車間調(diào)度中的可行性和有效性。

1 柔性作業(yè)車間模型建立

FJSP問題可以描述為：n個代加工工件的集合為J={J1，J2…Ji，…Jn}(i∈[1,n]),m臺機(jī)器集合為M={M1，M2…Mj，…Mm}(j∈[1,m])，且滿足的約束條件有：①第i個工件Ji的第k道工序加工機(jī)器選擇不止一臺機(jī)器，但不能再多臺機(jī)器上加工。②任何工件的任何工序加工一次性完成，不能中斷。③第j臺機(jī)器Mj在任意時刻最多只能有一個工件在上面加工。④第i個工件Ji工件的準(zhǔn)備和移動時間包含在加工時間內(nèi)。⑤加工過程中的機(jī)器在工件沒有運(yùn)送到達(dá)時間限制，允許各個工序之間存在等待。為方便討論，引入如表1所示的數(shù)學(xué)符號。

表1 數(shù)學(xué)符號定義

本文調(diào)度模型研究的兩個目標(biāo)是加工時間和碳排放量，用T表示工序的加工時間，用C表示碳的總排放量。問題的數(shù)學(xué)模型建立如下。

(1)加工時間。FJSP的計(jì)算總完成時間計(jì)算方法。

(1)

(2)碳排放量。碳排放量只考慮加工過程中的碳排放，不考慮材料在運(yùn)輸中等環(huán)節(jié)的能源消耗。

(2)

(3)評價函數(shù)

minf(x)=α·T+β·C

(3)

假設(shè)在這個問題中，存在一個可行域，則這個可行域中的任意一個點(diǎn)都有對應(yīng)的x，y的值，x，y值對應(yīng)就是T,C的值乘以各自的權(quán)重，比較所有的方案，f(x)的值越大，此方案的適應(yīng)度值越低，方案越差，故f(x)的值最小的方案即是所選擇的方案。如圖1所示。

圖1 可行域方案集

2 改進(jìn)模擬退火算法求解FJSP問題

改進(jìn)的模擬退火算法(Modified Simulated Annealing，MSA)將粒子群(PSO)中的編碼方式引用到機(jī)器編碼中，在選擇機(jī)器時采用了隨機(jī)位置法與輪盤賭[13]的兩種不同的方法進(jìn)行編碼，通過算例驗(yàn)證證明輪盤賭的機(jī)器編碼可以大大減少運(yùn)行時間。并采取兩種不同的局部搜索方法建立領(lǐng)域結(jié)構(gòu)。

2.1 編碼方法

解決柔性作業(yè)車間調(diào)度問題，需要確定每個工件的加工路徑，即工件的每一道加工工序的機(jī)器選擇，本文通過兩種不同的編碼方法(隨機(jī)位置和輪盤賭)對加工機(jī)器人進(jìn)行選擇，進(jìn)而確定工件的加工路徑。

(1)隨機(jī)位置的個體編碼

隨機(jī)位置的個體編碼需要對規(guī)定位置的取值范圍，一般是取值范圍是正數(shù)。首先隨機(jī)生成一個數(shù)x，對其進(jìn)行取整操作，通過一定的函數(shù)關(guān)系得到每道工序加工的機(jī)器，進(jìn)而得到工件的加工路徑，最后生成調(diào)度方案。

(2)輪盤賭的個體編碼

柔性作業(yè)車間調(diào)度問題的特性是一道工序可以在多個機(jī)器上加工，但不是所有的機(jī)器可以加工這道工序，故采用隨機(jī)位置的個體編碼并不能確保每一次的機(jī)器的選取都能選到備選機(jī)器的范圍。如果選取不在備選區(qū)域內(nèi)，則需要進(jìn)行二次選取，這樣會大大增加系統(tǒng)算法的工作時間。因此采用輪盤賭的編碼方法進(jìn)行編碼，該方法可以確保每一次的機(jī)器選取都有唯一的一臺機(jī)器與之對應(yīng)，因此該方法編碼大大減少了算法的運(yùn)行的時間，加快算法的搜索的效率。以3臺機(jī)器為例具體流程如表2所示。

表2 二維機(jī)器編碼

①根據(jù)上述表2中加工時間的大小，從小到大排序，同時相應(yīng)的調(diào)整第一位機(jī)器號碼的次序。

②計(jì)算所有的機(jī)器號碼對應(yīng)加工時間的總和∑Tj，并計(jì)算每個工件j所對應(yīng)的比例pj，即有：

(4)

③工序O產(chǎn)生一個隨機(jī)數(shù)并滿足一下O(0，1)，如果0

2.2 局部搜索

模擬退火算法特性要求需要較高的初始溫度和較慢的溫降速率等特點(diǎn)，并且如果參數(shù)選取不當(dāng)會陷入局部最優(yōu)。故避免這種情況的發(fā)生在算法中引入了兩種局部搜索方法，具體如下:

(1)個體調(diào)換的局部搜索。個體調(diào)換的局部搜索步驟如下：①在當(dāng)前解的序列中隨機(jī)選取兩個位置a、b，調(diào)換a、b的位置得到一個新的序列。②對這個新的序列進(jìn)行解碼并計(jì)算其適應(yīng)度值，若適應(yīng)度高于舊序列則替換舊序列，否則仍用舊序列。③返回①繼續(xù)操作。直到達(dá)到終止條件。

(2)局部顛倒的局部搜索。局部顛倒的局部搜索步驟如下：①在當(dāng)前解的序列中隨機(jī)選取兩個位置a、b，顛倒a、b之間的序列得到一個新的序列。②對這個新的序列進(jìn)行解碼并計(jì)算其適應(yīng)度值，若適應(yīng)度高于舊序列則替換舊序列，否則仍用舊序列。③返回①繼續(xù)操作。直到達(dá)到終止條件。

2.3 算法流程

參數(shù)初始化，包括設(shè)置初始溫度T0、溫降速率q、結(jié)束溫度Te、以及迭代步長L。改進(jìn)的模擬退火算法的流程圖如圖2所示。

圖2 改進(jìn)模擬退火算法流程圖

3 實(shí)例仿真實(shí)驗(yàn)

某制造車間生產(chǎn)過程可以簡化為一個6個工件在6臺機(jī)器上加工的柔性作業(yè)車間調(diào)度問題。在制定生產(chǎn)調(diào)度計(jì)劃的時候需要考慮到最大完工時間和碳排放量這兩個目標(biāo)。該制造車間的加工數(shù)據(jù)如表3所示，其中第一列代表工件，第二列代表工序，之后的代表該工序可以在哪臺機(jī)器上加工，有數(shù)字的代表該機(jī)器可以加工該工序，沒有數(shù)字的代表該工序不能再這臺機(jī)器上加工。例如：O11不可以在第一臺機(jī)器上加工，可以在第6臺機(jī)器上加工，加工時間為15，單位時間的碳排放為1.1。

表3 實(shí)例數(shù)據(jù)

本文算法采用Matlab編程實(shí)現(xiàn)，其中初始溫度T0=1000、溫降速率q=0.98、迭代步長L=200、終止溫度Te=0.001。實(shí)驗(yàn)結(jié)果分為三個部分：兩種編碼方式的運(yùn)行時間、兩種局部搜索方式的優(yōu)劣度和不同權(quán)重系數(shù)下生產(chǎn)調(diào)度最優(yōu)結(jié)果。

3.1 兩種不同編碼方式的運(yùn)行時間

采用上文提及的兩種不同的編碼方式分別運(yùn)行該實(shí)例，通過20次的運(yùn)行去取平均運(yùn)行時間。具體如4所示。從表4可以清楚看到采用輪盤賭的編碼方式可以大大減少該算法的運(yùn)行時間。

表4 不同編碼方式的運(yùn)行時間

3.2 兩種不同的局部搜索的優(yōu)劣度

采用個體調(diào)換和局部顛倒的兩種不同的局部搜索方式，其它的參數(shù)完全相同，進(jìn)行20次的仿真運(yùn)行，結(jié)果如圖3所示。

圖3可以看出采用個體調(diào)換的局部搜索方式所對應(yīng)實(shí)線位于采用局部顛倒的局部搜索方式對應(yīng)的虛線下方。根據(jù)公式(3)可以知道當(dāng)適應(yīng)值越低，方案越優(yōu)越。故可以得到采用個體調(diào)換的局部搜索優(yōu)于局部調(diào)換的局部搜索。

圖3 兩種局部搜索適度值折線圖

3.3 不同權(quán)重系數(shù)的調(diào)度結(jié)果

依據(jù)上面所得到的結(jié)果，采用輪盤賭編碼方式以及個體調(diào)換的局部搜索，分別對3種不同情況進(jìn)行求解，如表5所示。圖4～圖6為不同方案的調(diào)度甘特圖。圖中橫坐標(biāo)代表完工時間，縱坐標(biāo)代表機(jī)器號，O1,2、O4,1代表第一個工件的第二道工序，第四個工件的第一道工序。

表5 不同權(quán)重系數(shù)的目標(biāo)值

方案1代表生產(chǎn)工廠在碳排放量滿足國家要求的情況下，側(cè)重最大完工時間對應(yīng)的調(diào)度甘特圖為圖4。從圖4得出：為了縮短加工時間，工序安排盡可能分散，使機(jī)器的利用率達(dá)到最大。方案2代表生產(chǎn)工廠對最大完工時間和碳排放重視力度一樣，對應(yīng)的調(diào)度甘特圖為圖5，從圖5得出：工序分布比較分散，故加工時間較長。機(jī)器6處理的工序較多，故機(jī)器6能耗較低。方案3代表生產(chǎn)工廠重視節(jié)能環(huán)保故需要犧牲完工時間，對應(yīng)的調(diào)度甘特圖為圖6。 從圖6得出：為了降低碳排放，花費(fèi)的大量的加工時間，故工序分布非常分散，并且機(jī)器的使用率分布不均。

綜上，決策者可以依托本文算法，根據(jù)生產(chǎn)實(shí)際情況，對目標(biāo)設(shè)置不同權(quán)重系數(shù)，從而得到最優(yōu)的調(diào)度方案。

圖4 方案1調(diào)度甘特圖

圖5 方案2調(diào)度甘特圖

圖6 方案3調(diào)度甘特圖

4 結(jié)論

對具有低碳要求的柔性車間資源調(diào)度問題進(jìn)行分析，建立了以最大加工時間和碳排放量為優(yōu)化目標(biāo)的調(diào)度模型。并提出了一種基于改進(jìn)模擬退火算法的調(diào)度策略，改進(jìn)了模擬退火算法的編碼方式和局部搜索方式，從而降低了算法的運(yùn)行時間。最后以車間生產(chǎn)實(shí)際案例為背景，通過設(shè)置不同的權(quán)重系數(shù)代表不同的工廠對生產(chǎn)目標(biāo)的要求，生成不同的調(diào)度方案。實(shí)驗(yàn)結(jié)果證明本文所提出的基于改進(jìn)模擬退火算法的調(diào)度策略在實(shí)際車間資源調(diào)度中是可行的。

[1] 姚立國,黃海松,田野,等. 云模式的機(jī)床供應(yīng)鏈運(yùn)作流程建模與計(jì)算[J]. 組合機(jī)床與自動化加工技術(shù),2017(2):108-111.

[2] 朱夏,李小平,王茜.基于總空閑時間增量的無等待流水調(diào)度混合遺傳算法[J].計(jì)算機(jī)研究與發(fā)展,2011,48(3):455-463.

[3] 張騰飛,馬躍,胡毅,等.基于遺傳算法的多目標(biāo)車間調(diào)度問題的研究[J].組合機(jī)床與自動化加工技術(shù),2016(5):43-45,50.

[4] 劉韻,胡毅,羅企,等.一種解決柔性車間作業(yè)調(diào)度問題的粒子群優(yōu)化算法[J].組合機(jī)床與自動化加工技術(shù),2015(12):144-147.

[5] 周鑫,馬躍,胡毅.求解車間作業(yè)調(diào)度問題的混合遺傳模擬退火算法[J].小型微型計(jì)算機(jī)系統(tǒng),2015(2):370-374.

[6] Laarhoven P J M V,Aarts E H L,Lenstra J K.Job Shop Scheduling by Simulated Annealing[J].Operations Research,1992,40(1):113-125.

[7] Dai M,Tang D,Giret A,et al.Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm[J].Robotics and Computer-Integrated Manufacturing,2013,29(5):418-429.

[8] 蔣增強(qiáng),左樂.低碳策略下的多目標(biāo)柔性作業(yè)車間調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng),2015, 21(4):1023-1031.

[9] Xia W,Wu Z.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems[J].Kongzhi Yu Juece/control & Decision, 2005,48(2):409-425.

[10] 張其亮,陳永生.基于混合粒子群-NEH算法求解無等待柔性流水車間調(diào)度問題[J].系統(tǒng)工程理論與實(shí)踐,2014,34(3):802-809.

[11] 劉愛軍,楊育,邢青松,等.多目標(biāo)模糊柔性車間調(diào)度中的多種群遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(9):1954-1961.

[12] 梁旭,黃明,常征.求解車間調(diào)度問題的一種新遺傳退火混合策略[J].計(jì)算機(jī)集成制造系統(tǒng),2005,11(6):851-854.

[13] 向萬里,馬壽峰.基于輪盤賭反向選擇機(jī)制的蜂群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(1):86-89.