混合花朵授粉算法在作業車間調度中的應用

唐麗君, 彭石燕

(柳州鐵道職業技術學院，柳州 545616)

0 引言

作業車間調度問題(Job-shop Scheduling Problem,JSP)已被證明是一個NP-hard 問題，因此它不能在合理的計算時間內被精確地求解。由于其具有許多實際應用背景，對其研究一直是學者們關注的共同課題，研究如何有效求解JSP 具有重要的理論意義和實際意義。目前，求解JSP 的方法主要有兩種，一種是精確方法，另一種是智能算法。精確方法如線性規劃法、枚舉法、分支定界法等是求解小規模JSP 的常用方法。近年來，人們開發了許多求解JSP 的近似方法。這些方法能在合理的時間內找到最優解或近似解，彌補了傳統方法無法達到近似解的缺陷。智能算法主要包括：文獻[1]提出一種改進并行遺傳算法求解作業車間調度問題，種群規模較大，迭代次數較多；文獻[2]提出改進差分進化算法的作業車間調度優化策略，求解效果較差；文獻[3]提出一種改進型蝙蝠算法并用于作業車間調度問題，效果較好，但迭代次數較多；文獻[4–5]分別提出基于改進粒子群算法作業車間調度問題的優化和新型教與同伴學習粒子群算法求解作業車間調度問題，求解效果較差；文獻[6]提出模擬退火下布谷鳥算法求解車間作業調度問題，求解效果較差；文獻[7]提出求解作業車間調度問題的改進灰狼優化算法，求解效果較差；文獻[8]提出作業車間問題的雜草優化算法求解等方法，求解效果較差；文獻[9–11]利用關鍵路徑移動較好地解決了作業車間調度問題；文獻[12]提出一種改進的帶有序列映射機制的混合復雜進化算法求解作業車間調度問題，求解效果較好。

針對上述問題，本文提出一種花朵授粉算法和遺傳算法的混合算法求解作業車間調度問題。通過26 個經典的基準算例仿真實驗，并與近5 年的6 種算法比較，結果表明所提算法在求解作業車間調度問題具有一定優勢。

1 問題描述

JSP 可描述為：給定n個作業和m臺機器，每個作業包含m道工序，需依次在m臺機器上加工。加工過程滿足約束條件：

1) 每個作業都有機器約束和時間約束；

2) 同一時刻一臺機器只能加工一道工序；

3) 同一時刻一道工序只能在一臺機器上加工；

4) 工序一旦開始加工則不能間斷。

因此，JSP 的數學模型為

其中i,j= 1,2,··· ,n, h,k= 1,2,··· ,m。式(1)為優化目標，式(2)和式(3)分別表示每個工件各工序的操作順序和每臺機器上加工工件順序的要求，式(4)為加工時間約束。Pik為加工時間，Cik為完工時間，T取值為相當大的正數，Xihk和Yijk為0-1 變量。

2 混合算法

2.1 花朵授粉算法

花朵授粉算法(Flower Pollination Algorithm, FPA)是由Yang[13]提出，該算法模擬自然界自花授粉和異花授粉過程，設計算法之初是為了解決連續優化問題，然而針對JSP 離散問題不適用，必須重新編碼及定義計算公式。

2.1.1 編碼與解碼

編碼是算法設計中首當其沖的問題，其關系后續算法計算的定義。以3×3 JSP 問題為例，采用基于工序編碼方式，其編碼方式如表1 所示，花粉個體中每個值為作業號，每個作業出現的順序為第幾道工序，如第1 個3 則工序為1，其在第3 臺機器上加工，加工時間為2，其余依次類推。

表1 基于工序編碼方式

2.1.2 重新定義花朵全局搜索

在基本花朵授粉算法的全局搜索過程中，采用

2.1.3 重新定義花朵局部搜索

局部搜索采用交換、逆序和插入操作，如圖1 所示。

圖1 局部搜索的說明

2.2 遺傳算法

2.2.1 選擇操作

采用輪盤賭選擇，同時保留種群最優解。

2.2.2 交叉操作

在JSP 問題中，采用文獻[14]中的優先交叉方式，其示意圖如圖2 所示。從種群中任意選擇兩個父類：父類1 和父類2。將作業集合劃分為2 個非空集合，保持父類中一個作業號不變，交換其他作業號，產生兩個子類：子類1 和子類2。

