混合鯨魚優化算法求解柔性作業車間調度問題①

李寶帥,葉春明

(上海理工大學 管理學院,上海 200093)

隨著生產技術的發展與制造業內在需求的變化,制造業正在向著智能制造的方式轉變,作為產品生產制造中重要一環,車間調度問題得到了極大關注.柔性作業車間調度問題(flexible job-shop scheduling problem,FJSP)作為經典作業車間調度問題(job-shop scheduling problem,JSP)的延伸被認為是NP-難問題,相較于JSP 具有更高靈活性與求解難度.如今智能制造是制造業主要發展方向,制造系統的高效運行是智能制造主要要求之一.FJSP 具有工序排序與機器選擇兩個子問題,其求解更具復雜性,同時也更貼近實際車間生產制造情況,為尋求高效求解方法,對于FJSP 的求解方法具有廣泛的研究.目前對FJSP 的求解方法主要集中于元啟發式算法.張超勇等[1]對遺傳算法進行改進,改變了染色體的表示方式,結合多種策略生產高質量初始種群等多種操作,在基準問題上進行驗證;Li 等[2]將禁忌搜索算法策略嵌入到遺傳算法中,綜合利用二者的尋優能力,為更好平衡算法的勘探與開發,通過與其他算法進行對比實驗,改進的混合算法具有顯著改進;仲于江等[3]利用改進的粒子群算法對多目標FJSP 進行研究,利用小生境技術更新解集避免算法陷入局部最優,并改進最優解的選擇方式,在算例與車間仿真實驗中驗證改進算法可行性.

隨著計算機科學技術發展,新式元啟發式算法不斷涌現,如灰狼優化算法[4],人工蜂群算法[5]等,學者利用新興的元啟發式算法對FJSP 進行進一步研究,Lu 等[6]設計了一種改進的多目標混合灰狼優化算法,在算法中嵌入遺傳算子增強全局搜索能力,在多目標動態調度模型中與其他經典算法進行比較,體現改進算法的優越性;Karthikeyan 等[7]針對有限資源約束下的多目標FJSP,考慮3 個最小化目標,結合鄰域結構的局部搜索方法,提出一種混合螢火蟲算法并將其離散化應用于多目標FJSP;姜天華[8]采用兩段式編碼方式將改進的灰狼優化算法應用于FJSP,引入變鄰域搜索方法與遺傳算法中交叉和變異算子的方式提高算法勘探能力在基準與隨機算例中與其他算法進行對比,數據證明改進算法;王玉芬等[9]針對FJSP,對人工蜂群算法進行改進,在搜索階段利用IPOX 與多點交叉方法避免產生非法解,通過增加偵察蜂的數量保持全局搜索能力,且用貪婪策略保留較優解,在算例上驗證改進算法的有效性與收斂性;Li 等[10]針對FJSP,提出了一種基于禁忌搜索的混合人工蜂群算法來求解,并使用聚類分組輪盤賭的方式來初始化種群,同時為提高種群質量,在計算過程中引入交叉算子,在基準算例上與其他算法進行比較并證明了算法有效性;劉雪紅等[11]對候鳥算法做出改進,使用精英分批策略提高算法性能,使其應用于FJSP,解決最小完工時間與最小批次數目的多目標FJSP.綜上,學者基于元啟發式算法解決FJSP 進行了廣泛研究.

鯨魚優化算法(whale optimization algorithm,WOA)[12]是一種基于種群的元啟發式算法,已應用于模型預測[13],參數優化等方面[14],WOA 具有獨特的搜索機制,其應用參數少,算法整體穩定性高,尋優能力較強[15],元啟發式算法在解決車間調度問題方面具有一定優勢,WOA 作為元啟發式算法的一種,同樣應用于在車間調度應用的方面,閆旭等[16]首先將WOA 應用于車間調度問題,利用量子計算方式改進的WOA求解JSP;張斯琪等[17]提出一種改進的WOA 優化單目標的FJSP.為進一步豐富FJSP 的求解算法,對FJSP求解進行深入研究,本文首先利用非線性收斂因子與正余弦算法對WOA 進行改進,提出一種混合正余弦鯨魚優化算法(sine cosine whale optimization algorithm,SCWOA),并應用SCWOA 求解以最小化最大完工時間的FJSP.

