求解考慮機器調(diào)整時間的并行機分批優(yōu)化調(diào)度問題

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

（8）在加工之前所需加工工件的子批已在緩存區(qū)等待加工；所需加工的工件都已備好，并且所有機器設(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ù)，然后對每種工件進行均量分批，最后還要確保所有子批的數(shù)量之和等于該工件的生產(chǎn)批量。其中[ ]為取整符號，取最為接近的整整；公式（6）、公式（7）分別表示每種子批在一臺機器上進行加工時有且僅有一個緊前和緊后工件。公式（8）表明每個子批加工的優(yōu)先級相同，且相鄰的兩個子批一定在同一臺機器上進行加工。公式（9）、（10）用來求解每個子批的完工時間，了解各個子批完工時間之間的關(guān)系，且（10）表明工件每個子批的完工時間都大于等于 0。公式（11）代表求解最大完工時間。公式（12）表示任何一個時刻加工同種工件的最大子批數(shù)不大于其對應(yīng)的模具數(shù)量；公式（13）表示0-1 變量。即其數(shù)值為1時，代表的意義分別為在t時刻，第i種工件在機器j上加工；第k種產(chǎn)品的第s子批在第i種工件的第r個子批加工完成后緊隨進行加工，否則為0。

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

2.1 灰狼差分進化混合算法流程框架

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

灰狼差分進化混合算法流程主要步驟如下：

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

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

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

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

圖1 灰狼差分進化混合算法流程圖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，判別是否達到終止條件，如果g≤maxG ，則轉(zhuǎn)回步驟3繼續(xù)進行迭代，直到滿足條件；否則，迭代終止，輸出最優(yōu)值及對應(yīng)的種群。

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

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

2.2.1 種群的編碼和解碼方式

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

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

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

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

該條染色體表示含義為：其中，染色體的第一段代表工件的分批個數(shù)，因此第一段的含義為三種工件分別分為2，2，3個子批進行生產(chǎn)加工。第二段代表的是每個子批如何分配，即每個子批具體分配到哪臺機器上進行加工。如13則代表第一種工件第三批子批在第一臺機器上加工。第三段的含義是三臺機器分別需要加工的子批數(shù)量。2，4，3表示機器 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作為灰狼差分進化混合算法的最優(yōu)目標(biāo)。

2.2.3 種群更新迭代方式

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

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

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

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

差分進化交叉操作選用二項式交叉，如方程（19）所示：

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

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

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

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

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

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

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

染色體第一段和第三段為實數(shù)編碼，第一段為工件分批數(shù)，其數(shù)值小于等于模具數(shù)，第三段為機器所分到的子批個數(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ù)值進行歸元化處理，使即重新選擇第三段基因，為使每臺機器都在加工，不會存在空余機臺，浪費資源，因此當(dāng)染色體第三段上基因值小于0時，對其進行訂正操作，使其數(shù)值為1。

3 仿真實驗

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

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

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

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

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

4 算例結(jié)果分析

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

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

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

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

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

圖4 10＊5規(guī)模問題獨立運行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表示兩種算法獨立運行二十次所得到的最優(yōu)解的均值。單位為min。SD為兩種算法獨立運行10次得到的最優(yōu)解的標(biāo)準(zhǔn)差，反映最優(yōu)目標(biāo)的離散程度，即算法本身求解的穩(wěn)定性?；依遣罘诌M化混合算法搜尋得到的最優(yōu)值均值為1982.2 min，而遺傳差分進化混合算法得到的最優(yōu)解均值為 2119.8 min，其搜索的完工時間大于灰狼差分進化混合算法，且兩種算法在10次獨立運行中所搜尋的最優(yōu)解相差184 min。由此可見，本文所采用的灰狼差分進化算法在尋優(yōu)精度上明顯優(yōu)于遺傳差分進化算法。但是在尋優(yōu)穩(wěn)定性上，灰狼差分進化混合算法的標(biāo)準(zhǔn)差為87.41，遺傳差分進化混合算法的標(biāo)準(zhǔn)差為68.95，灰狼差分進化混合算法相比于遺傳差分進化混合算法所搜索到的最優(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）對于只考慮工件分批的非等同并行機調(diào)度問題，灰狼差分進化混合算法在求解精度要高于遺傳差分進化混合算法，在10次獨立運行中，灰狼差分進化混合算法所搜尋到的最優(yōu)解都優(yōu)于遺傳差分進化混合算法。

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