基于信息素的多Agent車間調度策略

陳 鳴 朱海華 張澤群 金永喬 王盈聰 唐敦兵

1.南京航空航天大學機電學院，南京，2100162.上海航天精密機械研究所，上海，201600

0 引言

當前制造業生產模式呈現出多品種、小批量、混流化的特征，在實際生產過程中，用戶的個性化定制需求，以及各種無法預測的擾動，使得整個生產系統變得復雜、動態、隨機，因此，急需尋求一種相應的動態調度方法來應對當前動態多變的制造環境。

動態調度也稱在線式調度，是指利用生產系統實時的狀態信息進行生產調度的一種方法。動態調度方法可以分為兩大類：傳統方法和智能方法[1]。傳統方法包括最優化方法、仿真方法和啟發式方法。其中使用最為廣泛的是仿真方法，這種方法采用離散事件仿真方式模擬生產過程中的各種情況，通過數據分析為實際生產提供決策支持。該方法適用于各種復雜的生產系統，但其模型構建復雜，開發周期較長。智能方法包括專家系統、人工神經網絡、智能搜索算法和多Agent方法。專家系統(expert system,ES)是通過模擬人類專家來解決調度問題的一種方法，該方法需要完善的知識庫，因此開發周期較長、成本較高[2]。人工神經網絡一般采用Hopfield或BP神經網絡模型，用來降低計算的復雜性或構建決策模型，但往往需要龐大的歷史數據和訓練時間[3]。智能搜索算法包括遺傳算法、粒子群算法、蟻群算法等，這些方法能夠獲得較優或最優的調度方案，但是計算時間長，實時性不好。多Agent方法是指一系列分散的自治智能體(Agent)通過與環境交互來解決問題的方法[4]，該方法能夠有效地提高制造系統的柔性和可重構性[5]，符合復雜、動態、隨機的生產系統的要求。

傳統的多Agent方法一般采用基于市場招投標機制的合同網協議(contract net protocol,CNP)作為Agent間的協商機制，但是這種協商機制需要Agent間頻繁地進行直接交流，導致整個系統的通信量過大，大量時間用在處理信息上，而無法對事件作出實時響應。同時，由于通信量限制，系統往往只能采取單一報價原則，導致系統優化目標過于單一、不符合實際。此外，由于基本的合同網協議僅根據局部的信息作出決策，因此導致了整體的優化性能較差。桑澤磊等[6]提出了一種基于節拍的改進合同網協議，減少了協商步驟，降低了Agent間的通信量，但該方法并未解決優化目標單一、整體優化效果差的問題。潘穎等[7]將改進的遺傳算法封裝在策略Agent中，實現了完工時間、總負載、最大負載和加工成本的多目標優化，解決了傳統多Agent方法優化目標單一的問題。趙良輝[8]完全摒棄了合同網協議，設計了一種基于時間流的多Agent調度策略，通過抽取各個機床Agent的可用工時對一段時間內的工件Agent進行集中的優化調度。但以上方法Agent間的通信量都很大，實時性得不到滿足。

傳統或改進的協商機制都是Agent之間的直接通信，需要花費大量時間在信息處理上，無法實現實時響應。本研究針對柔性作業車間調度問題(flexible job shop scheduling problem,FJSP)，借鑒蟻群中的間接通信原理，通過信息素來完成Agent之間的協商，同時，在信息素的構成中融入了更多的全局性能指標信息，來實現全局的多目標優化。另外，本研究同時對生產任務分配階段和緩沖區工件選擇階段的調度進行了優化，并且考慮了獨立的調整時間，更加符合實際。

1 問題描述

傳統的調度中對生產車間做出了過多的假設，使得調度方法不能很好地應用于實際生產。本研究移除了一些不必要的假設，使得車間模型更加符合實際。

問題描述如下：①加工任務連續不斷地到來；②工件具有工序加工柔性，即一道工序能在幾臺不同機床上加工；③每一工件都有相應的交貨期；④訂單下達時間是隨機的，工件類型、工件交貨期只有在訂單下達時知道；⑤每臺機床同一時間只能加工一個工件；⑥工件調整時間單獨考慮且與機床上一道加工工序有關；⑦不考慮運輸時間；⑧考慮機床故障，且當故障發生時任何工序都不能在該機床上加工直到故障修復；此外故障發生時機床上正在加工的工件按報廢處理，并重新下料。

