基于機器空隙的自適應改進金槍魚群算法在生產排程調度中的研究

張東方 常萬軍 張潔 郭智 張芊芊 王曉雷

關鍵詞：生產排程調度；金槍魚群優化算法；機器空隙；自適應算子

0 引言

在工業領域，學者們積極提出了各種排程優化方法，這些方法主要分為精確方法和近似方法。精確方法在理論上容易實現，能夠得到最優解，但在大規模和復雜背景下往往受到限制，研究表明，當總工序超過250小時，精確方法的計算效率明顯受到限制[1-2]。而近似方法可以在相對短的時間內解決較大規模的問題，使其成為處理實際工業生產中大規模任務的可行選擇。智能優化算法將排程調度問題轉換為通過人工智能技術對問題進行動態演化的過程。例如，Umam等[3]將禁忌搜索過程與遺傳算法相結合，采用基于部分對立的種群初始化技術來最小化最大完工時間。Ali等[4]提出了一種基于虛擬交叉算子的進化遺傳算法，并將其應用到動態作業車間調度問題。黃宇等[5]為求解高復雜排程調度問題，提出基于差分量子粒子群優化算法。然而，每種智能算法都具有獨特的特性，智能算法的挑戰主要體現在計算量大、編碼解碼頻繁等方面，需要在綜合考慮其優缺點的基礎上，為實際應用場景選擇合適的智能方法。

1 基于自適應改進金槍魚群算法的生產調度模型

1.1 基于機器空隙的工序機器選擇

本文提出了一種基于操作的解碼方法，該方法在解碼過程中能夠為工序選擇適當的加工機器。機器的選擇規則取決于當前加工機器m的空閑時刻之前是否存在可插入的空隙[6]。對（?1）′≤&&（+T）≤ 和 ≤（?1）′&&（（?1）′ + T） ≤兩種情況，空隙均是可插的。

解碼的工序插入方式包括兩種情況，如圖1所示。本文選擇與當前解碼工序所需加工時間大小最為接近的空隙。如果機器均無可插入空隙，則根據當前最小最大完工時間為當前解碼工序選擇機器。

1.2 混沌映射初始化種群

本文選用logistic混沌映射作為初始化種群的手段，以改進解的質量，初始化公式如式（1） 所示。

式（1） 中Xi代表初始種群中第i 個個體的向量位置，為由logistic 混沌映射生成的隨機數，ubD 和lbD為搜索空間的邊界。引入logistic混沌映射的設定有助于實現更為均勻的種群分布，增強算法在整個空間的搜索能力。

1.3 自適應更新與解濃度的擾動處理

更新位置向量時，相同概率的更新方式存在可能會導致迭代周期的增長、收斂速度的減緩[7-8]。為解決金槍魚群算法兩種位置更新方式在解空間搜索能力的差異，本文引入自適應參數，并引入Levy飛行策略，螺旋位置更新的公式如式（2） 所示。

1.4 基于工件工序的變鄰域搜索機制

為提升對解空間的全面探索，本研究引入了變鄰域搜索機制，以通過改變工件工序序列的基因位值生成新的可行解。本文構建了三種不同類型的鄰域搜索結構NS，用于增強算法的鄰域探索能力，使其能夠更為靈活地遍歷搜索空間。

1） 鄰域搜索結構NS1。為改變工件工序編碼基因段中基因的相對位置，本文采用基因交換的移動鄰域結構，變換過程如下：

步驟1：在工件工序編碼基因段范圍內隨機生成兩個不等隨機數1、2，1≠2 且1<2。

步驟2：判斷1、2 的基因位在工件工序編碼中是否相同，不同則將基因位中的工序進行交換；相同則1=1+1，并重新執行步驟2。

2） 鄰域搜索結構NS2按以下過程進行結構變換：

步驟1：在工件的工序序列編碼基因段范圍內，生成兩個不同的隨機數：rand1、rand2，且rand1

步驟2：將以rand1為首，rand2為尾的基因段進行逆轉形成新的工件工序序列編碼基因段，以產生鄰域解。

3） 鄰域搜索結構NS3隨機選擇兩種不同類型的工件并將其對應基因位互換，以下為結構變換的具體過程描述：

步驟1：在工件工序序列編碼的基因段中，隨機抽取兩種不同的工件編號；

步驟2：將兩個工件號在基因段中基因位進行交換，若兩種工件的工序數量相等，則按照工件在工件工序序列中的基因位置，從左至右逐一交換生成新的鄰域解；若兩種工件的工序數量不等，則以工序數小的工件為主，按照從左至右的順序逐一交換這兩種工件工序所對應的基因位，完成交換后生成新的鄰域解。

以圖2中的工件工序序列編碼S3為例，假設在隨機過程中選中了J2和J3這兩個工件，按照NS3鄰域變換規則變換后得到新的工件工序序列編碼如圖2中所示。

2 實驗結果與分析

本小節選擇金槍魚群算法（Tuna swarm optimiza?tion， TSO） 、陳亮等[9] 提出的自學習遺傳算法（Selflearninggenetic algorithm， SLGA） 、黃宇等[5]提出的差分量子粒子群算法（Differential evolution quantum par?ticle swarm optimization， DEQPSO）、張景淘[10]提出的自學習蜂群算法（Self-learning artificial bee colony algo?rithm， SLABC） 、楊草原[11]提出的鯨魚優化算法（WhaleOptimization Algorithm， WOA） 與本文提出的TSOAMG 算法作比較。為保證公平，所有實驗均在相同環境下進行。設置種群數為30，最大迭代數為500，各對比算法均在各文獻提供的最優參數下進行。本文的TSOAMG算法實驗中z=0.05，a=0.7，與文獻11中TSO 算法一致。所有算法對每個數據案例均運行10次，實驗結果如表1所示。為比較算法的收斂性，圖3展示了20×10規模下的算法的收斂情況。

由圖3可知，實驗中在前100代收斂速度最快，本文改進的TSOMG算法與黃宇等改進的IPSO算法在100代后達到其最優函數值，其余4種算法均在150代后達到最優函數值。由此可知，本文改進TSOMG算法在排成調度問題中有較好的收斂性。

3 結束語

針對當下離散制造業生產中存在的排程調度不準確問題，本文提出了一種基于機器空隙的自適應改進金槍魚群算法，通過自適應更新來提高尋優能力和收斂精度。為保證流程初始化陣列的多樣性，本文采用混沌映射初始化陣列，設計自適應陣列算子情況選擇不同的更新策略，并結合Levy飛行策略來增強算法的搜索范圍。通過對排程經典案例的實驗驗證，證明了TSOMG算法在排程結果和收斂性優于當下其他流行算法，解決了多樣化訂單排程困難的問題，為傳統制造業實現智能化生產提供了解決思路。