孫思漢，陶翼飛，董圓圓，張 源，王加冕

（昆明理工大學(xué) 機(jī)電工程學(xué)院，云南 昆明 650000）

0 引言

其實(shí)車間調(diào)度問題[1]（Workshop Scheduling Problem，WSP），講的是在實(shí)際生產(chǎn)環(huán)境和外界突發(fā)因素的影響下，根據(jù)生產(chǎn)車間所提供的物資[2]按照一定規(guī)則進(jìn)行恰當(dāng)且符合實(shí)際生產(chǎn)的分配，用以確保能夠搜尋到任務(wù)所需的優(yōu)化目標(biāo)。目前對并行機(jī)優(yōu)化調(diào)度[3]（Parallel Machine Optimal Scheduling，PMOS）的研究不僅對企業(yè)的實(shí)際生產(chǎn)還是對研究人員，都有著重要的實(shí)際意義和理論價值。現(xiàn)階段，關(guān)于PMOS的研究，多數(shù)文獻(xiàn)中都是選用智能搜索算法[4]對模型進(jìn)行仿真求解，目前已廣泛應(yīng)用于企業(yè)生產(chǎn)所面臨問題的求解中?；依遣罘诌M(jìn)化混合算法是將經(jīng)典灰狼算法[5]（Grey Wolf Algorithm，GWA）、差分進(jìn)化算法[6]（Differential Evolution Algorithm，DEA）進(jìn)行局限性互補(bǔ)的智能優(yōu)化混合算法，主要是模仿狼群的捕獵行為，將求解最優(yōu)目標(biāo)抽象成狼群的狩獵行為，同時又具有遺傳、迭代等選擇操作流程的行為，具有避免其陷入局部最優(yōu)，防止過早收斂狀況、可調(diào)參數(shù)少的優(yōu)點(diǎn)。目前國內(nèi)已有文獻(xiàn)大多研究的是GWA和DEA單獨(dú)改進(jìn)的算法，應(yīng)用于求解企業(yè)項(xiàng)目中資源調(diào)度、函數(shù)優(yōu)化等問題[7]中，而對于灰狼差分進(jìn)化混合算法應(yīng)用到相關(guān)生產(chǎn)中的研究僅是對約束條件進(jìn)行簡化，往往忽略了工件在機(jī)器上的調(diào)整時間，使得算法的尋優(yōu)精度和效率有所降低。因此，本文結(jié)合實(shí)際工況，以生產(chǎn)過程中系統(tǒng)運(yùn)送工件和機(jī)器安裝不同的工件所產(chǎn)生的生產(chǎn)輔助時間為研究對象，引入灰狼差分進(jìn)化混合算法，建立PMOS并行機(jī)模型，并以最小化最大完工時間作為 WSP的優(yōu)化目標(biāo)和驗(yàn)證灰狼差分進(jìn)化混合算法的性能指標(biāo)。

1 考慮機(jī)器調(diào)整時間的并行機(jī)分批調(diào)度問題描述

現(xiàn)假定并行機(jī)生產(chǎn)車間要對若干個工件進(jìn)行分批加工，其中，工件有N種，每種工件有Gi個，每一種工件皆為一道工序進(jìn)行加工生產(chǎn)，即單工序加工。車間可提供的M臺加工機(jī)器，加工工件可以在所安排的M臺機(jī)器設(shè)備中的任意一臺上進(jìn)行加工，同時同一臺機(jī)器加工不同種工件時需要對機(jī)器進(jìn)行調(diào)整，產(chǎn)生相應(yīng)的調(diào)整時間。并行車間所提供的M臺機(jī)器屬于非等同并行機(jī)，即同一種工件在不同的機(jī)器上的加工時間不一樣。此外，加工每一種工件都需要在機(jī)器設(shè)備上安裝與之對應(yīng)的模具，且每種工件對應(yīng)的模具數(shù)量一定，具體規(guī)則如下：

（1）在確定的生產(chǎn)周期內(nèi)，所需加工工件的需求計劃確定。

（2）每種工件對應(yīng)的模具數(shù)量已知。

（3）每種工件在各個機(jī)器設(shè)備上的加工時間已知，不考慮移動時間。

（4）每種子批中僅有一種工件，并且具有不可拆分性，工件一旦開始加工就不能停止。