1.1 調整時間

調整時間(setup time)主要指機器在加工下一道工序前機器的清理，更換夾具、模具等輔助工件而進行的準備活動所花費的時間[9]。調整時間可以分為順序無關調整時間和順序相關調整時間[10]。順序無關調整時間指與機器上道加工工序無關的調整時間，順序相關調整時間指與機器上道加工工序相關的調整時間。大部分多Agent方法僅考慮了順序無關的調整時間，并作為加工時間的一部分進行計算，這種假設簡化了問題的復雜性，但不符合車間的實際情況，也不利于調度問題的優化。本文將更換夾具所用的時間作為調整時間來單獨考慮。如果加工工件與機床前一個加工工件類型相同，則不需要更換夾具，此時調整時間為0，否則調整時間以加工時間的30%計入[9]。

1.2 性能指標

本文考慮的性能指標主要包括平均流經時間、最大流經時間、平均拖期時間、最大拖期時間、加工成本、加工能耗，其數學模型如下：

(1) 平均流經時間

(1)

(2) 最大流經時間

f2=max(Ci-Ri)

(2)

(3) 平均拖期時間

(3)

(4) 最大拖期時間

f4=max(Ci-Di)

(4)

(5) 總加工成本

(5)

(6) 總加工能耗

(6)

2 調度策略

2.1 基于多Agent系統的動態調度模型

基于多Agent系統的動態調度模型由工件Agent(job Agent)、機床Agent(machine Agent)、管理Agent(manager Agent)組成。各Agent主要職能如下。

(1)管理Agent。管理Agent具有注冊功能，記錄著當前所有Agent的信息和狀態，可以為工件Agent提供加工機床的信息。此外，管理Agent實時監控機床的狀態，當機床發生故障時，管理Agent通知相應的機床Agent，并注銷當前機床；當機床修復時，重新進行注冊。

(2)工件Agent。在任務分配階段，即工件選擇機床階段，工件Agent通過向機床Agent招標來獲得各機床當前的信息素值，計算各機床的轉移概率，選擇轉移概率值最大的機床；在緩沖區工件選擇階段，工件Agent實時更新自己的信息素值，并在收到機床招標請求時發送當前信息素值。

(3)機床Agent。在任務分配階段，機床Agent向提出招標請求的工件Agent發送自己當前的信息素值；在緩沖區工件選擇階段，機床Agent 向緩沖區工件Agent招標來獲得各工件當前的信息素值，考慮順序相關調整時間，計算各工件的轉移概率，選擇轉移概率最大的工件進行加工。

2.2 動態調度策略

圖1是本文提出的多Agent調度策略的UML序列圖。管理Agent、工件Agent和機床Agent相互協作，共同求解出基于流經時間、拖期時間、加工成本、加工能耗的全局多目標優化調度方案。

圖1 多Agent調度策略UML序列圖Fig.1 UML sequence diagram of multi-Agent scheduling strategy

各Agent之間協商的具體步驟如下:

(1)機床Agent在管理Agent處進行注冊。

(2)有工件釋放工序時，工件Agent向管理Agent提出加工請求，管理Agent發送可以選擇的加工機床清單。

(3)工件Agent向清單中所有機床Agent發起招標。

(4)機床Agent向工件Agent投標，發送當前的信息素值。

(5)工件Agent評估所有的投標值，選擇轉移概率最大的機床進行加工，并向對應的機床Agent發送“接受”消息。

(6)被接受的機床Agent回應確認，如果當前機床空閑那么直接進行加工，否則存入緩沖區等待加工。

(7)機床加工完成后，如果工件完成所有加工，那么存入倉庫并注銷工件Agent，否則工件Agent釋放下一道工序，重復步驟(2)～(6)；同時，機床對自己緩沖區內的工件Agent進行招標。

(8)緩沖區內的工件Agent發送當前信息素值，進行投標。

(9)機床Agent在考慮調整時間的同時評估所有的投標值，選擇轉移概率最大的工件進行加工，并向對應的工件Agent發送“接受”消息。

(10)相應的工件Agent回應確認，機床對此工件進行加工，加工完成后重復步驟(7)～(10)。

