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

1.南京航空航天大學(xué)機(jī)電學(xué)院，南京，2100162.上海航天精密機(jī)械研究所，上海，201600

0 引言

當(dāng)前制造業(yè)生產(chǎn)模式呈現(xiàn)出多品種、小批量、混流化的特征，在實際生產(chǎn)過程中，用戶的個性化定制需求，以及各種無法預(yù)測的擾動，使得整個生產(chǎn)系統(tǒng)變得復(fù)雜、動態(tài)、隨機(jī)，因此，急需尋求一種相應(yīng)的動態(tài)調(diào)度方法來應(yīng)對當(dāng)前動態(tài)多變的制造環(huán)境。

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

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

傳統(tǒng)或改進(jìn)的協(xié)商機(jī)制都是Agent之間的直接通信，需要花費(fèi)大量時間在信息處理上，無法實現(xiàn)實時響應(yīng)。本研究針對柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem,FJSP)，借鑒蟻群中的間接通信原理，通過信息素來完成Agent之間的協(xié)商，同時，在信息素的構(gòu)成中融入了更多的全局性能指標(biāo)信息，來實現(xiàn)全局的多目標(biāo)優(yōu)化。另外，本研究同時對生產(chǎn)任務(wù)分配階段和緩沖區(qū)工件選擇階段的調(diào)度進(jìn)行了優(yōu)化，并且考慮了獨(dú)立的調(diào)整時間，更加符合實際。

1 問題描述

傳統(tǒng)的調(diào)度中對生產(chǎn)車間做出了過多的假設(shè)，使得調(diào)度方法不能很好地應(yīng)用于實際生產(chǎn)。本研究移除了一些不必要的假設(shè)，使得車間模型更加符合實際。

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

1.1 調(diào)整時間

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

1.2 性能指標(biāo)

本文考慮的性能指標(biāo)主要包括平均流經(jīng)時間、最大流經(jīng)時間、平均拖期時間、最大拖期時間、加工成本、加工能耗，其數(shù)學(xué)模型如下：

(1) 平均流經(jīng)時間

(1)

(2) 最大流經(jīng)時間

f2=max(Ci-Ri)

(2)

(3) 平均拖期時間

(3)

(4) 最大拖期時間

f4=max(Ci-Di)

(4)

(5) 總加工成本

(5)

(6) 總加工能耗

(6)

2 調(diào)度策略

2.1 基于多Agent系統(tǒng)的動態(tài)調(diào)度模型

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

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

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

(3)機(jī)床Agent。在任務(wù)分配階段，機(jī)床Agent向提出招標(biāo)請求的工件Agent發(fā)送自己當(dāng)前的信息素值；在緩沖區(qū)工件選擇階段，機(jī)床Agent 向緩沖區(qū)工件Agent招標(biāo)來獲得各工件當(dāng)前的信息素值，考慮順序相關(guān)調(diào)整時間，計算各工件的轉(zhuǎn)移概率，選擇轉(zhuǎn)移概率最大的工件進(jìn)行加工。

2.2 動態(tài)調(diào)度策略

圖1是本文提出的多Agent調(diào)度策略的UML序列圖。管理Agent、工件Agent和機(jī)床Agent相互協(xié)作，共同求解出基于流經(jīng)時間、拖期時間、加工成本、加工能耗的全局多目標(biāo)優(yōu)化調(diào)度方案。

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

各Agent之間協(xié)商的具體步驟如下:

(1)機(jī)床Agent在管理Agent處進(jìn)行注冊。

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

(3)工件Agent向清單中所有機(jī)床Agent發(fā)起招標(biāo)。

(4)機(jī)床Agent向工件Agent投標(biāo)，發(fā)送當(dāng)前的信息素值。

(5)工件Agent評估所有的投標(biāo)值，選擇轉(zhuǎn)移概率最大的機(jī)床進(jìn)行加工，并向?qū)?yīng)的機(jī)床Agent發(fā)送“接受”消息。

(6)被接受的機(jī)床Agent回應(yīng)確認(rèn)，如果當(dāng)前機(jī)床空閑那么直接進(jìn)行加工，否則存入緩沖區(qū)等待加工。

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

(8)緩沖區(qū)內(nèi)的工件Agent發(fā)送當(dāng)前信息素值，進(jìn)行投標(biāo)。

(9)機(jī)床Agent在考慮調(diào)整時間的同時評估所有的投標(biāo)值，選擇轉(zhuǎn)移概率最大的工件進(jìn)行加工，并向?qū)?yīng)的工件Agent發(fā)送“接受”消息。

(10)相應(yīng)的工件Agent回應(yīng)確認(rèn)，機(jī)床對此工件進(jìn)行加工，加工完成后重復(fù)步驟(7)～(10)。

