柔性作業(yè)車間差分退火調(diào)度優(yōu)化算法研究

覃 斌,宋文廣,張秋娟,尹 強(qiáng),高子召, Yu Qian

(長江大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,湖北 荊州 434023)

在科技與制造行業(yè)急速發(fā)展的現(xiàn)今,各企業(yè)的生產(chǎn)制造流程也在不斷優(yōu)化。生產(chǎn)調(diào)度問題長期以來一直是制造系統(tǒng)的熱門問題,其理論研究也是最為艱難跨越的障礙之一。調(diào)度的任務(wù)是由生產(chǎn)目標(biāo)和約束,來為工件明確合適的加工時(shí)間、路線、器械和順序等[1]。該研究不僅能改善效率,提高企業(yè)競(jìng)爭(zhēng)力,同時(shí)還能降低能耗,實(shí)現(xiàn)制造業(yè)的綠色發(fā)展。柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)作為傳統(tǒng)車間調(diào)度的擴(kuò)展,更加符合實(shí)際生產(chǎn)中的制造環(huán)境,增強(qiáng)了生產(chǎn)調(diào)度的靈活性。同時(shí)FJSP比傳統(tǒng)作業(yè)車間調(diào)度問題更為復(fù)雜,不僅需要對(duì)工序加工的順序進(jìn)行排序,還要給工序分配機(jī)器,因此被歸為NP-hard類問題[2]。

雖然FJSP的復(fù)雜性眾所皆知,但是為了適應(yīng)發(fā)展趨勢(shì),許多學(xué)者還是致力于FJSP的研究。張凱等[3]構(gòu)建了一種將柔性作業(yè)車間調(diào)度問題轉(zhuǎn)化為馬爾可夫決策過程的方式,并提出集成5種DQN優(yōu)化的算法D5QN求解FJSP;張博等[4]提高了粒子群算法在求解FJSP中獲取最優(yōu)解的速度;Escamilla等[5]提出了一種新的元啟發(fā)式算法(global-local neighborhood search algorithm,GLNSA),同時(shí)結(jié)合禁忌搜索算法(tabu search, TS),完成了對(duì)FJSP的優(yōu)化;Danial[6]等提出了一種高效的兩階段遺傳算法(2SGA)求解FJSP,效率相對(duì)傳統(tǒng)遺傳算法有很大的提升;王玉芳等[7]以優(yōu)化最大完工時(shí)間為目標(biāo),提出一種自適應(yīng)灰狼優(yōu)化算法(adaptive grey wolf optimization, AGWO)求解該問題。

差分進(jìn)化算法(differential evolution algorithm,DE)是一種快捷有效的智能優(yōu)化算法[8],它基于群體差異的啟發(fā)式隨機(jī)搜索,受控參數(shù)少、魯棒性強(qiáng),具有較強(qiáng)的全局收斂能力和穩(wěn)健性。但是差分進(jìn)化算法在柔性作業(yè)車間問題中,尋優(yōu)的速度較慢,而且比較容易陷入局部最優(yōu)解中[9],因此本文提出了一種改進(jìn)的差分進(jìn)化算法(improved differential evolution-simulated annealing algorithm,IDESA)來求解FJSP,此算法在改進(jìn)的差分進(jìn)化算法的基礎(chǔ)上,加入模擬退火操作以提高算法的尋優(yōu)能力。

1 FJSP模型設(shè)計(jì)

1.1 FJSP的描述

FJSP是指在一個(gè)生產(chǎn)系統(tǒng)中,有一個(gè)機(jī)器集合,該集合中有m臺(tái)可以用來加工的機(jī)器。這個(gè)機(jī)器集合可表示為M=(M1,M2,...Mm)。同時(shí)有一個(gè)由需要加工的工件所組成的工件集J=(J1,J2,...Jn),其中的每一個(gè)工件要經(jīng)歷p道加工程序,將這些加工程序記為P=(P1,P2,...,Pn),其中每道程序都將會(huì)在M中的一臺(tái)或多臺(tái)機(jī)器上進(jìn)行加工,不同機(jī)器的選擇將致使加工需花費(fèi)的時(shí)間不盡相同。FJSP需要解決的問題就是通過調(diào)度方法選擇最優(yōu)的一條加工順序,及每道工序加工的設(shè)備,在滿足約束條件的情況下達(dá)到最好的生產(chǎn)效益。表1是一個(gè)FJSP示例。

表1 4×4完全柔性作業(yè)車間調(diào)度示例

1.2 FJSP的符號(hào)表示

在FJSP中,各個(gè)實(shí)體及操作等將會(huì)采用統(tǒng)一的符號(hào)進(jìn)行表示,下文中所涉及的符號(hào)如表2所示。

表2 統(tǒng)一符號(hào)表示

1.3 FJSP的約束條件

FJSP中一系列的條件約束將最終的結(jié)果導(dǎo)向?qū)嶋H環(huán)境中我們想要達(dá)到的優(yōu)化效果。本文將以經(jīng)典的最大完工時(shí)間最小化問題來建立約束條件。

sjk+Pijk×tijk≤eij