此外，當機床出現故障時，管理Agent注銷故障機床信息并通知相應的機床Agent，相應的機床Agent通知緩沖區工件Agent重新招標，故障機床上正在加工的工件按報廢處理，同時管理Agent通知ERP系統重新下單；當機床故障修復時，機床Agent通知管理Agent，管理Agent重新注冊機床信息，并更新機床狀態。

2.2.1任務分配階段

機床信息素

(7)

轉移概率α,β,γ,δ是用來平衡信息素、加工時間、加工能耗、加工成本影響的平衡參數，其具體的設置值與實際的生產環境及企業看重的優化目標次序密切相關。其表達式為

(8)

式中，φmi為招標工件在機床上加工所需時間的倒數；μmi為加工能耗的倒數；ωmi為加工成本的倒數。

對于一個實際的生產環境及確定的優化目標次序，一般通過實驗仿真的方法對參數進行設置調整以達到最佳效果。本文在對多目標進行優化時，以基于時間的優化指標(流經時間及拖期時間)為主目標，而基于成本、能耗的指標為次目標。通過仿真實驗不斷地調整參數，最終設置α=1,β=6.5,γ=1,δ=1，此時可以獲得最佳的基于時間指標的優化結果以及一定的成本、能耗優化。

2.2.2緩沖區工件選擇階段

工件信息素

(9)

轉移概率

(10)

式(7)和式(9)都是關于時間的函數，因此機床信息素和工件信息素都需要實時更新。

2.3 算法時間復雜度分析

假設有m臺機床，n個工件，每個工件有r道工序，每道工序都具有工序加工柔性。

(1)任務分配階段。每個工件Agent在任務分配階段需根據信息素值為當前釋放工序選擇加工機床。由信息素計算公式可知，每臺機床信息素的時間復雜度是常數，機床數最多為m，則每個工件的時間復雜度為O(m)。該段時間最多有n個工件調度，所以任務分配階段的時間復雜度為O(mn)。

(2)緩沖區工件選擇階段。每次機床選擇工件時都要遍歷當前的緩沖隊列，緩沖隊列中最多有n個工件。工件信息素的時間復雜度為常數，所以每次機床選擇工件的時間復雜度為O(n)。該段時間內最多有m臺機床選擇工件，所以緩沖區工件選擇階段的時間復雜度也為O(mn)。

綜上所述，算法總的時間復雜度為O(mn)，與傳統的多Agent方法相同。

3 實驗驗證與分析

傳統的多Agent方法在任務分配階段一般是以招標任務完工時間最早為決策依據，同時在選擇緩沖區工件時采用FIFO原則，即先到先加工原則。而本文采用的是基于信息素的間接通信方式，并對任務分配階段和緩沖區工件選擇階段都進行了優化。為了驗證提出的基于信息素的多Agent方法的有效性，本文設計了相關的仿真實驗，將兩種方法進行了對比。

3.1 仿真實驗設計

作業車間共包含8臺機床，3臺數控車床，3臺數控銑床，2臺加工中心。數控車床可以完成車削和磨削的加工，數控銑床可以完成銑削和鉆孔的加工，加工中心可以完成所有類型的加工，詳細的機床工藝能力信息如表1所示。

表1 機床工藝能力信息表

加工工件主要有4種類型，詳細信息見表2。表中的加工時間指的是工件工序的平均加工時間，它在某一機床上的實際加工時間是工件工序的平均加工時間和機床加工系數的乘積。工件訂單的到達時間間隔服從指數分布，并且每種工件類型的到達概率都為0.25，指數分布的平均值

(11)

實驗設定車間利用率為0.9，所有工件平均加工時間取71.5，機床總數為8。

工件訂單的交貨期采用全部工作內容(TWK)方法[11]計算：

(12)

表2 加工工件信息表

本文取c=4和c=8，分別表示緊張的交貨期和寬松的交貨期兩種情況，來驗證本文所提方法在不同交貨期情況下的適應能力。

機床故障時所需的修復時間以及兩次故障之間的間隔時間服從指數分布，指數分布的平均值分別是平均故障修復時間(MTTR)和平均故障間隔時間(MTBF)，并且所有機床的MTTR和MTBF都相同，本文實驗設定MTTR為85，MTBF為4 165。

3.2 仿真結果分析