（5）每種工件具有一樣的優(yōu)先級，即沒有優(yōu)先或搶先生產(chǎn)的狀況。

（6）同一時刻，每臺機(jī)器僅有一個子批被加工，一個加工子批僅能在一臺機(jī)器上進(jìn)行加工；不同的工件在同一臺機(jī)器上加工時，要考慮機(jī)器的調(diào)整時間，并且調(diào)整時間和工件的加工順序相關(guān)。

（7）各臺機(jī)器為不相關(guān)并行機(jī)，即相同工件在不同的機(jī)器上的加工時間不同。

（8）在加工之前所需加工工件的子批已在緩存區(qū)等待加工；所需加工的工件都已備好，并且所有機(jī)器設(shè)備上的第一個子批不需要調(diào)整。

本文選擇合適的分批方案，以最小化最大完工時間為目標(biāo)，建立以下數(shù)學(xué)模型[9-10]：

表1 各公式中變量和參數(shù)代表含義Tab.1 The meaning of variables

其中，公式（1）是為本文所研究問題的目標(biāo)函數(shù)，在相關(guān)約束條件下，獲得最小化最大完工時間；公式（2）確保每種工件的分批個數(shù)不大于工件的最大分批數(shù)；公式（3）、公式（4）、公式（5）為工件的分批策略，表示工件為均量分批。首先保證子批的數(shù)量一定為整數(shù)，然后對每種工件進(jìn)行均量分批，最后還要確保所有子批的數(shù)量之和等于該工件的生產(chǎn)批量。其中[ ]為取整符號，取最為接近的整整；公式（6）、公式（7）分別表示每種子批在一臺機(jī)器上進(jìn)行加工時有且僅有一個緊前和緊后工件。公式（8）表明每個子批加工的優(yōu)先級相同，且相鄰的兩個子批一定在同一臺機(jī)器上進(jìn)行加工。公式（9）、（10）用來求解每個子批的完工時間，了解各個子批完工時間之間的關(guān)系，且（10）表明工件每個子批的完工時間都大于等于 0。公式（11）代表求解最大完工時間。公式（12）表示任何一個時刻加工同種工件的最大子批數(shù)不大于其對應(yīng)的模具數(shù)量；公式（13）表示0-1 變量。即其數(shù)值為1時，代表的意義分別為在t時刻，第i種工件在機(jī)器j上加工；第k種產(chǎn)品的第s子批在第i種工件的第r個子批加工完成后緊隨進(jìn)行加工，否則為0。

2 考慮機(jī)器調(diào)整時間的并行機(jī)分批調(diào)度問題算法求解

2.1 灰狼差分進(jìn)化混合算法流程框架

對于并行機(jī)分批調(diào)度的研究，選用分批和子批的排序同時進(jìn)行，選用灰狼差分進(jìn)化混合算法求解考慮機(jī)器調(diào)整時間的并行機(jī)分批調(diào)度問題。其中，將最小化最大完工時間作為并行機(jī)分批調(diào)度問題的優(yōu)化目標(biāo)和驗(yàn)證算法尋優(yōu)性能優(yōu)劣的指標(biāo)?，F(xiàn)對算法流程進(jìn)行簡單的介紹，并給出算法流程圖如圖 1所示。

灰狼差分進(jìn)化混合算法流程主要步驟如下：

步驟1：初始化種群。設(shè)定初始種群數(shù)量Np，最大迭代次數(shù) Gmax,交叉概率 Pc。初始化種群初始迭代次數(shù)g = 0。

步驟 2：選取適應(yīng)度函數(shù)并計算初始種群每個個體的適應(yīng)度值Fi。保留該種群中的最優(yōu)解。

步驟 3：種群更新迭代。通過灰狼差分進(jìn)化混合算法更新機(jī)制對初始種群進(jìn)行更新，得到新的測試種群。

步驟 4：非法種群個體修復(fù)操作。隨著迭代次數(shù)的增加，測試種群中會出現(xiàn)一些不合理的個體，通過對其進(jìn)行修復(fù)，得到新的種群。

圖1 灰狼差分進(jìn)化混合算法流程圖Fig.1 Flowchart of grey wolf differential evolution hybrid algorithm

