基于SOMA的多目標優化作業車間自適應調度研究

周競濤，蔣騰遠，袁 喬，路朝留

（1.上海航天壹亙智能科技有限公司，上海 201306；2.西北工業大學 機電學院，西安 710072）

0 引言

隨著產品需求的多樣化、定制化、個性化以及市場競爭的日趨激烈，產品的及時交付成為一個企業維持競爭力的有效途徑，而生產調度對產品的及時交付至關重要[1]。為了能夠更好的模擬作業車間的生產調度過程，相對于僅考慮作業車間單目標調度問題，同時針對多個調度目標進行優化調度研究更加貼近實際的生產過程，因此針對作業車間多目標調度問題的研究具有重要的意義，成為作業車間調度的備受關注的研究方向[2～9]。

針對作業車間的多目標調度研究，國內外學者面向不同的作業車間優化目標，采用了多種方法進行研究，能夠更為有效的符合實際的生產過程，如：魏巍等[2]以加工成本、加工質量及制造工期為目標，采用改進的強度Pareto進化算法對作業車間進行優化調度；劉愛軍等[3]將最小化拖期懲罰和加工時間作為調度目標，采用縱橫協同的多種群遺傳算法完成了工藝路線和加工順序的優化；Hamed等[6]針對碳排放量和總延遲時間作為調度目標，運用改進的多目標遺傳算法完成了作業車間的調度問題；朱傳軍等[7]以調度穩定性和魯棒性為優化目標，提出混合重調度策略，并運用多目標差分進化算法求解調度問題；Rong-Hwa H等[8]以時間跨度、作業延遲及分批成本為優化目標，運用改進的蟻群算法完成多目標調度求解；Hadi Mokhtari等[9]以總完成時間、系統利用率以及總能源成本為目標，結合增強進化算法和全局標準，完成問題的求解過程。通過對上述文獻的研究發現，現有的多目標柔性車間調度問題都是針對車間擾動的某一個方面或者某一特定的目標進行調度研究，通過算法優化得到的結果是各個目標的優化值，而不是權衡多個目標的全局調度優化結果。

因此，本文針對柔性作業車間調度問題，以最小化生產成本、最小化生產周期以及交貨緊張度因子作為調度目標，根據作業車間中發生問題的不同，采用動態的自適應調度策略，賦予調度目標不同權值，實現針對擾動的自適應調度過程，獲取權衡多個目標的全局最優解。在求解優化問題的各類方法中，自組織遷移算法（Self-organizing Migrating Algorithm，SOMA）是由Zelinka和Lampinen根據動物的覓食行為共同開發的一種基于合作-競爭的進化學習，由于具有收斂速度快、調節參數少、并行協同好、自適應等優點，被廣泛用于多個領域[10，11]，其中文獻[12]將改進的SOMA運用在流水車間的調度問題，顯示了很好的求解最優解的能力。本文通過對SOMA算法進行改進，采用動態步長，提高算法搜索性能；引入二次插值提高種群的多樣性，從而提高了SOMA算法的自適應能力，以此提高算法的性能。最后通過案例仿真，驗證了提出方法的有效性。

1 問題描述及數學模型

1.1 問題描述

本文研究的自適應調度問題可以描述為：已有調度在車間進行生產情況下，某時刻發生隨機擾動引起生產環境的改變，進而影響到正常生產情況，需要根據擾動進行自適應的調度，對生產資源進行重新的分配，生產新的調度方案，以降低隨機擾動的影響直至所有加工任務完成。

生產車間的調度問題可描述為：車間正在執行的任務集合為：task={τ1，τ2，...，τm}，其中n為車間總任務數目；制造系統中包含的機床集合為：machine={1，2，...，m}，，其中m為車間中機床的總數量；加工任務τi由一系列工序po={poi1，poi2，...，poinb}，其中nbi表示任務τi的工序數，poki，j表示任務τi的第j道工序在機床k上加工。