1 問題描述

FJSP 是經典JSP 的擴展,其問題可以描述為:假設在車間內n個工件(J1,J2,···,Jn)需在m臺機器(M1,M2,···,Mm)上進行加工,每個工件Ji包含一個以上工序,工序按預定順序進行加工.使用Oij表示工件Ji的第j道工序,Mij表示可加工工序的機器集合,工序可在具備處理能力的機器上進行加工.工序Oij在不同機器上的加工時間不同.FJSP 的調度目標是為Oij選擇機器進行加工,同時對機器上各個待加工工件工序進行排列以確定加工時間,平衡各性能指標以達到最好方案.

FJSP 的目標是在一定的約束條件下對工件和機器按時間進行分配并安排加工次序,使得加工性能指標達到最優.

本文評價目標是最大完工時間最小,目標函數可表示為:

式中,Cj為工件最后完成時間,n為工件數.

2 基本算法描述

2.1 鯨魚優化算法

WOA 的設計源于鯨魚群的捕食行為.在鯨魚群體中,其捕食行為常常伴隨著個體之間的合作,鯨魚群捕食行為中最特別之處是氣泡網捕食行為,即鯨魚群在發現獵物之后,會以螺旋路徑逐漸包圍獵物,將獵物活動范圍逐漸縮小,最終捕食獵物[12].WOA 從鯨魚群獨特的捕食行為中進行研究,通過仿效鯨魚群捕食的方式,從搜索、包圍、捕食獵物3 個方面建立數學模型,模擬算法尋優過程.

2.1.1 包圍獵物階段

WOA 模仿鯨魚群協同捕食方式,會有多個鯨魚個體對獵物進行包圍捕獵,算法在開始時設置一組隨機解并計算解的適應度,同時將適應度最高的解視作目標,其余鯨魚個體會向目標靠攏接近,其位置更新方式可以表示為:

式中,X*為獵物位置,t為迭代次數,A,C為系數,其計算方式為:

其中,a隨迭代次數增加從2 線性下降為0,r∈[-1,1]的隨機數.

2.1.2 氣泡網捕食

鯨魚群在進行捕食時會沿著圓形或“9”形的路徑捕食獵物,為模仿這種捕食方式,WOA 設置兩種方法進行模仿,第1 種為個體收縮環繞機制,這一機制通過a的線性降低來實現,由式(4)可知,A的值也會隨a的減小而減小,當a的值在[-1,1]時,鯨魚個體會對目標獵物進行收縮環繞行為.第2 種為鯨魚個體螺旋形位置更新,WOA 首先計算鯨魚個體與捕獵目標之間距離,然后在二者之間建立一個螺旋方程,模擬鯨魚個體的螺旋形運動方式[17],公式為:

式中,D′為鯨魚個體與獵物之間的距離,b為定義螺旋形狀的常數,l為[-1,1]之間的隨機數.WOA 通過這兩種機制模擬整個鯨魚群捕食路徑,為模擬同時發生的兩種行為,設置WOA 分別以50%的幾率進行收縮環繞機制或螺旋更新機制,公式如下:

其中,p為[0,1]之間的隨機數.

2.1.3 尋找獵物階段

為進一步尋找獵物,WOA 利用A的變化來進行探索,即|A|＜1時算法會進行精確搜索,鯨魚個體會向當前最優個體進行移動,與開發階段不同,當A的隨機值大于1 或小于-1 時,鯨魚個體會遠離當前獵物并且根據一個隨機鯨魚個體來更新自己的位置,位置更新公式如下:

其中,Xrand為隨機選取的鯨魚個體的位置.

WOA 從一組隨機解開始.在每次迭代中,鯨魚個體會根據隨機選擇的鯨魚個體位置或當前最優個體位置更新自身的位置,當|A|＞1時,鯨魚群進行隨機搜索,|A|＜1時,每個鯨魚個體會依據獵物位置更新本身所處位置,以此來進行勘探與開發;同時根據p的隨機取值,選擇對數螺旋方式或收縮環繞方式靠近捕獲獵物,WOA 會在達到最大迭代次數時結束.元啟發式算法作為求解FJSP 的有效手段,其中WOA 作為眾多元啟發式算法的一種,本身具備較強的搜索能力,在函數求解方面的穩定性與求解精度強于大部分元啟發式算法,但同時也具有元啟發式算法共有的易陷入局部最優等的缺點[18].因此本文在引入非線性收斂因子與正余弦算法策略對WOA 進行改進,并應用于FJSP 的求解.