此外，當(dāng)機(jī)床出現(xiàn)故障時，管理Agent注銷故障機(jī)床信息并通知相應(yīng)的機(jī)床Agent，相應(yīng)的機(jī)床Agent通知緩沖區(qū)工件Agent重新招標(biāo)，故障機(jī)床上正在加工的工件按報廢處理，同時管理Agent通知ERP系統(tǒng)重新下單；當(dāng)機(jī)床故障修復(fù)時，機(jī)床Agent通知管理Agent，管理Agent重新注冊機(jī)床信息，并更新機(jī)床狀態(tài)。

2.2.1任務(wù)分配階段

機(jī)床信息素

(7)

轉(zhuǎn)移概率α,β,γ,δ是用來平衡信息素、加工時間、加工能耗、加工成本影響的平衡參數(shù)，其具體的設(shè)置值與實際的生產(chǎn)環(huán)境及企業(yè)看重的優(yōu)化目標(biāo)次序密切相關(guān)。其表達(dá)式為

(8)

式中，φmi為招標(biāo)工件在機(jī)床上加工所需時間的倒數(shù)；μmi為加工能耗的倒數(shù)；ωmi為加工成本的倒數(shù)。

對于一個實際的生產(chǎn)環(huán)境及確定的優(yōu)化目標(biāo)次序，一般通過實驗仿真的方法對參數(shù)進(jìn)行設(shè)置調(diào)整以達(dá)到最佳效果。本文在對多目標(biāo)進(jìn)行優(yōu)化時，以基于時間的優(yōu)化指標(biāo)(流經(jīng)時間及拖期時間)為主目標(biāo)，而基于成本、能耗的指標(biāo)為次目標(biāo)。通過仿真實驗不斷地調(diào)整參數(shù)，最終設(shè)置α=1,β=6.5,γ=1,δ=1，此時可以獲得最佳的基于時間指標(biāo)的優(yōu)化結(jié)果以及一定的成本、能耗優(yōu)化。

2.2.2緩沖區(qū)工件選擇階段

工件信息素

(9)

轉(zhuǎn)移概率

(10)

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

2.3 算法時間復(fù)雜度分析

假設(shè)有m臺機(jī)床，n個工件，每個工件有r道工序，每道工序都具有工序加工柔性。

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

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

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

3 實驗驗證與分析

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

3.1 仿真實驗設(shè)計

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

表1 機(jī)床工藝能力信息表

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

(11)

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

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

(12)

表2 加工工件信息表

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

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

3.2 仿真結(jié)果分析

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

由于在實驗開始階段車間加工工件少，會有一段波動期，這嚴(yán)重影響了比較實驗的客觀性，因此必須在波動期結(jié)束后進(jìn)行比較。通過對平均流經(jīng)時間及平均拖期時間的觀察，發(fā)現(xiàn)在第500個工件到達(dá)后，系統(tǒng)進(jìn)入穩(wěn)態(tài)。因此，選擇對第501～2 500個到達(dá)的工件進(jìn)行比較分析。

在情景1下的實驗結(jié)果見表3。由實驗結(jié)果可知，本文提出的基于信息素的多Agent方法在寬松交貨期下，平均/最大流經(jīng)時間及平均/最大拖期時間這4個性能指標(biāo)都遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的多Agent方法，驗證了本文所提方法的有效性。

表3 情景1實驗結(jié)果(不考慮機(jī)床故障及獨(dú)立調(diào)整時間，交貨期寬松)

在情景2下的實驗結(jié)果見表4。由實驗結(jié)果可知，本文提出的基于信息素的多Agent方法，在緊張的交貨期下，優(yōu)化性能依舊遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的多Agent方法，驗證了本文所提方法面對緊張交貨期的適應(yīng)能力。

表4 情景2實驗結(jié)果(不考慮機(jī)床故障及獨(dú)立調(diào)整時間，交貨期緊張)

在情景3下的實驗結(jié)果見表5。由實驗結(jié)果可知，本文提出的基于信息素的多Agent方法，在遇到機(jī)床故障擾動時，依舊能有很好的優(yōu)化性能，且遠(yuǎn)遠(yuǎn)好于傳統(tǒng)多Agent方法，驗證了所提方法應(yīng)對機(jī)床故障擾動的有效性。

表5 情景3實驗結(jié)果(不考慮獨(dú)立的調(diào)整時間，考慮機(jī)床故障，交貨期寬松)

在情景4下的實驗結(jié)果見表6。與情景1中本文方法實驗結(jié)果比較可以發(fā)現(xiàn)，考慮獨(dú)立的調(diào)整時間，可以大大提升優(yōu)化效果，因此，考慮獨(dú)立的調(diào)整時間是十分有效的。

表6 情景4實驗結(jié)果(考慮獨(dú)立的調(diào)整時間，不考慮機(jī)床故障，交貨期寬松)

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

表7 情景5實驗結(jié)果(考慮獨(dú)立調(diào)整時間，不考慮機(jī)床故障，交貨期寬松，多目標(biāo))

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

圖2 γ值對調(diào)度結(jié)果的影響Fig.2 The effect of γ on scheduling results

圖3 δ值對調(diào)度結(jié)果的影響Fig.3 The effect of δ on scheduling results

4 結(jié)語

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