步驟 5：求解新種群中每一個個體的適應(yīng)度值Fj，且保留當(dāng)前種群中的最優(yōu)值。

步驟6：比較Fi和Fj的大小，適應(yīng)值大的個體留下，生成新的種群，并保留新種群中的最優(yōu)解。

步驟7：令g = g + 1，判別是否達(dá)到終止條件，如果g≤maxG ，則轉(zhuǎn)回步驟3繼續(xù)進(jìn)行迭代，直到滿足條件；否則，迭代終止，輸出最優(yōu)值及對應(yīng)的種群。

2.2 改進(jìn)的灰狼差分進(jìn)化混合算法設(shè)計

為了更好地提高問題的求解精度，實(shí)現(xiàn)工件分批和子批分配同時進(jìn)行，在通過閱讀相關(guān)文獻(xiàn)進(jìn)行比較后，本文選用文獻(xiàn)所提出的三段染色體編碼方式，設(shè)計了灰狼差分進(jìn)化混合算法，并對該算法中灰狼算法的更新機(jī)制做出了相應(yīng)的改動。

2.2.1 種群的編碼和解碼方式

基于并行機(jī)分批調(diào)度模型需考慮以下幾個問題：如何對工件進(jìn)行分批，工件分批后子批分別在那臺機(jī)器上進(jìn)行加工，同一臺機(jī)器上各自子批的加工的順序是怎樣的。針對以上幾個問題，本文設(shè)計了灰狼差分進(jìn)化混合算法，編碼方式具體注釋如下：

將染色體分為三段，第一段P1P2…Pn代表的意思是：工件n分為幾批，即子批的個數(shù)，它的長度和工件的種類數(shù)目一樣，大小為N。第二段J11J12…JMP1…JMPn為符號編碼，其代表的意義為：第n種工件的MPn個子批，如J11則代表第一個工件的第一個子批。但是，染色體的長度需要保持一致，因此子批的注明需要用工件的最大分批數(shù)來進(jìn)行標(biāo)注。例如工件A的分批數(shù)P1為2，但是其對應(yīng)的最大分批數(shù)MP1為3，則代表著子批13的工件數(shù)量為0。第三段長度等于機(jī)器數(shù)目，MG1MG2…MGK則代表每臺機(jī)器上所分批的子批數(shù)目。第一段和第三段的位置分別意味著相對應(yīng)工件和機(jī)器。編碼方式如圖2所示。為了更方便的理解如何進(jìn)行解碼，現(xiàn)給出一個簡單例子說明。假定工件種類有三種，且三種工件分別對應(yīng)的模具數(shù)量為 2，3，3，每種工件待加工數(shù)量分別為 8，10，15，不考慮機(jī)器調(diào)整時間，現(xiàn)車間有三臺可提供的加工機(jī)器，每臺機(jī)器加工同種加工時間不同，即屬于非等同并行機(jī)。如圖 2.3所示，其代表一種可行的染色體。

圖2 灰狼差分進(jìn)化混合算法編碼方式Fig.2 Coding method of grey wolf differential evolution hybrid algorithm

圖3 一條可行的染色體Fig.3 A viable chromosome

該條染色體表示含義為：其中，染色體的第一段代表工件的分批個數(shù)，因此第一段的含義為三種工件分別分為2，2，3個子批進(jìn)行生產(chǎn)加工。第二段代表的是每個子批如何分配，即每個子批具體分配到哪臺機(jī)器上進(jìn)行加工。如13則代表第一種工件第三批子批在第一臺機(jī)器上加工。第三段的含義是三臺機(jī)器分別需要加工的子批數(shù)量。2，4，3表示機(jī)器 M1，M2，M3分別需要加工的子批個數(shù)，且子批的加工順序如染色體第二段所示。最終解碼結(jié)果如表2所示。2.2.2 適應(yīng)度函數(shù)

表2 解碼結(jié)果Tab.2 The results of decoding

本文以最小化最大完工時間為優(yōu)化目標(biāo)，如公式（14）所示。適應(yīng)度函數(shù)設(shè)為 F。需求適應(yīng)度函數(shù)的最優(yōu)解，適應(yīng)度函數(shù)和優(yōu)化目標(biāo)關(guān)系為：

