基于Multi-Agent的作業(yè)車間調(diào)度策略研究

陳大林

(東南大學機械工程學院，江蘇 南京 211189)

作業(yè)車間調(diào)度是指根據(jù)一組特定的規(guī)則和指標，對制造企業(yè)有限的資源進行合理的配置和調(diào)節(jié)，以滿足企業(yè)的需求和目標，提高企業(yè)的經(jīng)濟效益[1]。近年來，由于現(xiàn)代制造系統(tǒng)的市場運行環(huán)境越來越充滿了不確定性，制造業(yè)一直以來都需要面對各種挑戰(zhàn)：市場的動態(tài)需求、制造任務不斷變化，生產(chǎn)任務不可預期地增加與減少、某些生產(chǎn)資料的緊缺和引入、加工工藝及時間的變化等。這些不確定性和動態(tài)性組合在一起,進而使車間調(diào)度變得更加困難。甚至有調(diào)查表明[2]，制造過程有95%的時間消耗在非切削過程中。因此，作業(yè)車間調(diào)度是制造中最基本、最重要的問題之一,其對制造過程中資源合理分配、縮短加工時間以及提高生產(chǎn)效率等具有重要的實際意義。

早在1954年 Johnson 研究了流水車間調(diào)度的問題之后，由于調(diào)度問題的理論價值和實用意義，眾多學者對車間調(diào)度問題進行了廣泛的研究[3-4]。近年來，隨著研究的逐漸深入，大量的研究成果相繼問世，形成了一系列先進的研究算法，解決了許多典型的調(diào)度優(yōu)化問題，包括基于啟發(fā)式規(guī)則的方法、分枝定界法、拉格朗日松弛算法、遺傳算法和多智能體(Multi-Agent)方法等。特別是多智能體方法，其是從分布式人工智能(distributed artificial intelligence, DAI)領域擴展而來，對于作業(yè)車間調(diào)度這類具有NP困難特性，比較復雜的分布式系統(tǒng)有著天然的適合度，為解決作業(yè)車間調(diào)度問題提供了一個新途徑。

本文對Multi-Agent系統(tǒng)進行簡要介紹，分析了Multi-Agent系統(tǒng)在制造作業(yè)車間調(diào)度中的應用，提出一種基于Multi-Agent黑板模型的作業(yè)車間調(diào)度方案及框架，并探討了Multi-Agent黑板模型及知識庫規(guī)則。

1 Multi-Agent系統(tǒng)

Agent一般被定義為智能體，Wooldridge[5]指出：Agent能感知環(huán)境，并能自治地運行,一般來說，它具有反應性、自治性、環(huán)境針對性和社會性。

反應性，即Agent能感知周圍環(huán)境,并在環(huán)境發(fā)生變化時及時做出響應。自治性， 即Agent具有主動權，可以不受其他Agent的控制。環(huán)境針對性，即Agent對環(huán)境變化做出針對性的反應。社會性，即多個Agent之間可以通過特定協(xié)議進行通信交互，完成目標。

Multi-Agent系統(tǒng)是指由一組Agent組成的耦合系統(tǒng)， Agent被看成是Multi-Agent系統(tǒng)的微觀層次，每個Agent都有自己的控制域及運行機制，可以實施具有一定“智商”的特定的行為，但不能獨立解決整個任務；而Multi-Agent系統(tǒng)通過對各層次Agent的組織與協(xié)作，可以實現(xiàn)需要更高靈活性、環(huán)境適應性以及柔性的綜合功能，以解決問題。制造車間的各加工設備、工藝數(shù)據(jù)是分散的，各個設備Agent具有自己控制域的完整的信息，但不足以解決所有突發(fā)問題，Agent之間可以通信，異步計算，通過協(xié)作解決任務。由于作業(yè)車間調(diào)度系統(tǒng)的制造任務經(jīng)常是動態(tài)變化的，市場變化、設備故障等不確定性、動態(tài)性和復雜性組合在一起，使調(diào)度變得更加困難，因此將Multi-Agent系統(tǒng)應用到車間作業(yè)調(diào)度問題，為解決車間作業(yè)調(diào)度問題提供了一種有效方法。

2 Multi-Agent系統(tǒng)在制造作業(yè)車間調(diào)度中的應用

作業(yè)車間的調(diào)度是現(xiàn)代制造系統(tǒng)一項最基本、最重要的任務，由于Agent技術具有處理分布式特點的自然屬性，基于Multi-Agent系統(tǒng)的作業(yè)車間調(diào)度問題引起了很多學者的關注。