2.2 正余弦算法

正余弦算法(sine cosine algorithm,SCA)由Mirjalili 在2016年提出[19],SCA 算法的主要思想是在算法尋優過程中綜合使用正弦函數與余弦函數來進行勘探與開發,通過正余弦函數的周期性變化實現勘探與開發.SCA 算法首先隨機創建一組初始解,然后根據正余弦函數進行迭代更新位置,尋找最優解,其位置更新公式可以表示為:

其中,Xt是在第t次迭代時個體的位置,pt表示在第t次迭代時適應度最高的個體所處位置,SCA 控制參數包括r1、r2、r3、r4,其中r1的表示公式如下:

其中,k為常數,t為當前迭代次數,T為最大迭代次數;r2∈[0,2π],r3∈[0,2π],r4∈[0,1],均為隨機數.在SCA算法中,r1確定個體下一次更新的運動方向;r2確定個體的移動距離;r3是當前最優個體位置的一個權重,若r3＞1表示增大當前最優個體位置對其他個體改變的影響,若r3＜1表示減弱當前最優個體位置對其他個體改變的影響;r4代表隨機選擇正余弦函數.在4 個參數中,r1的取值對SCA 全局探索與局部開發之間的平衡影響較大,r1＞1時,函數r1sin(r2)與r1cos(r2)的值會大于1 或小于-1,此時個體會遠離當前的最優個體,算法會探索更加廣闊的求解區域,保證算法全局探索能力;當r1≤1時,函數r1sin(r2)與r1cos(r2)的值會處于-1 到1 之間,此時個體會逐漸向當前最優個體移動,算法會對區域內進行進一步精確搜索,保證算法進行良好的局部開發.SCA 在正弦余弦函數中利用自適應參數平滑實現從全局探索到局部開發,能夠將全局探索和局部開發有效結合起來.

3 混合正余弦鯨魚優化算法

3.1 編碼解碼

基于FJSP 的特性,設置基于機器分配與工序排序的兩段式向量進行編碼,分別對應FJSP 的兩個子問題,對于一個鯨魚個體向量X=(x1,x2,···,xn),將其分為長度相等兩段,滿足n=2l,l為FJSP 總工序數,第一段向量用于表示機器分配,第二段向量表示工序排序,并設置個體位置取值范圍為[-ε,ε],ε為FJSP 總工件數.假設存在一個3 個工件,每工件含2 道工序的調度問題,則可表示為兩段向量,每段向量長度為6,個體位置向量總長為12,個體位置元素的取值介于[-3,3]之間,如圖1所示是一段個體位置向量.

圖1 個體位置向量

3.1.1 編碼

首先對第一段機器分配向量進行編碼,參考文獻[20]的編碼方法,通過式(13)將鯨魚個體位置向量映射到當前可選機器集合的機器序號,從而完成個體位置轉換機器分配的過程.

其中,x(j)為鯨魚個體向量,s(j)為可選機器集合,u(j)為機器集合中的序號.如圖2 為第一段機器分配向量的轉換過程.

圖2 機器分配向量轉換

工序O11選擇可選機器集合中的序號2 機器即M3,工序O12選擇可選機器集合中序號1 機器即M1.

工序排序向量的編碼采用文獻[21]的最大位置值規則(largest position value,LPV)來實現,首先按照位置元素值的大小進行降序排列,之后依照這一排列順序實現工序順序的排列,最后確定工序順序.如圖3所示為第2 段向量的轉換過程.

圖3 工序排序向量轉換

3.1.2 解碼

解碼也包括機器分配與工序排序兩部分,機器分配向量向個體位置向量的轉換是公式的逆轉換,即:

若發生特殊情況,在可選集合中僅存在唯一一臺機器,即當s(j)為1 時,此時x(j)取值為[-ε,ε]之間的隨機數.

工序排序向量的解碼同樣依據LPV 規則,工序排序向量π(j)的轉換根據式(15)實現.

3.2 非線性收斂因子

