改進灰狼算法求解多目標柔性作業(yè)車間調(diào)度問題

孫新宇

(上海理工大學機械工程學院，上海 200093)

807713550@qq.com

1 引言(Introduction)

柔性作業(yè)車間調(diào)度的概念是在1990 年BRUCKER和SCHLIE提出的，其作為經(jīng)典作業(yè)車間調(diào)度問題的進一步擴展，屬于一個典型的NP-hard問題，存在求解優(yōu)化的困難。不同于作業(yè)車間調(diào)度，柔性作業(yè)車間調(diào)度可以使每個作業(yè)在不同的機器上進行加工，也可以在機械設備出現(xiàn)故障時處理問題，并滿足不同加工需求的變化，更有利于提高生產(chǎn)效率，貼近現(xiàn)實具體的生產(chǎn)環(huán)境。按照求解目標，柔性作業(yè)車間調(diào)度問題可分為單目標和多目標，單目標一般的優(yōu)化目標為最大完工時間、機器空閑時間、總流動時間等，目前研究最多的是最大完工時間。多目標是將多個目標同時考慮，選擇最優(yōu)情況，更符合現(xiàn)實生產(chǎn)要求。

灰狼優(yōu)化算法(Grey Wolf Optimizer，GWO)是MIRJALILI等在2014 年觀察模仿狼群生活和狩獵方式提出來的一種基于群體的優(yōu)化搜索算法。該算法的搜索原理簡單、魯棒性較好、收斂性能較強、求解速度較快和參數(shù)較少。通過近些年的研究，其已經(jīng)很好地應用在車間調(diào)度問題的求解、圖像分類、參數(shù)優(yōu)化等領域。

灰狼算法較多用于解決連續(xù)函數(shù)方面的問題，對于柔性作業(yè)車間問題，特別是本文對多目標的優(yōu)化方面的應用還是較少。因此本文通過優(yōu)化初始種群，在此基礎上，與非支配排序算法結合，引入非支配排序與擁擠度，提出了一種解決多目標優(yōu)化問題的思路，并通過調(diào)度算例進行有效驗證。

2 問題描述(Problem description)

對柔性作業(yè)車間問題的描述如下：假設一個柔性作業(yè)車間有臺加工機器和個工件，不同機器會加工多種工件，每個工件的工序數(shù)量也不一定相同，每個工序的加工需要按照一定的先后順序進行，并且加工的時間也會各不相同。按照某些優(yōu)化目標，為每道工序分配合適的加工機器，并且每臺機器按照分配的任務進行順序加工，從而實現(xiàn)最優(yōu)化的目標安排。

對于柔性作業(yè)車間，還存在下面的假設條件：

(1)一臺機器某一時刻只能加工處理一個工件；

(2)所有工件在開始的零時刻都可以被加工；

(3)同種工件的工序一定要按照次序加工，不同工件的工序之間相互獨立；

(4)各個工件之間不存在加工的優(yōu)先級的差別；

(5)任意工序只要開始加工，就不能中斷；

(6)同一工件的同一道工序在同一時刻被加工的機器數(shù)是一。

3 模型建立(Model building)

把車間的最大完成加工時間、機器總耗能及總機器負荷作為優(yōu)化目標，建立柔性車間的多目標模型。

(1)最大加工完成時間最小化

加工完成時間是每個工件的最后一道工序完成的時間，當最后一個工件的最后一步工序結束時，加工零件所用時間最長的就是最大完工時間。在調(diào)度排產(chǎn)中，完工時間可以體現(xiàn)一個車間生產(chǎn)效率的高低，表示為

式中，表示最大完成加工時間；表示工件序號；表示工件總數(shù)；C表示每個工件的完成加工時間。

(2)機器總耗能最小化

總耗能是空載能耗與負載能耗之和，零時刻機器開工，能耗計算公式表示為

式中，表示機器序號；表示機器總數(shù)；表示速度擋位序號； d表示機器的速度擋位； E表示單位時間內(nèi)機器加工時的加工能耗；p表示工件以速度擋位在機器上的實際加工時間； x表示0或1變量，若工件在機器以速度擋進行加工則為1，否則為0；SE表示機器單位時間內(nèi)的平均空載能耗；MC表示機器的完成加工時間；W表示機器的總負載。

(3)總機器負荷最小化

在不同的調(diào)度安排下，機器的總負荷也會不同，所以在不同機器上同種工序花費的時間也不同，因此最小化機器的總耗能顯得很有必要，前提是最大完工時間最好一致，表示為

式中， h表示第個工件的工序總數(shù)； p表示第個工件的第道工序在機器上的加工時間； x為0或1變量，如果第個工件的第道工序在機器上加工則值為1，否則為0。

(4)上述假設條件的約束模型

式中， s為第個工件的第道工序加工開始的時間； c為第個工件的第道工序加工完成的時間；代表工序序號；表示不同于的工件序號； y為0或1變量，如果第臺機器上第個工件的第道工序先于該臺機器上第個工件的第道工序加工則為1，否則為0。

式(4)和式(5)表示工序加工時按照工件規(guī)定的次序；式(6)表示總的完工時間一定大于每個工件的完成加工時間；式(7)和式(8)表示一臺機器某一時刻只能加工處理一個工件的工序；式(9)表示工件的工序在任意時刻有且僅有一臺機器可以加工處理它；式(10)和式(11)表示車間中的任何一臺機器的操作是可重復的；式(12)表示各個變量不可小于零。