Maturana等[6]針對分布式制造系統(tǒng)，設計了一種基于Multi-Agent的協(xié)調(diào)機制框架，并且在制造車間進行了實踐應用，研究表明該協(xié)調(diào)框架對其他分布式智能制造系統(tǒng)也同樣適用。Takahashi等[7]將Multi-Agent系統(tǒng)應用于制造企業(yè)關于市場變化的預測上，構建了一個具有共享服務的市場模型，利用Multi-Agent仿真來描述制造車間生產(chǎn)計劃的決策過程。Peng等[8]為解決企業(yè)缺乏集成能力的問題，設計了一組具有專門知識庫的Agent，收集信息并與其他管理系統(tǒng)、人力管理人員和分析人員進行協(xié)作，并通過一個集成場景對Multi-Agent系統(tǒng)進行了仿真。Baker[9]介紹了多種多智能體結構，解釋了調(diào)度算法、工序安排算法和推拉算法等常見的工廠控制算法，并描述了如何在Multi-Agent異構的環(huán)境下實現(xiàn)制造工廠控制算法。Hussain等[10]在分布式制造控制系統(tǒng)中，基于Multi-Agent系統(tǒng)建立了一個系統(tǒng)性能評價機制，以完工時間、平均機器利用率和零件平均等待時間為基準對系統(tǒng)進行評價，對仿真模型進行仿真實驗。

3 基于Multi-Agent黑板模型的作業(yè)車間調(diào)度

現(xiàn)代制造業(yè)系統(tǒng)是分布式開放系統(tǒng)，一直以來都需要面對各種挑戰(zhàn)[11-14]，比如：如何保持高效的市場核心競爭力，如何快速響應市場的動態(tài)需求，不斷提高自身效率等，這些也都是制造業(yè)能健康發(fā)展的核心要素。制造工廠的作業(yè)車間調(diào)度是先進制造系統(tǒng)的基礎和核心技術。因此高效的作業(yè)車間調(diào)度方法與優(yōu)化技術，對于先進制造企業(yè)的現(xiàn)代化具有重要的現(xiàn)實意義。

作業(yè)車間調(diào)度的主要目的是在時間上、空間上合理配置制造車間的有限資源，以滿足企業(yè)生產(chǎn)經(jīng)營目標的要求。傳統(tǒng)車間調(diào)度問題可以看成是所有待加工零件的資源調(diào)度問題，每個零件包含一個工藝工序的集合，每道工序均需要占用機床、刀具等生產(chǎn)資源，按照零件的工藝路線進行加工，其中部分機床加工的工序可以不同。調(diào)度的目的就是合理地分配機床等資源，合理地安排加工時間，使得企業(yè)的經(jīng)濟效益等指標最優(yōu)化。

當客戶需求發(fā)生改變以及機床設備出現(xiàn)故障等問題時，制造車間的作業(yè)配置往往需要動態(tài)調(diào)整，為了及時處理、應對實際生產(chǎn)中經(jīng)常出現(xiàn)的突發(fā)事件和不確定的因素等，本文提出了基于Multi-Agent黑板模型的動態(tài)作業(yè)車間調(diào)度方案。

3.1 Multi-Agent黑板模型

黑板模型[15-18]的基本思想是任務共享，黑板模型可以解決Multi-Agent協(xié)作完成任務的分布計算，管理Agent單元之間的通訊，非常適合于復雜問題的求解。黑板模型由黑板、知識庫與控制模塊3部分組成，其中黑板就是一個共享的任務求解工作空間，知識庫包含求解任務的不同知識。

黑板模型的工作原理為：當有多個Agent需要協(xié)同求解一個問題時，多個Agent可以在這個共享的工作空間交互通信，控制模塊通過一定的策略(比如操作域)來選擇激活某個Agent，由該Agent對指定的任務進行求解。當這個Agent完成求解后，它會將求解結果記錄在黑板上，這樣其他Agent也可發(fā)現(xiàn)并共享這個結果，也可以利用這個結果進行求解，然后再記錄一次求解結果，直到任務解決，獲得滿意結果。黑板模型體系結構示意圖如圖1所示。

圖1 黑板模型的體系結構

3.2 作業(yè)車間調(diào)度方案建模

作業(yè)車間調(diào)度涉及合理分配制造資源。為了采用Multi-Agent黑板模型進行制造作業(yè)車間調(diào)度，首先定義用于作業(yè)車間調(diào)度的Multi-Agent系統(tǒng)：車間管理Agent(MA)，工作單元Agent(WA)，任務管理Agent(TA)，事件Agent(SA)等。

MA，主要完成車間任務分配，制定車間生產(chǎn)計劃、調(diào)度和過程控制等，管理其余Agent的信息交流反饋，MA是全局類型的Agent。

