基于SOMA的多目標優(yōu)化作業(yè)車間自適應(yīng)調(diào)度研究

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

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

0 引言

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

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

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

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

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

生產(chǎn)車間的調(diào)度問題可描述為：車間正在執(zhí)行的任務(wù)集合為：task={τ1，τ2，...，τm}，其中n為車間總?cè)蝿?wù)數(shù)目；制造系統(tǒng)中包含的機床集合為：machine={1，2，...，m}，，其中m為車間中機床的總數(shù)量；加工任務(wù)τi由一系列工序po={poi1，poi2，...，poinb}，其中nbi表示任務(wù)τi的工序數(shù)，poki，j表示任務(wù)τi的第j道工序在機床k上加工。

1.2 多目標優(yōu)化模型

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

最小化生產(chǎn)成本

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

最小化生產(chǎn)周期

交貨緊張度因子

約束：

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

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

其中α為優(yōu)化目標歸一化后的結(jié)果，bmax表示優(yōu)化目標的最優(yōu)值，bmin表示優(yōu)化目標的最劣值，b表示優(yōu)化函數(shù)的當前值。

基于以上歸一化后的三個優(yōu)化目標，采用權(quán)系數(shù)的方法將其歸一化為單一調(diào)度目標，如下式：

1.3 自適應(yīng)權(quán)重因子

為了能夠適應(yīng)生產(chǎn)過程中針對不同擾動進行自適應(yīng)調(diào)度，需要根據(jù)不同的擾動賦予調(diào)度目標不同的權(quán)重，從而使調(diào)度模型能夠適應(yīng)擾動，給出較為合理的生產(chǎn)調(diào)度方案。因此，本文針對任務(wù)拖期、緊急訂單以及設(shè)備故障三種典型情況給出相應(yīng)的權(quán)重賦予結(jié)果，用以指導(dǎo)自適應(yīng)調(diào)度過程，具體情況如下：

Situation1：當車間進行正常生產(chǎn)時，任務(wù)的優(yōu)先級已經(jīng)確定，此時選用的策略模型為最小生產(chǎn)周期與最少生產(chǎn)成本，此時賦予三個調(diào)度目標的權(quán)重分別為ω1=0.5，ω2=0.5，ω3=0。

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

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

針對不同的擾動，運用不同的權(quán)重進行調(diào)度規(guī)劃，生成更加符合實際的生產(chǎn)調(diào)度方案，從而實現(xiàn)作業(yè)車間擾動的自適應(yīng)調(diào)度。

2 基于改進SOMA的調(diào)度算法

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

2.1 編碼與解碼

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

2.2 自適應(yīng)步長設(shè)置

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

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

2.3 自適應(yīng)個體遷移運動

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

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

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

當擾動矩陣Ai，j為0時，選擇種群中的最優(yōu)個體（領(lǐng)導(dǎo)者）和兩個隨機個體，利用二次插值方法創(chuàng)建一個新的個體，其公式如下：

其中R1表示領(lǐng)導(dǎo)者，R2和R3是從種群中隨機選擇的個體，如果新的個體比原個體的適應(yīng)度值要好，則用該個體代替原個體，實現(xiàn)個體向最優(yōu)結(jié)果的遷移過程。

2.3 改進SOMA基本流程

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

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

步驟2：粒子初始化，在解空間內(nèi)初始化產(chǎn)生NP個粒子，ML=0。

步驟3：根據(jù)目標函數(shù)評價每一個體所對應(yīng)的適應(yīng)度值。

步驟4：確定最優(yōu)的適應(yīng)度值的個體作為領(lǐng)導(dǎo)者，其他的個體作為遷移者。

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

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

步驟7：對新的種群進行評估，選擇出新的領(lǐng)導(dǎo)者和遷移者。

步驟8：判斷結(jié)束條件，如果未達到轉(zhuǎn)到步驟5，否則執(zhí)行步驟9。

步驟9：算法結(jié)束。返回最優(yōu)個體值，或者根據(jù)情況返回所有個體值。

3 算例分析

3.1 算法性能比較

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

1）Ackley函數(shù)

2）Schwefel函數(shù)

3）Rana函數(shù)

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

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

圖1 Ackley函數(shù)動態(tài)尋優(yōu)曲線

圖2 Schwefel函數(shù)動態(tài)尋優(yōu)曲線

圖3 Rana函數(shù)動態(tài)尋優(yōu)曲線

表3 工件加工準備時間、準備成本系數(shù)、加工時間、加工成本系數(shù)

3.2 算例分析

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

表1 染色體編碼

表2 工件交貨期、提前、拖期懲罰系數(shù)

其中每組數(shù)據(jù)機床加工相應(yīng)工序的準備時間、準備時間成本系數(shù)、加工時間、加工時間成本系數(shù)，如2，3；2，5表示工件1的第一道工序在機床1加工的生產(chǎn)準備時間為2，準備時間成本為3，加工時間為2，加工成本為5。

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

圖4 4×6算例的甘特圖

4 結(jié)語

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