基于合同網協議的工藝路線規劃與作業調度研究

陳大林

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

現代制造生產車間有兩個關鍵任務：工藝路線規劃和作業調度[1]。工藝路線是指生產過程中產品零部件從毛坯到成品的加工路線，它是制訂零件生產工藝過程和車間任務分配的重要依據，與刀具、機床等車間資源聯系緊密。工藝路線規劃就是根據企業目標以及生產車間的資源，找出最合適的產品零部件加工工序和加工路線。生產企業通常安排產品零件和工序數量多于設備和工人等資源，避免浪費資源以節省制造成本。作業調度的目的就是為零件合理地分配設備等資源，并根據給定的工序和路線合理地安排加工時間，使得企業的生產效率與效益實現最優化。

作業調度問題是復雜問題，也是NP(nondeterministic polynomial-bounders)問題，隨著制造企業的市場環境越來越具有不確定性，以及客戶需求不斷改變導致訂單不斷調整，使得作業調度變得更加復雜。因此，很多學者[1-3]將工藝路線規劃與作業調度優化分開，單獨進行研究，然而這樣導致制造系統的靈活性不足，生產效率也較為低下。部分學者[4]嘗試一種把工藝路線規劃與作業調度集成的方法：為每個工件保留多個工藝路線，作業調度時，根據車間作業實際情況動態選擇一條最合適的工藝路線。

近年來，隨著分布式人工智能技術的發展，一些智能算法被單獨用于工藝路線規劃和作業調度。潘全科[5]研究了基于多智能體系統的多目標車間調度問題，建立了多資源、多工藝、多目標的動態調度模型，采用基于周期和事件驅動的調度策略及動態算法，仿真結果表明了算法的可行性和優越性。文獻[6]介紹了一種基于分層次工藝路線案例庫、結合層次分析法進行工藝路線檢索的方案，并進行了實例驗證。

本文研究了工藝路線規劃與作業調度問題，對多智能體系統及其應用進行了介紹，分析了合同網協議在多智能體系統中的協作機制，將信任度指標引入經典合同網協議，并以某軸類零件為例，給出了基于合同網協議的工藝路線規劃及作業調度方案，最后進行了總結。

1 多智能體系統

智能體(Agent)和多智能體系統(Multi-Agent system，MAS)的概念起源于人工智能領域，一直以來都是分布式人工智能的主要研究方向之一[7]。由于多智能體系統有著健壯、可靠、高效、可擴展等一系列特性，一直備受學術界和工程應用界關注。在智能制造系統、網絡協同制造、工業機器人、故障診斷與監控、空地交通管理系統等許多領域得到越來越多的應用[3,4,8-10]。

Van[8]將多智能體系統應用到工業過程控制。首先進行任務分解，并設計了多個Agent，包括跟蹤Agent、過程Agent等。然后通過協作將所有Agent組合成一個MAS，實現對大型設備的過程控制。Hussain等[10]針對分布式制造控制系統，提出了一個基于Multi-Agent系統的評價機制，利用完工時間、平均機器利用率和零件平均等待時間為基準對系統進行評價，并對仿真模型進行仿真實驗。Baker[11]介紹了多種多智能體結構，對調度算法、工序安排算法和推拉算法等常見的工廠控制算法進行了解釋，并描述了如何在Multi-Agent異構的環境下實現制造工廠控制算法。

2 合同網協議及其應用

合同網協議最早由Smith 和Davis提出[12]，在分布式人工智能領域應用非常廣泛。CNP(contract net protocol)經常被用來解決分布式環境下多節點之間的任務協作問題，它是實現Agent之間有效協作的一種協議，也是MAS具有代表性的協作機制之一。

徐燕妮[13]分析了多Agent協作合同網協議，并且探討了如何減少多智能體系統通信量、提高系統的執行速度。將信任度、積極度、友好度和信號強度等心智狀態參數引入到CNP中，兼顧了系統協作的成功率和系統協作的性能；趙新宇等[14]提出了一種自私Agent的可信度模型，由于自私Agent在自己能力不足的情況下仍有可能對系統發布的任務進行投標，因此將其引入可信度模型，可避免因自私Agent能力不足而多次協商導致系統性能下降、任務完成質量差等缺點。實驗結果表明，基于可信度模型的Agent協商策略能顯著提高系統性能。

CNP節點之間的任務分配與接受構成了類似合同的關系。其工作流程為：產生任務的節點Agent(也稱為管理Agent)根據自身的知識庫規則、當前工作狀態等信息，向其他Agent發布任務標書；接收到任務通知的節點Agent，將根據自身的知識庫規則、當前工作狀態、預期收益等決定是否向管理Agent進行投標操作。當節點Agent發現一個適合自身的任務時，它會向管理Agent提交一個激活請求(該請求可以理解為投標標的)，而管理Agent可能會收到多個激活請求(標的)，基于任務信息、自身知識庫規則、當前工作狀態等，管理Agent將會選擇一個最合適的Agent并給它分配任務，這個Agent就是中標者。管理Agent與節點Agent之間就簽訂了完成該任務的合同。

在合同網協議中,管理Agent和節點Agent均不需要預先規定，其角色也可以根據需要互換。任何發起任務廣播通知的Agent，就成為了管理Agent，而應答投標的Agent就是節點Agent。對于制造系統中的工藝路線規劃任務以及作業調度任務，分解后的待求解任務由承擔者Agent負責完成，一旦出現無法完成的情況，承擔者Agent就變為管理Agent,向系統發布廣播通知，承擔者Agent根據自身知識庫規則，從返回的投標當中選擇最優的投標者(節點Agent)，將任務發送給他，建立對應的合同。