1.2 多目標優化模型

大多數文獻采用生產周期、加工成本等作為指標進行調度方案的評估，這些指標雖然能夠在很大程度上反映調度方案的優劣，但是沒有考慮到不同任務的優先程度和緊迫程度。本文通過對已有文獻的分析，分別考慮生產成本、生產周期和交貨緊張度因子三個目標，用以表達調度方案的成本、時間和任務的緊迫程度，其數學模型如下：

最小化生產成本

其中：Cost表示生產車間總成本，Costready表示加工準備成本，Costprocess表示加工成本，Costearly表示提前完工懲罰費用，Costdelay表示拖期完工懲罰費用，crki，j表示任務τi的第j道工序在機床k上加工的準備成本系數，cpi，j表示任務τi的第j道工序在機床k上加工成本系數，ceki，j表示任務τi的第j道工序在機床k上加工提前完工懲罰費用系數，cdki，j表示任務τi的第j道工序在機床k上加工拖期完工懲罰費用系數，Dki，j表示任務τi的第j道工序在機床k上加工的截止日期。

最小化生產周期

交貨緊張度因子

約束：

式(4)表示工件的加工時間不為負；式(5)表示每一道工序的準備時間在加工時間之前；式(6)表示上一道工序完成才能進行下一道工序的加工；式(7)表示任意確定時刻，機器k不能同時加工任意兩個不同的工件，其中Ykab，ij=1表示任務τa的工序b先于任務τj的工序j在機床k上加工；式(8)表示任一任務不能的加工不能超過去截止日期。

生產調度的優化過程是使各優化目標達到一種平衡，獲取生產過程近似最優解，因此將上述三種優化目標進行整合，形成單一整體目標。在進行優化目標整合前，需要對單一優化目標進行歸一化處理，因此采用下式對優化目標進行歸一化處理：

其中α為優化目標歸一化后的結果，bmax表示優化目標的最優值，bmin表示優化目標的最劣值，b表示優化函數的當前值。

基于以上歸一化后的三個優化目標，采用權系數的方法將其歸一化為單一調度目標，如下式：

1.3 自適應權重因子

為了能夠適應生產過程中針對不同擾動進行自適應調度，需要根據不同的擾動賦予調度目標不同的權重，從而使調度模型能夠適應擾動，給出較為合理的生產調度方案。因此，本文針對任務拖期、緊急訂單以及設備故障三種典型情況給出相應的權重賦予結果，用以指導自適應調度過程，具體情況如下：

Situation1：當車間進行正常生產時，任務的優先級已經確定，此時選用的策略模型為最小生產周期與最少生產成本，此時賦予三個調度目標的權重分別為ω1=0.5，ω2=0.5，ω3=0。

Situation2：當有緊急訂單插入時，緊急插入的訂單一般具有較短的交貨期，因此，應優先考慮緊急訂單的調度問題，此時，調度的策略以交貨緊張度因子為首要調度目標，再配合最小生產周期和最少生產成本進行任務的調度，此時三個調度目標的權重分別為ω1=0.25，ω2=0.25，ω3=0.5。

Situation3：發生故障時，首先需要對故障的影響進行分析，以當前任務的最少生產成本和最小生產周期為主要調度目標，再配合任務交貨緊張度因子進行調度，此時三種的權重分別為ω1=0.4，ω2=0.4，ω3=0.2。

針對不同的擾動，運用不同的權重進行調度規劃，生成更加符合實際的生產調度方案，從而實現作業車間擾動的自適應調度。

2 基于改進SOMA的調度算法

為了能夠提高SOMA算法的自適應能力，本文將自適應步長與二次插值結合使用，利用自適應步長提高算法的自適應勘探能力，避免算法的早熟，利用二次插值提高SOMA的多樣性，進而增大尋優的概率。其中算法中的每一個個體相當于調度過程中的一個方案，優化目標則作為算法的適應度函數，用于對個體進行評估，實現最后的優化過程。