任何群智能優化算法在尋優的過程中都存在全局探索與局部開發兩個階段,恰當平衡兩個階段,可使算法在初期尋優中探索更大范圍,同時提升其后期對于局部范圍的搜索精度,提升算法求解的整體準確性.WOA 的勘探與開發平衡主要由 |A|確定,又由式(4)可知 |A|是由收斂因子a的變化決定,收斂因子a的值較大時,|A|＞1,算法會處于全局探索階段,反之|A|＜1,算法會處于局部開發階段.針對SCA,其勘探與開發兩階段之間平衡主要取決于參數r1.

然而無論是WOA 收斂因子a還是SCA 參數r1都根據迭代次數由2 線性遞減至0,為適應WOA與SCA 的優化過程,因此本文提出一種非線性收斂因子調整策略,對WOA 的收斂因子a進行改進,其改進公式如下:

其中,t為當前迭代次數,T為最大迭代次數,λ ,μ都為常數.此種改進使得的值可以隨著迭代過程進行非線性變化,適應WOA 與SCA 的非線性優化過程.

如圖4所示為WOA 收斂因子與非線性收斂引子在迭代過程中的變化對比.非線性收斂因子相比標準WOA 的收斂因子,的值在其優化過程前期取值較大且遞減速度較慢,保證 |A|的取值較大,進而使得算法前期全局搜索范圍較大,適用于全局搜索,在后期取值較小且遞減速度加快,|A|的取值較小,算法在更小范圍內進行搜索,保證算法局部搜索精確性,提高算法搜索精度,同時可提高算法收斂速度.

圖4 收斂因子迭代對比

3.3 正余弦算法策略

SCA 利用正余弦函數的周期性變化實現尋優過程,這種位置更新方式使得算法勘探時會探索更大區域,局部開發時會在更小范圍內進行精確搜索,綜合利用SCA 的位置更新方式,將其應用于WOA 的位置更新與螺旋更新中,對WOA 進行改進,提高WOA 的整體尋優水平.標準SCA 參數r1作為平衡探索與開發的重要參數,其迭代變化也與WOA 中收斂因子類似,呈線性變化,這種線性變化無法充分發揮算法在探索、開發能力[22].因此同樣考慮對SCA 參數r1引入非線性收斂因子策略,對r1改進如式(17)所示,增強SCA 的全局探索能力與局部搜索能力.

3.3.1 改進鯨魚個體位置更新方式

WOA 全局探索能力依靠式(9)來實現,即通過隨機選擇鯨魚個體來確保算法的全局探索,這種隨機產生鯨魚個體的方法只有同時滿足p＜0.5 且|A|＞1 時,算法才會采用式(9)進入全局探索階段,過多的條件限制使得WOA 全局探索能力略顯不足,因此將SCA 與WOA 進行混合,利用SCA 的尋優方式,結合SCA 較強的全局探索能力,首先對WOA 的全局探索方式進行改進.利用控制參數為指數函數遞減的SCA 較原算法具有更高的計算精度,同時提高了算法的求解效率,因此結合非線性收斂因子策略,同時把式(11)引入WOA,對式(10)進行改進如下:

基于同樣考慮,把SCA 策略引入WOA 的局部開發過程中,提升算法的局部開發能力,對式(3)進行改進如下:

3.3.2 改進鯨魚個體螺旋更新方式

由式(6)可知,在WOA 中個體會一直以對數螺旋的軌跡方式進行位置更新,這種螺旋更新位置的方式雖然可以加快整體收斂速度,但是會導致群體內個體以較快速度聚合在一起,進而導致整個種群喪失多樣性,最終增大陷入局部最優的幾率.因此,為增強整個種群多樣性與跳出局部最優能力,同樣利用SCA 策略對螺旋更新方式實行改進如下:

其中,r3為[0,1]之間的隨機數,通過利用正弦螺旋更新運動與余弦螺旋更新運動的隨機發生,避免種群多樣性的快速丟失,使其從全局勘探平滑地過渡到局部開發,最終迭代收斂到最優解.

3.3.3 混合鯨魚優化算法流程與實施

混合正余弦鯨魚優化算法綜合非線性收斂因子與SCA 策略改進方式,提高算法全局勘探能力與局部開發能力,SCWOA 的框架如下:

(1)定義目標函數,設置算法參數,包括種群規模N,最大迭代次數T,設置t=1;