4 改進的灰狼算法(Improved GWO algorithm)

4.1 基本的灰狼算法

灰狼算法的數(shù)學模型由兩部分組成：包圍獵物的部分和獵殺獵物的部分。包圍獵物的數(shù)學公式如下：

獵殺獵物的數(shù)學模型如下：

4.2 初始化種群的改進

對于群智能優(yōu)化算法來說，好的初始化種群可以加快全局收斂的速度，以及尋找更精確的解，所以改進算法的初始種群，提高尋優(yōu)能力就顯得很有必要。在標準灰狼算法中，種群的多樣性無法保證，因為其采用隨機初始化的方法來初始種群。

本文采用了LUO等提出的復數(shù)值編碼的方法，初始化種群，并與工序結合，較好地提高了全局優(yōu)化的策略，尋找工序中最優(yōu)的分配，減少最大完工時間和機器耗能等。該方法為了提高種群的多樣性，引入了復數(shù)，因為復數(shù)包含實部和虛部，可以單獨分別更新，從而包含了更多的信息，進而增強了種群的多樣性。

4.3 非支配排序及擁擠度

為了解決柔性作業(yè)車間的多目標問題，標準的灰狼算法對于單目標問題，個體的優(yōu)劣比較容易判斷，但當涉及多目標問題時，就很難尋找目標。引入非支配排序遺傳算法中的非支配排序和擁擠度的概念，將每個個體按照它們的支配與非支配關系進行分層，再根據(jù)擁擠度，選出同級別中的優(yōu)解，保持了種群的多樣性，從而達到求解多目標問題的目標。

(1)在種群中尋找單獨的個體，這類個體不受上一級個體的控制影響，把它們放入集合中。

(2)對上述集合中的每個個體，找出受它影響控制的下一級個體集合，那么因為找出了一類上一級個體，集合中個體的受上一級影響數(shù)量需要減去一類。

(3)當該個體受上一級影響的數(shù)量減去1后值為0時，存入另一個集合中。那么集合中的個體都是非支配的，第一次分級找出的這些個體也被叫作第一級非支配個體。然后重復上面的操作，由集合開始分級，不斷進行下去，那么所有的個體都可以分級完成。

密度估計：對同一個前沿面的解集合按各個目標分量大小排序，計算每個解在該分量下的兩側點的距離差值，而后進行累加各個分量上的距離作為擁擠系數(shù)。

4.4 算法流程

圖1 算法步驟流程圖Fig.1 Flow chart of algorithm steps

步驟1：設置算法參數(shù)、種群大小及迭代次數(shù)。

步驟2：采用上文所述的復數(shù)值編碼的方法初始化種群。

步驟3：解碼得到加工時間、耗能和機器負荷，進行非支配排序和擁擠度計算。

步驟4：對擁擠度排序后，找出決策層的、和狼。

步驟5：更新每個灰狼個體的位置。

步驟6：計算更新后群體個體的適應度，再找出最優(yōu)的三條狼。

步驟7：判斷迭代次數(shù)是否滿足，是則轉到步驟8，否則轉到步驟5。

步驟8：算法結束，輸入結果。

5 實例結果與分析(Example results and analysis)

為了驗證上述模型和算法在解決FJSP問題方面的有效性，本文采用了Brandimarte中的基準算例MK10，算例中的工件數(shù)為20，機器數(shù)量為10。

以最小完工時間、最小機器負荷及最小機器耗能為目標，在柔性作業(yè)車間中，通過改進的灰狼算法進行甘特圖的排產(chǎn)安排，其中灰狼優(yōu)化算法的種群大小設置為100，最大迭代次數(shù)為100。最終優(yōu)化的三個目標結果圖如圖2、圖3和圖4所示；甘特圖排產(chǎn)的結果如圖5所示。

圖2 最小完工時間趨勢曲線Fig.2 Trend curve of the minimum completion time

圖3 最小機器負荷趨勢曲線Fig.3 Trend curve of the smallest machine load

圖4 最小機器耗能趨勢曲線Fig.4 Trend curve of the minimum machine energy consumption

根據(jù)運行結果，從圖2—圖4中可以看出收斂的所有零件完成加工的最小時間在510 分鐘左右，最小機器負荷為2，395 kW，最小機械總能耗為6，175 kW?？梢钥吹礁倪M后的灰狼算法可以較快收斂到最優(yōu)解，加入非支配排序和擁擠度后，該算法在解決三目標的優(yōu)化問題方面是有效的。

圖5 實例MK10的甘特圖Fig.5 Gantt Chart of example MK10

6 結論(Conclusion)

為了研究柔性作業(yè)車間多目標調(diào)度的優(yōu)化問題，本文采用改進的灰狼優(yōu)化算法，用復數(shù)值編碼的方式初始化種群，使用了非支配排序遺傳算法中的非支配排序和擁擠度，使得改進后的灰狼算法，也可以用于解決多目標優(yōu)化問題。

建立了關于完工時間、機械負荷和機械總能耗的數(shù)學模型，并用灰狼算法對模型進行驗證，結果表明改進后的灰狼算法可以較快地收斂，找到多目標的最優(yōu)解，說明了該算法的有效性。

本文研究的內(nèi)容都是在靜態(tài)調(diào)度的情況下，針對動態(tài)調(diào)度的情況沒有考慮，下一步需要考慮更多的現(xiàn)實問題和與其他智能隨機算法結合對比研究，獲得更高效的算法。