改進(jìn)麻雀算法求解低碳柔性作業(yè)車間調(diào)度問題

楊國棟 馮國紅

（東北林業(yè)大學(xué)，黑龍江 哈爾濱 150036）

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

1 柔性作業(yè)車間調(diào)度問題

1.1 問題描述

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

1.2 建立模型

通過最小化最大完工時間和碳排放量2個目標(biāo)函數(shù)構(gòu)建FJSP多目標(biāo)優(yōu)化模型，最小化最大完工時間如公式（1）所示。

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

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

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

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

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

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

式中：PIk為機(jī)器k的待機(jī)功率。

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

2 改進(jìn)麻雀搜索算法

2.1 編碼機(jī)制

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

表1 3×5FJSP實例

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

圖1 個體位置編碼

表2 結(jié)果比較

2.2 解碼

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

2.2.1 工序解碼

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

圖2 個體位置轉(zhuǎn)化為工序排序

2.2.2 機(jī)器解碼

機(jī)器解碼是根據(jù)文獻(xiàn)[2]的轉(zhuǎn)換方法，將個體位置向量轉(zhuǎn)化為對應(yīng)工件工序的可選加工機(jī)器的序號，如公式（6）所示。

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

2.3 初始化種群

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

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

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

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

2.4 正弦搜索策略

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

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

通過正弦搜索策略改進(jìn)SSA后，ISSA的發(fā)現(xiàn)者位置更新如公式（9）所示。

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

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

式中：Xtbest和Xtworst分別為全局最優(yōu)和最差的個體位置；D為個體位置維度數(shù)。

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

式中：β為服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)；K為[-1，1]中的一個隨機(jī)數(shù)；forst和fbest分別為當(dāng)前全局最差和最優(yōu)個體的適應(yīng)度函數(shù)值；ε為一個充分小的數(shù)。

2.5 交叉變異操作

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

2.6 ISSA整體框架

根據(jù)上述改進(jìn)策略，結(jié)合FJSP，提出的ISSA的流程如圖3所示。

圖3 ISSA流程圖

3 試驗分析

為驗證ISSA求解FJSP的可行性，用ISSA對10個Brandimarte標(biāo)準(zhǔn)算例和實際數(shù)據(jù)進(jìn)行仿真試驗。對Brandimarte算例中機(jī)器的加工功率和待機(jī)功率借鑒文獻(xiàn)[5]里設(shè)定的功率。

3.1 參數(shù)設(shè)置

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

3.2 多目標(biāo)算法評價指標(biāo)

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

3.3 ISSA與SSA、NSGAII標(biāo)準(zhǔn)算例比較

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

3.4 實例驗證

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

表3 柔性作業(yè)車間調(diào)度實例

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

圖4 最優(yōu)調(diào)度方案甘特圖

表4 ISSA、SSA和NSGAII求解結(jié)果

以最小化最大完工時間為目標(biāo)的最優(yōu)調(diào)度方案的甘特圖如圖4所示。

4 結(jié)語

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