無人計量實驗室中的車間調度問題優化與仿真

武子科，潘 警攀，彭 警誠，張洪光

(1.北京東方計量測試研究所，北京 100093；2.北京郵電大學，北京 100876)

1 警引言

車間調度問題是典型的NP-Hard問題之一，具有廣闊的工業應用前景[1，2]。車間調度是指在資源有限的情況下對工件加工任務進行排序，使其達到最優的生產調度指標。該類問題的相關研究，在很多領域中有著重要的實用價值。

北京東方計量測試研究所的無人計量實驗室是無人值守的計量檢測平臺，該實驗室可以進行多個型號電學儀器的多個種類計量檢測任務，每個任務無調度順序的約束。因此，可以把無人計量實驗室定義為開放式車間環境，該開放式車間環境的計量檢測任務分配可以被定義為開放式車間調度問題(open shop scheduling problem，OSSP)。

如圖1所示，開放式車間調度問題的一般形式為n個工件在m臺機器上進行加工，所有工件均需在每一臺機器上進行一次加工，且無前后加工順序約束，求解最小化最大完工時間的加工排序。如果工件在機器上以固定加工順序進行加工，該問題將演變為流水車間調度問題；如果每個工件按各自加工順序進行加工，該問題將演變為作業車間調度問題。因此，開放式車間調度問題具有較高的復雜度。

圖1 不同車間調度問題示意圖

求解開放式車間調度問題的方法主要有精確算法和智能算法。Bruker等人[3]基于析取圖提出的分支定界算法是一種被廣泛應用的精確算法，首次在標準算例上取得了部分最優解。Gueret等人[4]在該研究基礎上加入智能回溯算法，解決了更大規模的問題。由于精確算法的時間復雜度大，不適于求解大規模問題，當前的研究主要采用智能算法提高求解效率。Liaw等人[5]將基于禁忌搜索的局部改進過程引入遺傳算法中，在局部最優子空間進行遺傳搜索，獲得了標準算例中的大部分最優解。Blum等人[6]在蟻群算法中加入集束搜索提出集束蟻群搜索算法，加速了問題求解速度，提高了解的質量。此外，高亮等人[7]針對粒子群優化算法信息共享機制的缺陷提出改進的粒子群優化算法，提高了粒子群優化算法在該問題中的鄰域搜索能力。陳祥等人[8]使用文化基因法進行了優化求解，并在標準算例中驗證了其算法在搜索空間較大問題中的優勢。灰狼優化算法是Mirjalili等人[9]在2014年提出的一種新型優化算法，大量的實驗表明[10，11]，該算法及其改進算法在求解精度和穩定性上優于粒子群優化算法、遺傳算法等。灰狼優化算法已廣泛應用于路徑規劃問題、無人機協同調配問題和軌跡預測問題等，然而在車間調度問題中的應用剛剛起步。Komaki等人[12]和Jiang等人[13]分別證明了灰狼優化算法在流水車間調度問題和作業車間調度問題及其變種問題的有效性。但是，在開放式車間調度問題中灰狼優化算法的有效性還未得到實驗證明。

由于無人計量實驗室具有多種的計量檢測任務，如何實現不同任務的合理調度，是無人計量實驗室研究主要問題之一。本文首先將無人計量實驗室的計量檢測任務調度問題定義為開放式車間調度問題，并提出基于適應度和距離評估標準的離散灰狼優化算法(discrete grey wolf optimization，DGWO)。此外，根據北京東方計量測試研究所無人計量實驗室的日常實際計量檢測需求，使用離散灰狼優化算法，來實現最小化最大完成時間的目標。

2 開放式車間調度問題模型

開放式車間調度問題模型的參數定義，如表1所示。由工件集J={J1，J2，…，Jn}和對其進行加工的機器集M={M1，M2，…，Mm}組成，每個工件Ji∈J均在每個機器Mj上執行相應的工序Oi，j。相關的假設如下：①每個工件需在全部m臺機器上完成m個操作，無順序優先性；②工件加工工序嚴格遵守加工時間，加工過程不能中斷；③任意時刻一臺機器只能加工一個工件，且任意時刻一個工件只能在一臺機器上加工；④0時刻所有機器可用；⑤不考慮機器故障及工件到達延遲等問題。

表1 參數定義

