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

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

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

0 引言

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

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

1.1 基于機(jī)器空隙的工序機(jī)器選擇

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

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

1.2 混沌映射初始化種群

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

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

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

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

1.4 基于工件工序的變鄰域搜索機(jī)制

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

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

步驟1：在工件工序編碼基因段范圍內(nèi)隨機(jī)生成兩個(gè)不等隨機(jī)數(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)，生成兩個(gè)不同的隨機(jī)數(shù)：rand1、rand2，且rand1

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

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

步驟1：在工件工序序列編碼的基因段中，隨機(jī)抽取兩種不同的工件編號(hào)；

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

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

2 實(shí)驗(yàn)結(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 算法作比較。為保證公平，所有實(shí)驗(yàn)均在相同環(huán)境下進(jìn)行。設(shè)置種群數(shù)為30，最大迭代數(shù)為500，各對(duì)比算法均在各文獻(xiàn)提供的最優(yōu)參數(shù)下進(jìn)行。本文的TSOAMG算法實(shí)驗(yàn)中z=0.05，a=0.7，與文獻(xiàn)11中TSO 算法一致。所有算法對(duì)每個(gè)數(shù)據(jù)案例均運(yùn)行10次，實(shí)驗(yàn)結(jié)果如表1所示。為比較算法的收斂性，圖3展示了20×10規(guī)模下的算法的收斂情況。

由圖3可知，實(shí)驗(yàn)中在前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é)束語

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