改進(jìn)模擬退火算法在柔性調(diào)度中的應(yīng)用*

黃海松，劉 凱，初光勇

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

0 引言

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

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

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

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

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

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

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

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

(1)

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

(2)

(3)評(píng)價(jià)函數(shù)

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

(3)

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

圖1 可行域方案集

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

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

2.1 編碼方法

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

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

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

(2)輪盤(pán)賭的個(gè)體編碼

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

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

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

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

(4)

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

2.2 局部搜索

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

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

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

2.3 算法流程

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

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

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

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

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

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

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

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

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

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

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

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

圖3 兩種局部搜索適度值折線(xiàn)圖

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

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

[5] 周鑫,馬躍,胡毅.求解車(chē)間作業(yè)調(diào)度問(wèn)題的混合遺傳模擬退火算法[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),左樂(lè).低碳策略下的多目標(biāo)柔性作業(yè)車(chē)間調(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算法求解無(wú)等待柔性流水車(chē)間調(diào)度問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐,2014,34(3):802-809.

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

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

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