先做一個聲明：文章是由我的個人公眾號中的推送直接復制粘貼而來，因此對智能優化算法感興趣的朋友，可關注我的個人公眾號：啟發式算法討論。我會不定期在公眾號里分享不同的智能優化算法，經典的，或者是近幾年提出的新型智能優化算法，并附MATLAB代碼。

本期的主要參考資料：

[1] 潘全科, 高亮, 李新宇. 流水車間調度及其優化算法[M]. 武漢: 華中科技大學出版社, 2013.

不允許機器停止運轉，這就是所謂的零空閑調度問題。圖1(a)所示為一個3×3的零空閑流水車間調度問題的甘特圖，由于機器連續運轉的要求，當第一個工件到達機器2時，該機器并不能立即開工。與圖1(b)所示的置換流水車間調度相比，機器2的開工時間有所滯后。因此，零空閑流水車間調度問題不同于一般的置換流水車間調度問題。

圖1

01
問題描述

這里主要考慮以最大完成時間為優化目標的零空閑流水車間調度問題(no-idle flow-shop scheduling problem, NIFSP)，記為Fm|perm, no-idle|Cmax。當m≥3時，這類調度問題就是NP-Hard 問題。

Fm|perm, no-idle|Cmax問題可描述為：有n個工件按照相同的工藝路線在m臺機器上加工，約定所有機器上工件的加工次序都相同,要求在同一機器上加工的相鄰兩工件之間沒有空閑時間。假設機器之間存在無限大的緩沖區，一個工件不能同時由多臺機器加工，一臺機器也不能同時加工多個工件。已知工件在各機器上的加工時間。問題是如何安排各工件的生產次序，使得最大完成時間取值最小。

02
數學模型

（以下內容截自推文開頭提到的參考書籍，潘老師的那本書。）

03
加工性能指標計算

最大完成時間(Cmax)是研究零空閑流水車間調度問題最常用的加工性能指標。NIFSP的最大完工時間有五種計算方法，其時間復雜度均為O(nm)。

方法一：計算機器之間的開工時間差

方法二：Kalezynski和Kamburowski方法(轉化為F2|perm|Cmax)

方法三：前向計算法

方法四：反向計算法

方法五：雙向計算法

這里主要介紹前向計算法。（以下內容截自推文開頭提到的參考書籍，潘老師的那本書。）其他計算方法也可以在這本書籍里查閱。選擇前向計算法是為了方便畫甘特圖。

04
智能算法(GA、DBO等)編碼方法

對于遺傳算法(GA)，因為其算法本身是離散的，通過選擇、交叉、變異產生下一代。因此，一條染色體就代表一種調度方案。即工件的排序即是它的個體編碼。例如，10個工件的排序方案，用MATLAB初始化GA的一個個體(一條染色體)就是：

x=randperm(10);

效果如下所示：

但是對于粒子群優化(PSO)、麻雀搜索算法(SSA)、蜣螂優化(DBO)等，它們本身是針對連續優化問題提出的，所以在編碼時需要經過進一步的處理。與GA一樣，一個調度方案(工件排序)表示一個個體，可以采用SPV規則，將實數編碼轉成整數編碼。例如，10個工件的排序方案，用MATLAB初始化DBO的一個個體(一條染色體)就是：

jobNum=10; %?工件數x=unifrnd(0,1,[1?jobNum]);?%?產生10個[0,1]之間隨機數os?=?1:1:jobNum;?%?產生從1到10的數列[~,?up_index]?=?sort(x);?%?對x進行降序排序, 得到位置序列x?=?os(up_index);?%?按照位置序列排序工件,?得到一個調度方案

效果如下：

此外，與SPV規則相反，Li等提出最大排序值法(Largest rank value, LRV)，也是將連續值映射成離散排列常用的方法之一。如圖2所示，LRV將代表種群個體的一組連續值按降序排列生成一組工件排序。(參考文獻：[2] LI X, YIN M. An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure [J]. Advances in Engineering Software, 2013, 55(8): 10-31.)

圖2 最大排序值法的表示方法

05
數值實驗

這里對DBO求解NIFSP的效果進行簡單測試，調度問題算例選用Rec(21個)。最大迭代次數T設置為2000，種群規模NP設為60。下面展示的結果都是算法隨機運行一次得到的結果。

首先，以Rec05(20工件×5機器為例)，展示DBO隨機運行一次的求解結果。圖3繪制了種群每代的最優適宜度收斂曲線和平均適宜度收斂曲線：

圖3 DBO-NIFSP對于Rec05的收斂曲線

圖4繪制了調度結果的甘特圖：

圖4 DBO-NIFSP對于Rec05的甘特圖

其次，以Rec11(20工件×10機器為例)，展示DBO隨機運行一次的求解結果，如圖5和圖6所示。

圖5 DBO-NIFSP對于Rec11的收斂曲線

圖6 DBO-NIFSP對于Rec11的甘特圖

最后，以Rec41(75工件×20機器為例)，展示DBO隨機運行一次的求解結果，如圖7和圖8所示。

圖7 DBO-NIFSP對于Rec41的收斂曲線

圖8 DBO-NIFSP對于Rec41的甘特圖

06
MATLAB代碼

智能算法(GA、PSO、DE、GWO、SSA、DBO等)求解零空閑流水車間調度問題(no-idle flow-shop scheduling problem, NIFSP)的MATLAB代碼，其中：main.m是主函數，直接運行即可；以算法簡稱命名的.m算法代碼；gantt_chart.m用來繪制甘特圖；objective.m是目標函數，即計算Makespan；method.pdf用來說明Makespan的計算方法，代碼采用的是前向計算方法；Car.xlsx和Rec.xlsx是流水車間調度的兩個經典測試集。

輸出結果包括Makespan、工件排序、計算時間、最優適宜度收斂曲線、平均適宜度收斂曲線、甘特圖。

博主選擇了十種算法來求解NIFSP。主要是幾種經典算法和幾個近幾年的高引算法。對應的MATLAB代碼鏈接如下：

遺傳算法(GA)求解NIFSP
差分進化(DE)求解NIFSP	關注公眾號，里面有鏈接
粒子群優化(PSO)求解NIFSP	關注公眾號，里面有鏈接
灰狼優化(GWO)求解NIFSP	關注公眾號，里面有鏈接
鯨魚優化算法(WOA)求解NIFSP	關注公眾號，里面有鏈接
哈里斯鷹優化(HHO)求解NIFSP	關注公眾號，里面有鏈接
麻雀搜索算法(SSA)求解NIFSP	關注公眾號，里面有鏈接
非洲禿鷲優化算法(AVOA)求解NIFSP	關注公眾號，里面有鏈接
蜣螂優化(DBO)求解NIFSP	關注公眾號，里面有鏈接
星鴉優化算法(NOA)求解NIFSP	關注公眾號，里面有鏈接
以上十種智能優化算法(GA、DE、PSO、GWO、WOA、HHO、SSA、AVOA、DBO、NOA)求解NIFSP的全家桶	關注公眾號，里面有鏈接

可通過下方鏈接下載代碼清單，在里面尋找需要的算法代碼，然后去對應的鏈接獲取。清單會同步更新，一旦有新的代碼，就可以在清單里找到。清單里面有部分代碼是開源獲取的。可隨時免費下載。

鏈接：https://pan.baidu.com/s/1SFDMplrL7tiqGZlrpOSGYg

提取碼：8023

此外，歡迎添加算法交流群進行交流：912369858