3 基于合同網協議的工藝路線規劃與作業調度方案

工藝路線規劃與車間作業調度聯合，有利于提高制造車間生產效率，提高產品質量。由于作業調度是NP問題，特別是當市場訂單變化、設備故障等意外情況出現時，需要對工藝路線、制造車間設備、人員以及資源等展開協作，因此本文以生產車間常見的軸類零件為例，分析基于合同網協議的工藝路線規劃與作業調度協作方案，縮短產品生產周期、提升產品質量和企業經濟效益。

3.1 經典合同網協議

根據車間設備資源情況，軸類零件的工藝路線可以有3種：L1，L2，L3。零件加工工序見表1，其中L1為最優推薦工藝路線，該表構成了任務管理Agent。

表1 零件加工工序

當發生數控銑床故障的特殊事件，管理Agent給系統內所有Agent發布一個標記，并記錄任務需求。管理Agent發布任務：1臺數控銑床故障，需要數控銑削設備。系統內其他節點收聽到了任務廣播，根據自身知識庫規則，判斷是否在自身能力范圍內，當前生產條件是否適合激活響應任務，如果系統中有多個任務，對多個任務進行評價，選擇最合適的任務進行投標；管理Agent可能會收到好幾份投標書，它依據自身知識庫規則，對投標者進行評估，然后選擇最優的投標者作為中標者，并向系統其他Agent發布中標通告，與中標者簽訂合同，中標節點Agent激活，完成任務。系統的協作流程如圖1所示。

圖1 管理Agent與節點Agent的協作流程圖

經典CNP可以實現任務的求解，但同時也存在著一些不足，會對實際的協作過程及效率有所影響，特別是對多數量的節點Agent系統。主要有以下幾點：

1)任務發布。

管理Agent將任務標書以廣播的形式發送給系統中所有節點Agent，但實際上只有部分節點Agent有能力去執行這些任務，這可能會導致通信網絡堵塞，耗費了大量的系統資源。

2)質量評價。

中標Agent完成任務后，將結果發送給管理Agent，但是管理Agent沒有對中標Agent完成任務質量評價，這對于管理Agent來說，節點Agent就不存在能力的差別，這樣會造成系統的求解能力降低。

3.2 改進合同網協議

工藝路線規劃與作業調度系統中節點Agent的數量較多，且系統對任務質量要求較高，為了節省系統資源，提高協作效率，更好地解決任務，考慮引入信任度指標。

將信任度引入到節點Agent，作為任務分配的主要指標之一，當管理Agent對某個節點Agent的信任度越高，則將任務分配給該節點Agent的可能性就越大。針對軸類零件，數控銑床完成銑削任務的信任度記為：Trust(Mk，M_i,j,其中M表示銑削設備，k表示第k臺設備，M_i表示銑削加工子工序，j表示能力值(設定初始值0.5)。在多智能系統運行中，信任度指標是動態調整的，比如：銑削設備M2，在加工銑鍵槽M_2的任務中，完成的質量好，系統會給能力值j加上一個獎勵系數Δaward。反之，如果完成的質量不好，系統會給能力值j減去一個懲罰系數Δaward。引入信任度是激活了Agent的競爭機制，有利于多智能體系統對Agent的掌握。

3.3 改進的合同網協議工藝路線規劃與作業調度協作方案

參考表1的某軸類零件的工藝路線，當突發情況發生時，如數控車床N1故障，任務分配協作的過程如下：

1)發標。

管理Agent以廣播的形式向投標對象發送任務信息，投標對象選擇信任度為Trust(Nk，N_i,j)的節點Agent，擬定的標書格式為：

Contract={Contract ID，Manager，Task，Task_Restriction，Deadline}

其中：Contract ID為合同編號，即任務編號；Manager為管理Agent；Task為任務描述；Task_Restriction為Manager對任務完成的要求；Deadline為Manager規定的投標截止時間。

2)投標。

其余數控車床設備節點Agent收到標書，首先閱讀任務和任務要求項，以及自身知識庫，判斷自身的能力及自身的情況(作業情況、資源情況等)決定是否投標，如果決定投標，在規定的5 s內進行投標。

3)中標。

管理Agent接收到發來的標書，主要考慮節點Agent的信任度Trust，從中選擇一個合適的Agent作為中標者。初次投標選擇隨機。

4)流標。

如果管理Agent沒有找到合適的中標者，或者節點Agent沒有在規定的時間內響應，那么管理Agent宣布流標，重新招標。

5)簽訂合同。

數控車床N3節點Agent作為中標者，在接收到管理Agent同意激活指令后，如果因狀態改變不簽訂合同或在5 s內沒有啟動工作，那么管理Agent將轉向下一個狀態，重新招標。

6)任務結束。

當任務結束時，數控車床N3節點Agent向管理Agent報告執行結果，管理Agent完成對數控車床N3節點Agent評價，并給出獎勵或懲罰信任度值。如果任務沒有正常結束，那么管理Agent將重新招標。

4 結束語

工藝路線規劃與車間調度問題是制造企業的兩個核心任務，本文開展了基于合同網協議的工藝路線規劃與作業車間調度策略研究，設計了經典合同網協議協作流程，以及信任度指標，并對典型軸類零件工藝進行分析，給出了基于合同網協議的工藝路線規劃與作業調度協作方案。如何高效地綜合工藝路線規劃與車間調度問題目前依然是制造企業的核心問題，合同網協議等多智能體系統的協作協議為解決這一問題提供了一個新的思路，其將會進一步促進制造業向智能制造發展。