覃 斌,宋文廣,張秋娟,尹 強,高子召, Yu Qian

(長江大學(xué) 計算機科學(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)和約束,來為工件明確合適的加工時間、路線、器械和順序等[1]。該研究不僅能改善效率,提高企業(yè)競爭力,同時還能降低能耗,實現(xiàn)制造業(yè)的綠色發(fā)展。柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)作為傳統(tǒng)車間調(diào)度的擴展,更加符合實際生產(chǎn)中的制造環(huán)境,增強了生產(chǎn)調(diào)度的靈活性。同時FJSP比傳統(tǒng)作業(yè)車間調(diào)度問題更為復(fù)雜,不僅需要對工序加工的順序進行排序,還要給工序分配機器,因此被歸為NP-hard類問題[2]。

雖然FJSP的復(fù)雜性眾所皆知,但是為了適應(yīng)發(fā)展趨勢,許多學(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),同時結(jié)合禁忌搜索算法(tabu search, TS),完成了對FJSP的優(yōu)化;Danial[6]等提出了一種高效的兩階段遺傳算法(2SGA)求解FJSP,效率相對傳統(tǒng)遺傳算法有很大的提升;王玉芳等[7]以優(yōu)化最大完工時間為目標(biāo),提出一種自適應(yīng)灰狼優(yōu)化算法(adaptive grey wolf optimization, AGWO)求解該問題。

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

1 FJSP模型設(shè)計

1.1 FJSP的描述

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

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

1.2 FJSP的符號表示

在FJSP中,各個實體及操作等將會采用統(tǒng)一的符號進行表示,下文中所涉及的符號如表2所示。

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

1.3 FJSP的約束條件

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

sjk+Pijk×tijk≤eij

(1)

ejk≤sj(k+1)

(2)

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

Ej≤Emax

(3)

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

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

(4)

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

(5)

公式(4)和公式(5)表示在相同的時間點,一個機器只能加工某一個工件的一道工序,此時此工件獨占此臺機器。

(6)

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

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

minEmax=min{max{maxEi}}

(7)

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

2.1 差分進化算法改進

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

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

2.2.1 編碼方式

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

圖1 編碼方式

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

2.2.2 種群初始化

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

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

步驟1 首先,隨機生成工序碼。

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

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

步驟4 計算每臺機器的時間占總時間的概率,作為被選擇的概率。

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

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

2.2.3 變異

(8)

2.2.4 交叉

(9)

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

2.3.5 模擬退火操作

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

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

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

Xnew=Xold?Random

(10)

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

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

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

圖2 IDESA算法流程

3 實驗

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

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

表3 Brandimarte算例測試結(jié)果對比

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

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

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

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

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

4 結(jié)束語

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

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