本文使用整數規劃模型[6，14]來描述開放式車間調度問題，并以最小化Cmax為優化目標，如式(1)-(8)所示。式(1)為目標函數；式(2)表示每個工件只能在每臺機器上加工一次；式(3)表示每臺機器加工完一個工件后只能繼續加工另一個工件；式(4)表示零工序可以為任意工序的前置工序；式(5)表示任意工件的一個工序不能同時在另一個工序之前和之后；式(6)表示任意時刻一臺機器只能加工一個工件；式(7)表示任意時刻一個工件只能在一臺機器上進行加工；式(8)表示最大完工時間不小于任意一個工件的完工時間。

minCmax

(1)

(2)

(3)

(4)

(5)

Ck，j-Ci，j≥Pk，j，?j∈M;?i，k∈J;i≠k

(6)

Ci，1-Ci，j≥Pi，1，?j，l∈M;j≠1;?i，k∈J

(7)

Cmax≥Ci，j，?i∈J;?j∈M

(8)

3 求解開放式車間調度問題的灰狼優化算法

3.1 基本灰狼優化算法

灰狼優化算法是受自然界狼群捕獵行為啟發而提出的一種群智能優化算法。該算法模擬了自然界中灰狼群體的領導等級和狩獵機制，用四種類型的灰狼(α狼、β狼、δ狼和ω狼)模擬狼群階層，并模擬了追蹤、圍獵和攻擊過程。灰狼算法將每只狼抽象為問題的一個解，適應度最好的解為頭狼，稱為α狼，適應度次好的解為β狼，適應度第三的解為δ狼，其它解為ω狼。ω狼在α狼、β狼和δ狼的引領下完成追蹤、圍獵和攻擊行為，最終捕獲獵物。灰狼群圍獵的數學模型用以下公式進行描述

(9)

(10)

(11)

(12)

(13)

(14)

3.2 基于適應度和距離評估標準的離散灰狼優化算法

提出的離散灰狼優化算法，使用適應度和距離評估標準，選出最好適應度的個體作為α狼，此外，還選出既有較好適應度、又與α狼有一定漢明距離的β狼和δ狼。從而，盡量讓α狼、β狼和δ狼平衡地引導狼群，保持種群多樣性，避免早熟現象發生。通過反復迭代，不斷更新α狼、β狼和δ狼，使得種群逐漸向最優解收斂。

3.2.1 算法框架

離散灰狼優化算法框架如下：

算法1：離散灰狼優化算法

輸入：變異概率pm，距離系數b

Step 1：用隨機整數序列，生成初始種群；

Step 2：計算種群適應度，按適應度對種群進行排序；

Step 3：根據適應度和距離評估標準，選出α、β、δ個體，并將其余個體標記為ω；

Step 4：對ω中所有的個體執行按照式(15)離散搜索策略；

Step 5：檢查是否到達終止條件，如果沒有，則返回Step 2；

Step 6：輸出得到的最優個體與最高適應度。

3.2.2 編碼方法

本文使用工序編碼方案，即將編碼定義為按工序排列的序列，編碼位數值是由從1到n×m的數字組成。以圖2為例，考慮3個工件、3個機器，共計9個工序的問題，按照工序順序進行編碼。以個體(2-3-4-7-5-6-1-9-8)為例，表明其執行順序為(O12-O13-O21-O31-O22-O23-O11-O33-O32)對應的甘特圖見圖3。

圖2 3×3問題序號對應的操作示意圖

圖3 個體(2-3-4-7-5-6-1-9-8)的甘特圖

3.2.3 適應度和距離評估標準

本文對于灰狼群中α狼、β狼、δ狼三個體，采取了基于適應度和距離排名的選擇策略[15]，具體步驟如下：

算法2 適應度和距離評估標準

輸入：每次迭代的種群POP，距離系數b

Step 1：計算種群POP中每個個體的適應度Fitness，并將Fitness最優個體標記為α狼；

Step 2：將除α狼外的每個個體Fitness排名(從優到劣)記為Fitness Rank；

Step 3：計算種群中每個個體與α狼之間的漢明距離Distance；

Step 4：將種群中每個個體的Distance排名(從大到小)記為Distance Rank；

Step 5：選擇Fitness Rank≤10和Distance Rank≤10的個體組成集合MP；

Step 6：計算MP中每個個體的Sum Rank=Fitness Rank+b×Distance Rank；

Step 7：選取Sum Rank最小的兩個個體，分別標記為β狼和δ狼。

3.2.4 離散搜索策略

本文使用基于交叉和變異操作的離散搜索策略表示ω狼向α狼、β狼、δ狼的靠攏過程，如下所示

(15)

算法3 個體更新函數

輸入：個體A、個體B、變異概率pm

Step 1：隨機生成個體上的兩個位置c1和c2；