(2)進入主循環,根據適應度記錄最優個體位置,定義并更新非線性收斂引子參數設置依據式(16),式(17);

(3)定義并更新參數A,C,l,θ,r3,r4的值,A的數值依據式(4)所定,C為[0,2]內隨機值,l,θ,r4為[0,1]內隨機值,r3為[0,2π]內隨機值;

(4)判斷p＜0.5,若|A|≥0.5,采用式(18)更新個體位置;若|A|＜0.5,采用式(19)更新個體位置;

(5)判斷p≥0.5,采用式(20)更新個體位置;

(6)判斷t=T,若滿足進行步驟(7),否則返回步驟(2);

(7)輸出最優個體位置與目標函數最優解.

圖5 為SCWOA 流程圖.

圖5 SCWOA 運行流程

4 實驗分析

本文選取文獻[23]中BRdata 包含的10 個FJSP 標準調度實例(MK01-MK10),與文獻[24]中5 個標準調度實例(kacem01-kacem05)對SCWOA 實行實例驗證,SCWOA 由Python 3.7 實現,在Windows 10,Intel(R)Core(TM)i5-9300 CPU,2.4 GHz 主頻,16 GB 內存的系統上運行.算法參數設置種群為160,最大迭代次數為300.

首先對基本WOA 與SCWOA 進行實驗對比,以驗證非線性收斂因子與正余弦策略改進措施的有效性.為避免隨機性,算法共運行10 次,Time 表示算法的平均運行時間,Best 代表10 次運行結果中最優結果,Avg代表10 次實驗的平均優化結果.借鑒文獻[17]的對比方法加入提升率,其計算公式為(SCWOABest-WOABest)/SCWOABest,其用來表示SCWOA 相較于原算法的提升水平.其實驗對比結果如表1所示.

表1 WOA 與SCWOA 實驗對比結果

從表1 對比結果可知,SCWOA 相較WOA 在最優尋優結果與平均尋優結果方面都獲得了一定的提升,在8 個實例中優化結果得到了提升,并且最大提升效果達到了0.1,證明SCWOA 的改進措施有效.值得注意的是SCWOA 的時間復雜度也較WOA 有一定程度的提高.如圖6所示為SCWOA 在MK04 上的調度甘特圖,MK04 有8 個加工機器與15 個待加工工件,求解結果Cmax 為67,雖未達到最優調度結果,但調度結果仍優于大部分優化算法.

圖6 MK04 調度甘特圖

同時將SCWOA 與其他元啟發式算法進行實驗對比,對比算法包括基本遺傳算法、文獻[2]中的混合遺傳算法、文獻[8]的混合灰狼優化算法、文獻[24]與文獻[25],最優結果以粗體表示,對比結果如表2 與表3所示.

表2 SCWOA 與其他算法在Kacem 實驗對比結果

表2 對比結果表明文獻[24]在缺失2 個算例情況下獲得最優解有1 次,文獻[8]獲得最優解有4 次,文獻[25] 獲得最優解有3 次,SCWOA 獲得最優解有4 次.SCWOA 表現較好.表3 對比結果表明GA 獲得最優解有1 次,文獻[23]獲得最優解1 次,文獻[2]獲得最優解有4 次,文獻[8]獲得最優解5 次,SCWOA獲得最優解次數最多,并且SCWOA 的尋優能力在問題規模較大時相較于其他算法表現也較好,以上結果綜合表明SCWOA 應用于FJSP 的有效性.

表3 SCWOA 與其他算法在BRdata 實驗對比結果

5 結束語

本文以FJSP 的最大完工時間為優化目標,對WOA進行設計改進,提出了一種混合正余弦鯨魚優化算法.首先以兩段式編碼使鯨魚優化算法離散化,使其可應用于FJSP;加入非線性收斂因子策略;并加入SCA 的優化策略,改進鯨魚優化算法的位置變動方式,提高全局勘探與局部開發能力.通過與其他算法在BRdata 算例上的實驗對比,實驗對比結果證明了算法設計的有效性.下一步工作可將鯨魚優化算法應用于更加復雜的車間調度問題,如多目標FJSP,進一步豐富算法的應用范圍,并且可將綠色調度目標作為算法優化目標,響應國家碳中和、碳達峰政策.