WA，該Agent是由全部加工設備組成的具有一定的制造能力的加工單元，是具體任務的承接者。其知識庫存放各加工設備制造能力、刀具物料存儲情況、加工工序時間等信息。

TA，該Agent接受MA分配的任務，根據(jù)不同的需求分成若干個子任務，將任務發(fā)送到黑板模型。其知識庫存放任務的加工工藝、加工工序、加工時間等知識，對子任務進行分配并解決。

SA，主要根據(jù)突發(fā)事件動態(tài)生成。比如突發(fā)訂單取消或增加情況，設備故障、刀具斷裂、作業(yè)延遲等特殊情況，激活SA，在任務完成后，SA自動銷毀。其知識庫包含事件邏輯推理，比如：IF[突發(fā)增加訂單-保證交貨周期]，THEN[發(fā)布共享任務-設備需求]；IF[設備故障]，THEN[發(fā)布共享任務-設備需求]。

3.3 作業(yè)車間調(diào)度

為了驗證Multi-Agent是如何利用黑板模型實現(xiàn)作業(yè)車間調(diào)度管理，考慮以智能制造系統(tǒng)某一個車間為例進行說明。

車間中包含一系列加工設備：數(shù)控銑床，數(shù)控車床、鉆床、磨床、檢測臺、清洗臺、裝配機械手等。所有的加工設備組成了WA，其中每臺設備均為一個獨立的Agent。假設該車間經(jīng)常生產(chǎn)的零件有3種，分別為P1，P2，P3。零件的加工工序見表1，該表構成了任務管理Agent。

表1 零件加工工序

該車間考慮的突發(fā)情況主要有兩種：一是機械設備突然故障(電氣損壞或者刀具崩裂等)；二是訂單突然增加或減少，這是企業(yè)實際生產(chǎn)中最常見的突發(fā)狀況。將這兩種情況定義為SA，SA激活后，MA引入緊急因子Δ，該因子由MA根據(jù)突發(fā)事件的嚴重程度以及經(jīng)濟損失來確定，一般取值為：1，緊急任務，請立即響應；0，普通任務，請抽空響應；-1，排隊任務，請空閑設備響應。

MA接受車間生產(chǎn)任務后，根據(jù)各零件的工藝要求、時間計劃，分配任務給WA、TA，同時通過通信模塊與各Agent單元保持通信。WA接受來自MA與TA的任務計劃，分配給加工設備單元Agent，并通過通信模塊與加工設備單元Agent、MA、TA保持通信。TA接受MA任務、WA綜合設備信息后，根據(jù)零件特點安排加工子任務，見表1，定義P11表示零件P1的第一個工序，其余類推。

基于Multi-Agent黑板模型的作業(yè)車間調(diào)度架構如圖2所示。基于Multi-Agent的作業(yè)車間調(diào)度為現(xiàn)代化制造車間的動態(tài)管控和調(diào)度提供了一種有效途徑，有可能成為未來智能制造車間的主要運行模式之一。

圖2 基于Multi-Agent黑板模型的作業(yè)車間調(diào)度架構

知識庫規(guī)則定義如下。

設備故障或訂單信息變更等突發(fā)事件發(fā)生：WA向MA報告，接受訂單信息變更或某數(shù)控設備Agent發(fā)來故障信息，需要調(diào)度。MA激活SA，根據(jù)當前設備信息，向黑板發(fā)布任務，并給出緊急因子；TA根據(jù)緊急因子決定是否接受任務，接受任務后，TA進行子任務分配，并向黑板發(fā)送子任務；WA根據(jù)緊急因子決定是否接受任務，設備Agent根據(jù)不同的緊急因子有以下動作：暫停當前任務，接受新任務；不接受任務；完成當前任務后接受新任務。

4 結束語

車間調(diào)度問題是現(xiàn)代制造企業(yè)的重要問題之一，本文開展了基于Multi-Agent的作業(yè)車間調(diào)度策略研究，通過定義車間管理Agent、工作單元Agent、任務管理Agent、事件Agent等作業(yè)車間調(diào)度系統(tǒng)模型，設計Multi-Agent黑板模型及知識庫規(guī)則，提出了基于黑板模型實現(xiàn)作業(yè)車間調(diào)度管理框架，Agent根據(jù)不斷變化的事件及環(huán)境做出的決策，動態(tài)地發(fā)布任務，這樣全局系統(tǒng)就具有較好的反應性和適應性。研究表明，基于Multi-Agent的作業(yè)車間調(diào)度為現(xiàn)代化智能制造車間的動態(tài)管控和調(diào)度提供了一種有效途徑，具有廣闊的應用前景。