2.1 編碼與解碼

為了能夠將實際的調度問題與優化算法相結合，編碼是非常關鍵的問題。為了保證所得染色體能夠與調度結果相對應，以及調度過程中工序不發生混亂，本文借鑒[劉愛軍，柔性作業車間多目標動態調度]中提出的加工工序與加工機器相融合的兩層編碼方法，提出一種三層染色體編碼方法，第一層編碼用于表達產品的工序，第二層編碼用與表達加工產品相應工序所用到的機器。如在3×3問題中，假設給定的染色體為[321122331]，其中1代表工件τ1，2代表工件τ2，3代表工件τ3，每件工件都有三道工序，所以每個工件出現三次。機器層用于表達加工該工序的可用機器集合中，如m31是表達用于加工工序po31可用的機床集合。第三層的種群層是將所表達的工序機器與種群初始化得到的結果對應起來，根據最后形成的最優種群對染色體進行調整，從而實現對工序的優化。

2.2 自適應步長設置

在SOMA個體遷移過程中，步長step表示個體向最優解方向搜索范圍的大小，在標準的SOMA算法中，其推薦值為0.11。但在實際的仿真應用過程中發現，算法運行的初期，可以采用較大的步長，提高算法的勘探能力，在運行的后期，采用較小的步長，加強算法的局部搜索能力，在保證提高算法收斂速度的同時，有效利用算法的局部搜索能力。因此，本文采用文獻[12]提出的線性遞減步長策略，令初始步長即為最大步長Stepmax，終止步長即為最小步長Stepmin，且在每次評估過后進行步長的自適應更新，自適應步長定義為：

其中，Count表示當前評價次數，Sum Count表示品鑒次數上限的估計值，根據文獻[12]的實驗結果，這里Stepmax設為0.7，Stepmin設為0.4。

2.3 自適應個體遷移運動

與其他進化算法不同的是，SOMA算法用一個在[0，1]之間的實數PRT表示擾動，用于決定個體是否向領導者遷移。PRT是一個敏感的參數，其可以決定算法的收斂速度，當值越大時，算法收斂越快，一般將PRT的值設為[0.7，1]。用PRT決定個體遷移的過程是通過產生的隨機數與PRT進行比較，進而構建擾動矩陣，其構建過程如下：

當擾動矩陣Ai，j的值為1時，表示個體可以向領導者遷移，當擾動矩陣Ai，j的值為0時，個體不允許向領導者遷移。其移動過程模仿生物覓食活動中的協作行為，生成一個新的位置，其具體的位置遷移過程如下：

其中，xti，j表示個體的新位置，表示個體的原位置，表示領導者的原位置，s∈[0，step]，Ai，j表示擾動矩陣。為了能夠提高種群的多樣性，本文參考文獻[11]引入二次插值用于解決擾動矩陣Ai，j為0的情況，進而提高種群的多樣性，增大獲取最優解的概率。

當擾動矩陣Ai，j為0時，選擇種群中的最優個體（領導者）和兩個隨機個體，利用二次插值方法創建一個新的個體，其公式如下：

其中R1表示領導者，R2和R3是從種群中隨機選擇的個體，如果新的個體比原個體的適應度值要好，則用該個體代替原個體，實現個體向最優結果的遷移過程。

2.3 改進SOMA基本流程

為此，根據以上提出的綜合自適應步長與自適應個體遷移運動的改進SOMA，該算法的基本流程如下：

步驟1：參數定義。根據要解決的問題，定義算法必要的參數，如：PathLength，NP（個體數），ML（最大循環數），PRT，Stepmax，Stepmin等。

步驟2：粒子初始化，在解空間內初始化產生NP個粒子，ML=0。

步驟3：根據目標函數評價每一個體所對應的適應度值。

步驟4：確定最優的適應度值的個體作為領導者，其他的個體作為遷移者。