(1)

ejk≤sj(k+1)

(2)

公式(1)和公式(2)表示在工件加工的過程中,必須按照固定的工件加工順序來進(jìn)行,前一個(gè)工序未執(zhí)行之前不允許跳過此工序加工下一個(gè)工序。

Ej≤Emax

(3)

公式(3)約束了每一個(gè)工件加工的完成時(shí)間,不能超過所有工件完成以后總的完工時(shí)間。

sjk+tijk≤sln+H(1-Qjklni)

(4)

ejk≤sj(k+1)+H(1-Qlnj(k+1)i)

(5)

公式(4)和公式(5)表示在相同的時(shí)間點(diǎn),一個(gè)機(jī)器只能加工某一個(gè)工件的一道工序,此時(shí)此工件獨(dú)占此臺(tái)機(jī)器。

(6)

公式(6)約束了在相同的時(shí)間點(diǎn)上,同一道工序只能被一臺(tái)機(jī)器加工。同時(shí)需要保證sjk,ejk的取值必須大于等于0。

不同的生產(chǎn)環(huán)境優(yōu)化目標(biāo)也有所不同,當(dāng)前已有眾多學(xué)者針對(duì)不同優(yōu)化目標(biāo)做出了研究,如趙詩奎等[10]研究基于極限調(diào)度完工時(shí)間(Climit)最小化的機(jī)器選擇方式,陳廣鋒等[11]選擇全局最小負(fù)荷為目標(biāo)求解FJSP。由于本文的目標(biāo)是對(duì)加工時(shí)間進(jìn)行縮減,所以目標(biāo)函數(shù)是在最大完工時(shí)間的基礎(chǔ)上使其最小化:

minEmax=min{max{maxEi}}

(7)

2 差分進(jìn)化算法的優(yōu)化

2.1 差分進(jìn)化算法改進(jìn)

本文將在差分進(jìn)化算法中加入模擬退火操作。模擬退火算法有著較強(qiáng)局部極值逃脫能力和不依賴初值的特點(diǎn),但整體搜索能力較弱;而差分進(jìn)化算法作為隨機(jī)的啟發(fā)式搜索算法,全局尋優(yōu)的能力更具優(yōu)勢(shì)。

2.2 算法優(yōu)化流程

2.2.1 編碼方式

單一的編碼方式很難獲取最優(yōu)解[12],因?yàn)镕JSP在給加工工序排序的同時(shí)還要給工序分配可加工機(jī)器,問題的可行解需要確定工序先后順序的編碼和給工序分配機(jī)器的編碼兩部分,因此采用雙層編碼,如圖1所示。

圖1 編碼方式

以表1為例,假如工序O11、O12、O13、O21、O22、O23、O31、O32、O41、O42的加工順序?yàn)镺23-O32-O13-O21-O12-O42-O41-O11-O31-O22,那么工序編碼為[2,3,1,2,1,4,4,1,3,2]T;假如工序O11、O12、O13、O21、O22、O23、O31、O32、O41、O42對(duì)應(yīng)的加工機(jī)器為M2、M4、M2、M1、M3、M2、M4、M1、M1、M3,那么機(jī)器編碼則為[2,4,2,1,3,2,4,1,1,3]T。每個(gè)工件的工序數(shù)目是確定的,而工序編碼只是負(fù)責(zé)記錄工件的加工順序,因此編碼具有唯一性。

2.2.2 種群初始化

初始種群的質(zhì)量直接影響算法的收斂速度和性能,初始種群質(zhì)量越好,DE算法的效果越顯著。在大部分DE算法中,初始化種群一般會(huì)采取完全隨機(jī)的初始化方式,該方式雖然能夠較好的實(shí)現(xiàn)了隨機(jī)性和多樣性,但是得到的初始解質(zhì)量大多都偏低,可能需要進(jìn)化更多的代數(shù)才能計(jì)算出理想解。

本文對(duì)工序碼采取隨機(jī)生成的初始化方式,而對(duì)機(jī)器碼則使用輪盤賭的初始化策略。初始化策略如下:

步驟1 首先,隨機(jī)生成工序碼。

步驟2 對(duì)于生成碼中的每道工序,取出能對(duì)其處理的機(jī)器集。

步驟3 將相應(yīng)機(jī)器上各工序加工的時(shí)間,取倒數(shù),累加得到總概率。

步驟4 計(jì)算每臺(tái)機(jī)器的時(shí)間占總時(shí)間的概率,作為被選擇的概率。

步驟5 每道工序?qū)?yīng)的各機(jī)器的被選擇概率隨機(jī)生成該工序加工機(jī)器的機(jī)器號(hào)。

通過這種方式可以得出,機(jī)器加工工序的時(shí)間越長,則其被選中的概率越小,反之,其被選中的概率就越大。這樣不僅保證了隨機(jī)性和多樣性,也提高了初始種群的質(zhì)量,為之后的進(jìn)化步驟提高了效率和準(zhǔn)確率。

2.2.3 變異

(8)

2.2.4 交叉

(9)

式中:Cr表示交叉概率,p是在區(qū)間[1,D]上的隨機(jī)整數(shù)。