MinCmax作為灰狼差分進(jìn)化混合算法的最優(yōu)目標(biāo)。

2.2.3 種群更新迭代方式

因?yàn)樵撊旧w編碼由實(shí)數(shù)編碼和符號編碼組成。故本文設(shè)計灰狼差分進(jìn)化混合算法對模型求解。首先，染色體第一段和第三段為實(shí)數(shù)編碼，故選取差分變異，交叉，選擇操作；第二段染色體為符號編碼，采用灰狼算法思想進(jìn)行更新迭代。

（1）差分進(jìn)化算法更新機(jī)制。對于差分變異，按照公式（15）和（16）對第一段和第三段染色體進(jìn)行差分變異操作：

其中，差分變異操作的參數(shù)和變量含義如表 3所示。

表3 各參數(shù)和變量所代表含義Tab.3 The meaning of each parameter and variable

差分進(jìn)化交叉操作選用二項(xiàng)式交叉，如方程（19）所示：

差分進(jìn)化選擇操作，對于算法迭代后產(chǎn)生的新個體需要與父代個體進(jìn)行比較，適應(yīng)度優(yōu)的保留，適者生存，即擇優(yōu)篩選，優(yōu)勝略汰，適應(yīng)度值大的種群個體進(jìn)入下一代種群中。其操作如公式（20）所示：

其中，差分進(jìn)化交叉、選擇操作參數(shù)和變量代表含義如表4所示。

表4 各參數(shù)和變量所代表含義Tab.4 The meaning of each parameter and variable

（2）改進(jìn)的灰狼算法更新機(jī)制。第二段染色體所選算法為灰狼算法，現(xiàn)根據(jù)灰狼算法的基本思想對算法做如下改進(jìn)：首先，參照反向?qū)W習(xí)思想，對初始種群進(jìn)行優(yōu)化，即先將初始種群擴(kuò)大一倍，即先生成 2NP個個體對種群中每個個體的適應(yīng)度值進(jìn)行求解，選擇所有適應(yīng)度值較優(yōu)的前NP個個體作為初始種群，這樣可保證初始種群個體的優(yōu)異性，提高解的質(zhì)量。其次，因更新迭代皆是通過與三條最優(yōu)染色體交叉變異而來，故會出現(xiàn)種群多樣性不足的現(xiàn)象，并且隨著迭代次數(shù)的不斷累積，影響其收斂速率。針對這一問題，本文在灰狼算法中引入一個自適應(yīng)因子，避免其陷入局部最優(yōu)，防止早熟收斂狀況。在得出三個最優(yōu)解時，隨機(jī)生成一個屬于0到1的數(shù)字σ，比較其與a的大小，若其小于a,則其他染色體進(jìn)行自身突變，否則與三條最優(yōu)染色體進(jìn)行交叉變異。即其他染色體以a的概率進(jìn)行自身突變，以1-a的概率與最優(yōu)染色體進(jìn)行交叉變異。其表達(dá)式為：