步驟5：根據擾動矩陣創建新的個體，如果Ai，j=1，用公式X創建新的個體位置，并評價其適應度值，如果由于當前個體，則用新個體取代當前個體，否則不變；如果Ai，j=0，則轉步驟6。

步驟6：利用二次插值公式創建新個體，并評估其適應度值，如果優于當前個體適應度值，則取代當前個體，否則不變。

步驟7：對新的種群進行評估，選擇出新的領導者和遷移者。

步驟8：判斷結束條件，如果未達到轉到步驟5，否則執行步驟9。

步驟9：算法結束。返回最優個體值，或者根據情況返回所有個體值。

3 算例分析

3.1 算法性能比較

根據參考文獻[13]，選擇一下3個測試函數：

1）Ackley函數

2）Schwefel函數

3）Rana函數

為了能夠方便進行優化效果比較，參數設置參照文獻[12]：所有測試函數的維數均為30。群體規模均為20，適應度函數的評估次數上限為500，函數優化結果保留6為小數，同時令每個測試函數獨立運行10次，取其平均值。

參照文獻[12]，SOMA中的參數設置為PRT=0.1，PathLength=3，Step=0.11。基于改進的SOMA的參數設置為Stepmax=0.7，Stepmin=0.4，其余參數同基本SOMA。在處理器為Intel Celeron CPU N2940，主頻為1.83GHz，內存為3.89GB的硬件條件下應用MATLAB2016編寫仿真試驗程序。圖1～圖3給出了兩種SOMA算法收斂曲線。通過圖中可以看出，改進SOMA算法在開始時，其收斂速度與基本SOMA算法保持一致，隨著迭代次數的增加，其收斂速度逐漸快于基本SOMA算法，這主要是因為采用線性遞減的步長策略使算法具有更好的局部搜索能力，以及采用二次插值提高了種群的多樣性，使算法能夠跳出局部最優解。通過對比圖1～圖3可以看出，改進的SOMA算法優于基本SOMA。

圖1 Ackley函數動態尋優曲線

圖2 Schwefel函數動態尋優曲線

圖3 Rana函數動態尋優曲線

表3 工件加工準備時間、準備成本系數、加工時間、加工成本系數

3.2 算例分析

某機加車間有6臺機床組成，需要生產4種零件，完成每個零件的加工需要三道工序，每道工序可以選擇在三臺不同的設備上加工完成。零件的交貨期，提前、拖期懲罰如表1所示，其中工件的準備時間、準備成本系數、加工時間、加工成本系數。

表1 染色體編碼

表2 工件交貨期、提前、拖期懲罰系數

其中每組數據機床加工相應工序的準備時間、準備時間成本系數、加工時間、加工時間成本系數，如2，3；2，5表示工件1的第一道工序在機床1加工的生產準備時間為2，準備時間成本為3，加工時間為2，加工成本為5。

本次實驗算法的基本參數如下S t e pmax=0.7，Stepmin=0.4，PRT=0.1，PathLength=3。通過算法進行仿真，獲得目標函數的最優值0.790078，其中成本為122，生產時間為66，從仿真的結果可以看出，任務1的松弛度最大為2，如果出現擾動時，可以優先調整任務1以適應擾動。其調度的甘特圖如圖4所示。

圖4 4×6算例的甘特圖

4 結語

為解決針對生產車間動態擾動的多目標調度問題，本文采用自適應調度策略與改進的SOMA算法相結合的方法對調度問題進行自適應優化。首先，根據任務的調度目標，生成當前場景下的調度策略，形成相應的多目標調度優化模型；然后，針對多目標調度問題改進了SOMA算法，采用自適應步長的思想，提高SOMA算法的搜索能力，將二次插值問題運用在種群遷移過程中，提高種群的多樣性，解決算法早熟的問題，從而實現運用改進SOMA算法對多目標調度進行自適應優化的過程。通過仿真試驗可以證明，本文提出的改進SOMA算法可以有效求解動態生產車間的針對擾動的多目標調度問題。