Step 2：在B中將A中c1與c2之間的序號賦值為0，生成B1；

Step 3：從B1中c2后一位開始，將非零元素順序排列成C；

Step 4：將全零個體D從c2后一位開始用C賦值；

Step 5：將D中的空位用A中c1與c2之間的元素填充；

Step 6：根據變異概率，對個體D執行插入變異操作。

在離散搜索策略中，種群中的每個個體都作為一個親本，隨機與α狼、β狼、δ狼之一執行個體更新函數，得到子代個體。圖4顯示了一次個體更新中交叉過程的實例。為保證種群的多樣性，對交叉生成的個體執行一定概率的插入變異操作。其具體過程為：在個體上隨機選擇兩個位置，將后一個位置上的序號放置于前一個序號之前。此外，圖5顯示了一次個體更新中的插入變異過程。

圖4 個體交叉過程示意圖

圖5 個體變異過程示意圖

4 實驗與討論

4.1 實驗設計

為證明離散灰狼優化算法求解開放式車間調度問題的性能，在經典數據集和北京東方計量測試研究所無人計量實驗室實際問題中進行了實驗。Taillard等人提出了經典數據集[16]，是開放式車間調度問題的常用數據集，本文選取由7個機器和7個工件組成的10個測試實例，以T7-1～T7-10作為測試問題編號。北京東方計量測試研究所的無人計量實驗室由六個機械臂自動檢測環節O1O2O3O4O5O6組成，6個待檢測件均需進行無順序要求的六個環節的計量檢測。圖6顯示了實驗室的布局情況，和其中兩個執行不同計量檢測任務的自動檢測環節實物圖。本文選取該實驗室實際計量數據中的10組數據作為10個實例，并使用編號F1～F10進行區分(https:∥github.com/ZikeW/OSSP.git)。

圖6 無人計量實驗室的調度問題示意圖

本文將選取Hosseinabadi等人提出的擴展遺傳算法(EGA_OS)[17]、Senthilkumar等人提出的啟發式算法(Hu1)[18]、基本灰狼優化算法(GWO)作為對比算法[9]。其中，EGA_OS算法和Hu1算法的交叉概率為0.8；DGWO的距離系數b從1線性遞減到0。所有算法的種群規模為50，變異概率為0.2，終止條件為種群進化600代。

針對每個問題，每種算法都運行50次，通過比較50次Cmax的平均值，來測試算法的有效性。此外，使用誤差棒來表示50次Cmax的標準差，來比較算法的穩定性[19]。

4.2 實驗結果與分析

如圖7所示，對于經典數據集T7-1～T7-10測試問題，提出的DGWO算法在絕大多數問題中取得了最好Cmax的平均值結果。此外，EGA_OS算法雖然也得到了較好的平均值，但是有著較大的標準差，說明了其穩定性有待提高，Hu1算法和GWO算法取得的平均值和標準差都相對較大。上述實驗結果說明，提出的DGWO算法在開放式車間調度問題的經典數據集測試中具有較好的有效性和良好的穩定性。

如圖8所示，與其它對比算法相比，提出的DGWO算法在北京東方計量測試研究所無人計量實驗室數據集的絕大多數問題中均取得了最好的Cmax平均值和標準差。這些實驗結果，說明了提出的DGWO算法在無人計量實驗室調度問題中具有有效性和穩定性，能夠應用于實驗室中實際計量檢測任務的調度，提高計量檢測效率。

綜上，兩種實驗結果說明了不同算法在不同規模問題中的有效性和穩定性，也說明了提出的DGWO算法能夠適用于7×7規模的經典數據集和6×6規模的實驗室數據集，可以較好地適應不同規模的測試問題。

5 結束語

灰狼優化算法作為一種新興的智能優化算法，已經在很多領域得到了應用，但是在開放式車間調度問題中的相關研究才剛剛起步。本文提出了一種離散灰狼優化算法，驗證了離散灰狼優化算法在開放式車間調度問題的可行性。在經典數據集和北京東方計量測試研究所無人計量實驗室實際問題上進行的測試，證明了提出算法的有效性和穩定性，為未來無人計量實驗室的計量檢測任務調度研究打下了基礎。

圖7 Taillard經典數據集T7-1～T7-10仿真結果

圖8 無人計量實驗室數據集F1～F10仿真結果

在未來無人計量實驗室調度問題的研究中，工件的運輸延遲、機器故障等事件會影響實驗室計量檢測任務的統籌調度，如何解決這些不確定性調度問題是無人計量實驗室的未來研究方向之一。