2.3.5 模擬退火操作

在經(jīng)過變異、交叉操作之后不再進(jìn)行差分進(jìn)化算法的選擇過程,而是通過模擬退火算法Metropolis[13]準(zhǔn)則進(jìn)行選擇,判斷是否接受實(shí)驗(yàn)向量,然后再繼續(xù)模擬退火的降溫操作,依次往返執(zhí)行到模擬退火規(guī)則下的終止條件,輸出結(jié)果。求解步驟如下:

1)設(shè)置開始溫度Ts和結(jié)束溫度Te。

2)當(dāng)溫度參數(shù)T=T0時(shí),在可行解的空間內(nèi)生成一個(gè)新解,新解產(chǎn)生公式為:

Xnew=Xold?Random

(10)

式中:Xnew為新解,Xold為執(zhí)行交叉變異后的個(gè)體,Random為一個(gè)隨機(jī)的擾動(dòng)向量。

3)計(jì)算新解的適應(yīng)度f(Xnew),以及新解和原始解之間的適應(yīng)度差值ΔE=f(Xnew)-f(Xold),然后以概率p=exp(-ΔE/T)確定是否選擇該新個(gè)體進(jìn)入下一代,最后執(zhí)行退溫操作。重復(fù)上述過程到滿足條件后產(chǎn)生下一代種群個(gè)體。

IDESA算法完整流程如圖2所示:

圖2 IDESA算法流程

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

本節(jié)實(shí)驗(yàn)在Windows11 64bit的個(gè)人筆記本電腦上運(yùn)行,CPU為Intel(R) Core(TM) i9-12900 H、內(nèi)存為16 GB。

為了測(cè)試算法在柔性作業(yè)車間調(diào)度問題求解中的性能,選取Brandimarte[14]給出的10組柔性作業(yè)車間調(diào)度算例(mk01～mk10),這些算例通常被用來測(cè)試算法的性能。本次實(shí)驗(yàn)的種群規(guī)模設(shè)置為50,最大進(jìn)化代數(shù)設(shè)置為500。通過測(cè)試將變異概率和交叉概率設(shè)置為0.1,模擬退火操作的初始溫度為100 ℃,終止溫度為1 ℃,以Tk=0.9Tk+1執(zhí)行降溫操作。與比較的算法各自獨(dú)立運(yùn)行10次,與本文算法相比較。各算法的最優(yōu)解如表3所示。

表3 Brandimarte算例測(cè)試結(jié)果對(duì)比

式中:n表示工件數(shù),m表示機(jī)器數(shù),p表示工序數(shù),將本文算法分別與差分進(jìn)化算法(DE)、模擬退火算法(SA)和粒子群算法(PSO)進(jìn)行對(duì)比。可以看出,本文算法結(jié)合了差分進(jìn)化算法和模擬退火算法的優(yōu)勢(shì),隨著問題規(guī)模的增大,尋優(yōu)能力明顯優(yōu)于其他三種算法。圖3給出了四種算法在Mk02問題中最優(yōu)解的收斂情況。

圖3 Mk02問題全局最優(yōu)解收斂圖

由圖3可以看出,IDESA算法中新的種群初始化方式大大提高了初始解的質(zhì)量,同時(shí)在加入模擬退火操作后,種群迭代到380代左右時(shí),并沒有像傳統(tǒng)的差分進(jìn)化算法一樣陷入局部極值,而是能夠跳出局部最優(yōu)解,尋優(yōu)能力明顯提高。圖4給出了Mk02問題的最優(yōu)調(diào)度甘特圖。

圖4 Mk02問題最優(yōu)甘特圖

通過實(shí)驗(yàn)可得出,IDESA算法能夠提升求解速度,又不會(huì)陷入局部最優(yōu)。針對(duì)在處理柔性作業(yè)車間調(diào)度的問題上,調(diào)度效率提升的同時(shí),也保證了分配結(jié)果的最優(yōu)性。

4 結(jié)束語

本文設(shè)計(jì)出一種改進(jìn)的差分算法并結(jié)合模擬退火算法解決柔性作業(yè)車間調(diào)度問題。通過特殊的雙層編碼方式,以及種群初始化方式和DE/best/1變異方式,提高了差分進(jìn)化算法的全局搜索能力,同時(shí)在算法的選擇階段中與退火操作結(jié)合,彌補(bǔ)了DE算法局部搜索的缺陷。最后使用Brandimarte標(biāo)準(zhǔn)算例進(jìn)行了驗(yàn)證,FJSP中的最大完工時(shí)間得到有效縮短,且保證了調(diào)度分配質(zhì)量,證實(shí)了本文算法的優(yōu)勢(shì)與可行性。

本文驗(yàn)證了以最小化最大完工時(shí)間作為優(yōu)化目標(biāo)的結(jié)果,在實(shí)際生產(chǎn)制造中,還需要考慮運(yùn)輸時(shí)間、機(jī)器損耗、加急工件等各種情況,因此后續(xù)將繼續(xù)研究多目標(biāo)、高緯度情況下的FJSP。