圖2 優先交叉方式

2.2.3 變異操作

變異操作為防止種群進化停滯不前的主要手段，采取任意兩點間元素的逆序操作，如圖1(b)所示。

2.3 混合算法(FPA-GA)步驟

步驟1 設置種群規模、轉換概率和最大迭代次數等參數，導入機器約束和時間約束數據；

步驟2 使用表1 方式初始化種群，利用式(1)計算最優值及對應解；

步驟3 判斷循環變量是否達到最大迭代次數，如果是輸出最優值與最優解，否則對每個花粉個體判斷隨機數是否大于轉換概率p，如果大于則利用式(8)進行全局搜索；否則利用圖1 所示進行局部搜索。重新評估此時的目標函數值，并與之前最優值進行比較，如果小于則替換最優值和最優解。然后再執行遺傳算法的選擇、優先交叉和變異操作并評估此時最優值和最優解，如果較之前優越則替換；

步驟4 循環變量加1，進入步驟3。

3 仿真實驗與結果分析

為測試FPA-GA 算法的有效性和優越性，我們選擇標準的JSP 算例進行測試，其中包括23 個LA 問題和3 個FT 問題。CPU 為i7-9750H 2.60 GHz，內存8 G 的Windows 10平臺上，采用Matlab 編程實現。算法的參數設置為：種群數目為10，最大迭代次數為200，交叉概率為0.85(經驗值)，轉換概率為0.8(為原FPA 論文中參數值)。本算法對26 個JSP 測試算例獨立運行10 次的最優解與其他算法比較結果，如表2 所示，表中“–”表示算法未對該算例進行測試。算例FT10、LA16 和LA23 的調度甘特圖，如圖3 至圖5 所示，圖的橫坐標表示時間，縱坐標表示機器號，圖中“3-1”表示第3 個作業第1 道工序，其余依次類推。

圖3 FT10 甘特圖(Tm=967)

圖5 LA23 甘特圖(Tm=1 032)

由表2 中文獻[15]的求解結果可知，僅求解了9 個算例，其中有6 個達到已知最優解；而本文算法測試同樣的9 個算例中有7 個達到已知最優解，其余2 個未達到已知最優解的算例LA17 和LA20 也優于它。由表2 中文獻[8]的求解結果可知，僅求解了11 個算例，其中有8 個達到已知最優解；而本文算法測試同樣的11 個算例有10 個達到已知最優解，其余1 個未達到已知最優解的LA20 也優于它。由表2 中文獻[3]的求解結果可知，共測試了23 個算例，其中有19 個達到已知最優解；而本文算法測試同樣的23 個算例有17 個達到已知最優解，其中算例LA18 和LA19 稍差，但算例FT10、FT20、LA16 和LA20 優于它。由表2 中文獻[2]的求解結果可知，僅測試了10 個算例，其中有3 個達到已知最優解；而本文算法測試同樣的10 個算例中有9 個達到已知最優解，其中1 個未達到已知最優解的算例FT10 也優于它。由表2 中文獻[5]的求解結果可知，僅測試了7 個算例，其中有3 個達到已知最優解；而本文算法測試同樣的7 個算例中有3 個達到已知最優解，其余4 個未達到已知最優解的算例FT10、FT20、LA16 和LA21 優于它。由表2 中文獻[4]的求解結果可知，僅測試了7 個算例，其中有4 個達到已知最優解；而本文算法測試同樣的7 個算例中有4 個達到已知最優解，其余3 個未達到已知最優解的算例FT10、FT20 和LA16 優于它。由表2 中文獻[4]的求解結果可知，本文算法求解的最優解僅算例LA23 較其優越，其他算例均較其差。

表2 不同算法求解結果對比

圖4 LA16 甘特圖(Tm=956)

4 結論

本文針對最小化最大完工時間的作業車間調度問題，提出一種花朵授粉算法和遺傳算法的混合算法，首先離散化基本花朵授粉算法，再融入遺傳算法的選擇、優先交叉和變異操作。通過26 個經典的基準算例仿真實驗，并與近5 年的6 種算法比較，結果表明所提算法在求解作業車間調度問題具有一定優勢。但離散花朵授粉算法的交換和逆序操作有時可能是無效，如何設計有效的局部操作是下一步研究方向。