基于機器空隙的自適應(yīng)改進(jìn)金槍魚群算法在生產(chǎn)排程調(diào)度中的研究

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

關(guān)鍵詞：生產(chǎn)排程調(diào)度；金槍魚群優(yōu)化算法；機器空隙；自適應(yīng)算子

0 引言

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

1 基于自適應(yīng)改進(jìn)金槍魚群算法的生產(chǎn)調(diào)度模型

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

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

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

1.2 混沌映射初始化種群

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

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

1.3 自適應(yīng)更新與解濃度的擾動處理

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

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

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

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

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

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

2） 鄰域搜索結(jié)構(gòu)NS2按以下過程進(jìn)行結(jié)構(gòu)變換：

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

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

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

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

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

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

2 實驗結(jié)果與分析

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

由圖3可知，實驗中在前100代收斂速度最快，本文改進(jìn)的TSOMG算法與黃宇等改進(jìn)的IPSO算法在100代后達(dá)到其最優(yōu)函數(shù)值，其余4種算法均在150代后達(dá)到最優(yōu)函數(shù)值。由此可知，本文改進(jìn)TSOMG算法在排成調(diào)度問題中有較好的收斂性。

3 結(jié)束語

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