陳大林

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

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

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

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

1 Multi-Agent系統(tǒng)

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

反應(yīng)性，即Agent能感知周?chē)h(huán)境,并在環(huán)境發(fā)生變化時(shí)及時(shí)做出響應(yīng)。自治性， 即Agent具有主動(dòng)權(quán)，可以不受其他Agent的控制。環(huán)境針對(duì)性，即Agent對(duì)環(huán)境變化做出針對(duì)性的反應(yīng)。社會(huì)性，即多個(gè)Agent之間可以通過(guò)特定協(xié)議進(jìn)行通信交互，完成目標(biāo)。

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

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

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

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

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

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

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

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

3.1 Multi-Agent黑板模型

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

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

圖1 黑板模型的體系結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

表1 零件加工工序

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

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

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

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

知識(shí)庫(kù)規(guī)則定義如下。

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

4 結(jié)束語(yǔ)

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