改進麻雀算法求解低碳柔性作業車間調度問題

楊國棟 馮國紅

（東北林業大學，黑龍江 哈爾濱 150036）

隨著社會的快速發展和工業化進程加速，各國對能源消耗和CO2的排放越來越重視。而制造業消耗了全球總能源的1/3，產生了全球36%的CO2[1]。現代生產過程逐漸向多品種、小批量和定制化方向轉變，柔性作業車間調度問題（FJSP）是作業車間調度問題的擴展，更符合現代生產的需要。因此，采用優化柔性作業車間調度方案是降低加工能耗，減少碳排放的有效途徑。該文提出一種改進的麻雀算法（ISSA）求解低碳FJSP。

1 柔性作業車間調度問題

1.1 問題描述

FJSP問題可以描述為某車間有n個需要加工的工件，每個工件包括ni道工序。這些工序需要在m臺機器上加工，每道工序可被m臺機器中的一臺或者多臺設備加工，選擇不同的機器對應不同的加工時間。該文對工件工序排序和機器進行選擇，以達到減少工件的最大完工時間和減少碳排放量的目的。

1.2 建立模型

通過最小化最大完工時間和碳排放量2個目標函數構建FJSP多目標優化模型，最小化最大完工時間如公式（1）所示。

式中：Teijk為工序Oij在機器k結束加工時間；Oij為工件i的第j道工序；i為工件編號，i=1，2，…，n；n為加工工件數；j為工序編號，j=1，2，…，ni；ni為工件Ji包括的工序數；k為設備編號，k=1，2，…，m；m為加工機器數。

最小化碳排放量如公式（2）所示。

式中：CP和CI分別為加工碳排放量和待機碳排放量。

機器加工時的碳排放量如公式（3）所示。

式中：Ji為第i個工件；Pk為機器k的加工功率；Tijk為工序Oij在機器k結束加工時間；xijk為0～1變量，如果工序Oij在機器k上加工，則xijk=1，否則xijk=0；θ為電網碳排放因子。

機器待機時的碳排放量如公式（4）所示。

式中：PIk為機器k的待機功率。

以最小化最大完工時間和最小化碳排放量為目標建立雙目標FJSP優化模型，如公式（5）所示。

2 改進麻雀搜索算法

2.1 編碼機制

麻雀算法是解決連續問題的優化算法。為使用麻雀算法求解離散組合優化問題，該文將麻雀位置離散為工件排序+機器選擇2個部分。編碼方式為設個體位置向量長度為2l，為X={x（1），x（2），…，x（l），x（l+1），···，x（2l）}，其中前l個元素在[-n，n]內取值。后l個元素在[-m，m]內取值。FJSP實例見表1，表1中的數字為該工序在此機器上的加工時間。

表1 3×5FJSP實例

根據表2中的FJSP實例可得出1個個體向量，位置如圖1所示。其中Oij為第i個工件的第j道工序。

圖1 個體位置編碼

表2 結果比較

2.2 解碼

由于FJSP中的解為離散值，而麻雀個體向量為連續值，因此為實現麻雀算法解空間與實際問題解空間的映射，需要對個體位置向量進行解碼。

2.2.1 工序解碼

用ROV規則對工序解碼。將圖1中的工序個體位置轉化為工序排序，如圖2所示。

圖2 個體位置轉化為工序排序

2.2.2 機器解碼

機器解碼是根據文獻[2]的轉換方法，將個體位置向量轉化為對應工件工序的可選加工機器的序號，如公式（6）所示。

式中：i，j∈[1，l]，round為四舍五入函數；λi+1為個體位置向量中第i+1個元素的值；σ為機器總數；整數s（j）為Oij可選擇的機器總數；m（j）為工序Oij在可選擇加工機器集中的序號，不是機器編號。

2.3 初始化種群

該文采用工序排序+機器選擇的兩段式編碼機制。

工序排序的初始化采用立方混沌映射[3]隨機生成。首先，隨機成l個隨機數，隨機數在[-n，n]任意取值，n為工件個數，然后轉化為工序排序，如公式（7）所示。

式中：yi為立方序列；-n≤y≤n，n為工件個數，i=1，2，…，l，y0≠0。

機器選擇的初始化采用混合搜索的方式，借鑒文獻[4]里的初始化方法，該文先隨機生成工序排序，然后再選擇加工機器。機器分配初始化部分中70%（30%最小完工時間+40%最小碳排放量）由全局搜索產生，30%由局部搜索產生（單個機器加工時間最短），10%由隨機產生。整合工序排序部分和機器分配部分完成種群初始化。

2.4 正弦搜索策略