本文共在5種不同的情景下進行了對比實驗分析，以驗證本文所提方法的有效性和優越性。情景1是在不考慮機床故障及獨立調整時間，并且在寬松交貨期的情況下，比較傳統多Agent方法和本文所提方法的優劣；情景2是在不考慮機床故障及獨立調整時間，并且在緊張交貨期的情況下，比較兩者的優劣；情景3是在不考慮獨立調整時間，但考慮機床故障，且在寬松交貨期的情況下，比較兩者的優劣；情景4是為了驗證考慮調整時間的有效性，在考慮調整時間、不考慮機床故障，且交貨期寬松的情況下，與情景1中的實驗結果進行對比，突出單獨考慮調整時間優化的有效性；情景5在不考慮機床故障，但考慮獨立的調整時間，且在寬松交貨期的情況下，驗證考慮成本、能耗的多目標優化的有效性。

由于在實驗開始階段車間加工工件少，會有一段波動期，這嚴重影響了比較實驗的客觀性，因此必須在波動期結束后進行比較。通過對平均流經時間及平均拖期時間的觀察，發現在第500個工件到達后，系統進入穩態。因此，選擇對第501～2 500個到達的工件進行比較分析。

在情景1下的實驗結果見表3。由實驗結果可知，本文提出的基于信息素的多Agent方法在寬松交貨期下，平均/最大流經時間及平均/最大拖期時間這4個性能指標都遠遠優于傳統的多Agent方法，驗證了本文所提方法的有效性。

表3 情景1實驗結果(不考慮機床故障及獨立調整時間，交貨期寬松)

在情景2下的實驗結果見表4。由實驗結果可知，本文提出的基于信息素的多Agent方法，在緊張的交貨期下，優化性能依舊遠遠優于傳統的多Agent方法，驗證了本文所提方法面對緊張交貨期的適應能力。

表4 情景2實驗結果(不考慮機床故障及獨立調整時間，交貨期緊張)

在情景3下的實驗結果見表5。由實驗結果可知，本文提出的基于信息素的多Agent方法，在遇到機床故障擾動時，依舊能有很好的優化性能，且遠遠好于傳統多Agent方法，驗證了所提方法應對機床故障擾動的有效性。

表5 情景3實驗結果(不考慮獨立的調整時間，考慮機床故障，交貨期寬松)

在情景4下的實驗結果見表6。與情景1中本文方法實驗結果比較可以發現，考慮獨立的調整時間，可以大大提升優化效果，因此，考慮獨立的調整時間是十分有效的。

表6 情景4實驗結果(考慮獨立的調整時間，不考慮機床故障，交貨期寬松)

在情景5下的實驗結果見表7。由實驗結果可知，在考慮多目標優化的條件下，平均流經時間、最大流經時間、平均拖期時間、最大拖期時間這4個性能指標相對情景4的結果并未降低很多，而對應的加工成本降低了4.7%，加工能耗降低了4.5%，大大節約了生產的成本和能源。

表7 情景5實驗結果(考慮獨立調整時間，不考慮機床故障，交貨期寬松，多目標)

在考慮獨立的調整時間、不考慮機床故障、交貨期寬松的條件下，本文進一步分析了能耗、成本指標與基于時間的指標(平均流經時間、平均拖期時間)之間的約束關系以及參數設置對多目標優化效果的影響，見圖2和圖3。兩次分析實驗數據均是在保持時間指標平衡參數α,β,ε,θ值不變的情況下，單獨對γ或δ取值得到。由圖可見，能耗、成本指標與基于時間的指標近似成負相關性，隨著γ、δ值的不斷增大，總能耗與總成本指標不斷下降，而平均流經時間和平均拖期時間卻逐漸上升。據此，企業在生產中可以結合實際需要，選擇進一步放寬時間相關指標，增強成本能耗相關指標來達到節約成本能源的目的。

圖2 γ值對調度結果的影響Fig.2 The effect of γ on scheduling results

圖3 δ值對調度結果的影響Fig.3 The effect of δ on scheduling results

4 結語

本文針對FJSP問題，借鑒了蟻群中的間接通信原理，使得Agent間可以通過信息素完成間接通信，大大減少了通信量，增強了實時性。通過在信息素中加入更多的全局信息，實現了全局的多目標優化。此外，對任務分配階段和緩沖區工件選擇階段都進行了優化，并且考慮了獨立的調整時間，進一步提高了優化性能且更加符合實際。最后，通過實例仿真，驗證了本文所提多Agent方法的有效性。