最后，因?yàn)槟Ｐ偷恼{(diào)度目標(biāo)是最小化最大完工時間，即所求的為頭狼的位置，為增加其多樣性，每次進(jìn)行更新迭代后，在對最優(yōu)解中的基因以 1/R的概率進(jìn)行自身突變，引入變異算子如公式（22）所示：

其中各參數(shù)和變量含義如下：vj和wj是xj取值的上下限，λ服從均勻分布，

2.2.4 非法個體修復(fù)操作

染色體第一段和第三段為實(shí)數(shù)編碼，第一段為工件分批數(shù)，其數(shù)值小于等于模具數(shù)，第三段為機(jī)器所分到的子批個數(shù)，其數(shù)值總和為每種工件的模具數(shù)量之和。而隨著算法的不斷迭代，染色體第一段和第三段的數(shù)值將會發(fā)生改變，相應(yīng)染色體可能會產(chǎn)生不合規(guī)則的基因，因此設(shè)置以下規(guī)則：若第一段基因數(shù)值小于0，則規(guī)定其數(shù)值為1；若使其數(shù)值大于該工件的模具數(shù)Mo，則規(guī)定其數(shù)值為Mo。對于第三段染色體做以下規(guī)定，每次迭代更新后，第三段染色體基因數(shù)值進(jìn)行歸元化處理，使即重新選擇第三段基因，為使每臺機(jī)器都在加工，不會存在空余機(jī)臺，浪費(fèi)資源，因此當(dāng)染色體第三段上基因值小于0時，對其進(jìn)行訂正操作，使其數(shù)值為1。

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

考慮機(jī)器調(diào)整時間的并行機(jī)分批調(diào)度實(shí)例問題和算法參數(shù)的設(shè)置如下：在該實(shí)例中，待加工工件種類為10，每種工件數(shù)量分別為：200，300，500，300，400，300，500，400，200，400。加工時間如表5所示。

表5 單個工件在機(jī)器上的加工時間Tab.5 Processing Time of Single Workpiece on Machine

不同工件在同一臺機(jī)器上進(jìn)行加工時，需要考慮工件在機(jī)器上的調(diào)整時間，且每一種工件在不同的機(jī)臺上對應(yīng)的調(diào)整時間也不盡相同，工件在機(jī)器上的調(diào)整時間如表6所示。

表6 同一臺機(jī)器加工不同產(chǎn)品需要的調(diào)整時間Tab.6 Adjustment time needed for processing different products on the same machine

該實(shí)例分別采用灰狼差分進(jìn)化混合算法和遺傳差分進(jìn)化混合算法進(jìn)行求解。其中兩種算法的參數(shù)設(shè)置如下：種群數(shù)量N為20，最大迭代次數(shù)Gm為200，交叉PC為0.5，交叉算子F0為0.8。模型仿真優(yōu)化系統(tǒng)的運(yùn)行環(huán)境為：Inter Core i7-7700HQ CPU 2.80 GHz，8.00 GB內(nèi)存，64位win10操作系統(tǒng)。

4 算例結(jié)果分析

將兩種算法分別在考慮機(jī)器調(diào)整時間的并行機(jī)分批調(diào)度模型中獨(dú)立運(yùn)行10次，灰狼差分進(jìn)化混合算法和遺傳差分進(jìn)化混合算法在 10次搜索中得到的最優(yōu)解如表7所示。

表7 10次運(yùn)行尋優(yōu)結(jié)果統(tǒng)計表Tab.7 Statistical results table of 10 times optimization

由表7可以看出，所有的JV數(shù)值皆大于零，這表明在考慮機(jī)器調(diào)整時間的并行機(jī)分批問題的求解中，灰狼差分進(jìn)化混合算法在每次獨(dú)立運(yùn)行時得到的近似最優(yōu)解的精度要高于遺傳差分進(jìn)化混合算法搜尋得到的近似最優(yōu)解。為方便觀察，現(xiàn)展現(xiàn)該實(shí)例問題通過兩種算法求解獨(dú)立運(yùn)行 10次的迭代收斂圖如圖4所示。

從兩種算法十次尋優(yōu)的迭代收斂圖中可以看出，灰狼差分進(jìn)化混合算法的尋優(yōu)性能要優(yōu)于遺傳差分進(jìn)化混合算法。其中，算法在第2次、第3次和第7次獨(dú)立運(yùn)行時，迭代初期遺傳差分進(jìn)化混合算法所搜索到的目標(biāo)函數(shù)值比灰狼差分進(jìn)化混合算法搜索的優(yōu)解要好，但是隨著迭代次數(shù)的增加，灰狼差分進(jìn)化混合算法在尋優(yōu)性能上的優(yōu)勢逐漸體現(xiàn)出來，從圖4（2）、圖4（3）和圖4（7）中可以看出，在搜索后期，灰狼差分進(jìn)化混合算法的尋優(yōu)性能明顯高于遺傳差分進(jìn)化混合算法。另外在第8次和第9次的迭代收斂圖中，本文所設(shè)計算法在一開始的收斂性能就優(yōu)于遺傳差分進(jìn)化混合算法，隨后在整個迭代過程中所得到的最優(yōu)解也優(yōu)于對比算法，證明了所設(shè)計算法的優(yōu)越性。綜合這十次的尋優(yōu)迭代收斂圖來說，灰狼差分進(jìn)化混合算法在求解考慮調(diào)整時間的并行機(jī)分批調(diào)度問題上具有較高的收斂性能，且相較于遺傳差分進(jìn)化混合算法，其尋優(yōu)性能更佳。為了更為直觀的表述兩種算法在求解過程中所獲得的最優(yōu)解的差異，現(xiàn)對兩種算法針對10*5規(guī)模的考慮調(diào)整時間的并行機(jī)分批調(diào)度在 10次獨(dú)立運(yùn)行中所獲得的最優(yōu)解值進(jìn)行比較，并給出10次獨(dú)立運(yùn)行中所搜尋到最優(yōu)解的迭代收斂圖，分別如圖5所示。

從圖5可以明確看出，在10次求解過程中，灰狼差分進(jìn)化混合算法所搜索到的最優(yōu)解明顯優(yōu)于遺傳差分進(jìn)化混合算法所搜尋到的最優(yōu)值，在十次獨(dú)立運(yùn)行中，灰狼差分進(jìn)化混合算法所求的最優(yōu)值1728 min，相較于遺傳差分進(jìn)化混合算法所求的最優(yōu)值完工時間縮短了184 min，證明了灰狼差分混合算法比遺傳差分進(jìn)化混合算法的尋優(yōu)性能更佳?，F(xiàn)針對兩種算法在求解的穩(wěn)定性和尋優(yōu)性能等方面進(jìn)行對比，對比結(jié)果如表8所示。

圖4 10＊5規(guī)模問題獨(dú)立運(yùn)行10次的迭代收斂圖Fig.4 Convergence diagram of 10＊5 scale independent operation for 10 times

圖5 最優(yōu)解迭代圖Fig.5 Optimal iteration graph

表8中，MinCmax代表最小化最大完工時間，即算法優(yōu)化的最終目標(biāo)。其單位為 min。Avg表示兩種算法獨(dú)立運(yùn)行二十次所得到的最優(yōu)解的均值。單位為min。SD為兩種算法獨(dú)立運(yùn)行10次得到的最優(yōu)解的標(biāo)準(zhǔn)差，反映最優(yōu)目標(biāo)的離散程度，即算法本身求解的穩(wěn)定性?；依遣罘诌M(jìn)化混合算法搜尋得到的最優(yōu)值均值為1982.2 min，而遺傳差分進(jìn)化混合算法得到的最優(yōu)解均值為 2119.8 min，其搜索的完工時間大于灰狼差分進(jìn)化混合算法，且兩種算法在10次獨(dú)立運(yùn)行中所搜尋的最優(yōu)解相差184 min。由此可見，本文所采用的灰狼差分進(jìn)化算法在尋優(yōu)精度上明顯優(yōu)于遺傳差分進(jìn)化算法。但是在尋優(yōu)穩(wěn)定性上，灰狼差分進(jìn)化混合算法的標(biāo)準(zhǔn)差為87.41，遺傳差分進(jìn)化混合算法的標(biāo)準(zhǔn)差為68.95，灰狼差分進(jìn)化混合算法相比于遺傳差分進(jìn)化混合算法所搜索到的最優(yōu)目標(biāo)函數(shù)值的離散程度大，表明了本文所設(shè)計的算法極大的改善了算法尋優(yōu)性能。

表8 10次尋優(yōu)結(jié)果統(tǒng)計表Tab.8 Statistical results table of 10 times optimization

5 結(jié)束語

（1）對于只考慮工件分批的非等同并行機(jī)調(diào)度問題，灰狼差分進(jìn)化混合算法在求解精度要高于遺傳差分進(jìn)化混合算法，在10次獨(dú)立運(yùn)行中，灰狼差分進(jìn)化混合算法所搜尋到的最優(yōu)解都優(yōu)于遺傳差分進(jìn)化混合算法。

（2）針對非等同并行機(jī)分批調(diào)度問題，結(jié)合實(shí)際工況，考慮不同工件在同一臺機(jī)器上進(jìn)行加工時機(jī)器所需的調(diào)整時間。通過兩種算法對考慮機(jī)器調(diào)整時間的并行機(jī)分批調(diào)度算例進(jìn)行求解，灰狼差分進(jìn)化混合算法在 10次獨(dú)立運(yùn)行中求得的最優(yōu)解和最優(yōu)解均值皆優(yōu)于遺傳差分進(jìn)化混合算法，證明了所設(shè)計算法在尋優(yōu)性能上的優(yōu)越性。