該文引入正弦搜索策略，使個體根據自身在種群中的位置的優劣進行更新，以便更快搜索到最優解。正弦搜索如公式（8）所示。

式中：wmin和wmax為w的最小值和最大值，wmin=1，wmax=3；為第t次迭代時第i個個體的適應度函數值；和為第t次迭代過程中最好和最差個體的適應度值。

通過正弦搜索策略改進SSA后，ISSA的發現者位置更新如公式（9）所示。

式中：為種群第t+1代中第i個個體的第d維的位置；t為算法當前迭代次數；d為個體位置維度；itermax為算法的最大迭代次數；α為一個隨機數，且α∈（0，1）；R2為[0，1]中的均勻隨機數；ST為警戒值，取值為[0.5，1.0]；Q為一個標準正態分布隨機數；L是元素全為1的1×d的向量。

ISSA加入者的位置更新如公式（10）所示。

式中：Xtbest和Xtworst分別為全局最優和最差的個體位置；D為個體位置維度數。

ISSA警惕者的位置更新如公式（11）所示。

式中：β為服從標準正態分布的隨機數；K為[-1，1]中的一個隨機數；forst和fbest分別為當前全局最差和最優個體的適應度函數值；ε為一個充分小的數。

2.5 交叉變異操作

為進一步提高算法的全局搜索能力，該文在麻雀算法中引入交叉和變異算子。關于交叉操作，在工序排序部分采用部分匹配交叉法；在機器分配采用雙點交叉法。關于變異操作，在工序排序部分采用兩點交換法，即在工序位置向量中任選兩個位置，互換其對應工件的工序；在機器分配部分采用兩點選擇法，即在工序位置向量中任選兩個位置，然后將其對應工件工序的加工機器換為除當前機器的可加工機器集合中的任意一臺機器。

2.6 ISSA整體框架

根據上述改進策略，結合FJSP，提出的ISSA的流程如圖3所示。

圖3 ISSA流程圖

3 試驗分析

為驗證ISSA求解FJSP的可行性，用ISSA對10個Brandimarte標準算例和實際數據進行仿真試驗。對Brandimarte算例中機器的加工功率和待機功率借鑒文獻[5]里設定的功率。

3.1 參數設置

通過查閱文獻和實際測試，該文參數設置如下：種群規模為200，最大迭代次數為200，發現者比例為0.7，警惕者比例為0.2，安全閾值ST=0.5，交叉概率為0.7，變異概率為0.2，電網的碳排放因子[6]θ=0.7478kg（CO2）/（kW·h）。

3.2 多目標算法評價指標

通過查閱文獻，該文用反向世代距離（IGD）和超體積（HV）兩個指標評價ISSA的性能。IGD和HV均可以綜合反映解集的收斂性和多樣性。IGD值越小，算法求得的Pareto前沿越接近實際的Pareto前沿；HV值越大，算法求得的Pareto解分散的越均勻。

3.3 ISSA與SSA、NSGAII標準算例比較

分別用ISSA、SSA和NSGAII多次求解算例，計算IGD和HV的平均值，計算結果見表2。最優結果用加粗字體。由表2可知，ISSA求得的結果均優于SSA和NSGAII，證明ISSA求解FJSP可行。

3.4 實例驗證

為驗證ISSA在求解實際生產問題的性能，以某電梯零件制造企業金工車間[7]的一個加工任務為例，將數據整理簡化為一個8×6的FJSP，具體加工數據見表3。

表3 柔性作業車間調度實例

分別采用ISSA、SSA和NSGAII三個算法求解上述問題，結果見表4。由表4可知，用ISSA求解該實例得出的最大完工時間為52min，比SSA的結果少13.3%，比NSGAII的結果少5.5%。用ISSA求解該實例得到的最小碳排放量為30.0681kg，比SSA的結果少1.0261kg，比NSGAII的結果少0.4600kg。通過ISSA、SSA和NSGAII計算Pareto前沿如圖4所示。由圖4可知，用ISSA得出的解集分布比較均勻，解的數量也比較多，用ISSA得出的目標函數值整體優于SSA和NSGAII。

圖4 最優調度方案甘特圖

表4 ISSA、SSA和NSGAII求解結果

以最小化最大完工時間為目標的最優調度方案的甘特圖如圖4所示。

4 結語

針對SSA在求解FJSP時存在的問題，該文提出一種改進的多目標麻雀搜索算法。通過3種不同的方法對種群初始化，保證初始種群的質量。正弦搜索和交叉變異策略提升算法的搜索和收斂能力。并以標準算例和實例為研究對象驗證ISSA求解FJSP問題的有效性。