基于合同網(wǎng)協(xié)議的工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度研究

陳大林

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

現(xiàn)代制造生產(chǎn)車(chē)間有兩個(gè)關(guān)鍵任務(wù)：工藝路線(xiàn)規(guī)劃和作業(yè)調(diào)度[1]。工藝路線(xiàn)是指生產(chǎn)過(guò)程中產(chǎn)品零部件從毛坯到成品的加工路線(xiàn)，它是制訂零件生產(chǎn)工藝過(guò)程和車(chē)間任務(wù)分配的重要依據(jù)，與刀具、機(jī)床等車(chē)間資源聯(lián)系緊密。工藝路線(xiàn)規(guī)劃就是根據(jù)企業(yè)目標(biāo)以及生產(chǎn)車(chē)間的資源，找出最合適的產(chǎn)品零部件加工工序和加工路線(xiàn)。生產(chǎn)企業(yè)通常安排產(chǎn)品零件和工序數(shù)量多于設(shè)備和工人等資源，避免浪費(fèi)資源以節(jié)省制造成本。作業(yè)調(diào)度的目的就是為零件合理地分配設(shè)備等資源，并根據(jù)給定的工序和路線(xiàn)合理地安排加工時(shí)間，使得企業(yè)的生產(chǎn)效率與效益實(shí)現(xiàn)最優(yōu)化。

作業(yè)調(diào)度問(wèn)題是復(fù)雜問(wèn)題，也是NP(nondeterministic polynomial-bounders)問(wèn)題，隨著制造企業(yè)的市場(chǎng)環(huán)境越來(lái)越具有不確定性，以及客戶(hù)需求不斷改變導(dǎo)致訂單不斷調(diào)整，使得作業(yè)調(diào)度變得更加復(fù)雜。因此，很多學(xué)者[1-3]將工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度優(yōu)化分開(kāi)，單獨(dú)進(jìn)行研究，然而這樣導(dǎo)致制造系統(tǒng)的靈活性不足，生產(chǎn)效率也較為低下。部分學(xué)者[4]嘗試一種把工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度集成的方法：為每個(gè)工件保留多個(gè)工藝路線(xiàn)，作業(yè)調(diào)度時(shí)，根據(jù)車(chē)間作業(yè)實(shí)際情況動(dòng)態(tài)選擇一條最合適的工藝路線(xiàn)。

近年來(lái)，隨著分布式人工智能技術(shù)的發(fā)展，一些智能算法被單獨(dú)用于工藝路線(xiàn)規(guī)劃和作業(yè)調(diào)度。潘全科[5]研究了基于多智能體系統(tǒng)的多目標(biāo)車(chē)間調(diào)度問(wèn)題，建立了多資源、多工藝、多目標(biāo)的動(dòng)態(tài)調(diào)度模型，采用基于周期和事件驅(qū)動(dòng)的調(diào)度策略及動(dòng)態(tài)算法，仿真結(jié)果表明了算法的可行性和優(yōu)越性。文獻(xiàn)[6]介紹了一種基于分層次工藝路線(xiàn)案例庫(kù)、結(jié)合層次分析法進(jìn)行工藝路線(xiàn)檢索的方案，并進(jìn)行了實(shí)例驗(yàn)證。

本文研究了工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度問(wèn)題，對(duì)多智能體系統(tǒng)及其應(yīng)用進(jìn)行了介紹，分析了合同網(wǎng)協(xié)議在多智能體系統(tǒng)中的協(xié)作機(jī)制，將信任度指標(biāo)引入經(jīng)典合同網(wǎng)協(xié)議，并以某軸類(lèi)零件為例，給出了基于合同網(wǎng)協(xié)議的工藝路線(xiàn)規(guī)劃及作業(yè)調(diào)度方案，最后進(jìn)行了總結(jié)。

1 多智能體系統(tǒng)

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

Van[8]將多智能體系統(tǒng)應(yīng)用到工業(yè)過(guò)程控制。首先進(jìn)行任務(wù)分解，并設(shè)計(jì)了多個(gè)Agent，包括跟蹤Agent、過(guò)程Agent等。然后通過(guò)協(xié)作將所有Agent組合成一個(gè)MAS，實(shí)現(xiàn)對(duì)大型設(shè)備的過(guò)程控制。Hussain等[10]針對(duì)分布式制造控制系統(tǒng)，提出了一個(gè)基于Multi-Agent系統(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)。Baker[11]介紹了多種多智能體結(jié)構(gòu)，對(duì)調(diào)度算法、工序安排算法和推拉算法等常見(jiàn)的工廠控制算法進(jìn)行了解釋?zhuān)⒚枋隽巳绾卧贛ulti-Agent異構(gòu)的環(huán)境下實(shí)現(xiàn)制造工廠控制算法。

2 合同網(wǎng)協(xié)議及其應(yīng)用

合同網(wǎng)協(xié)議最早由Smith 和Davis提出[12]，在分布式人工智能領(lǐng)域應(yīng)用非常廣泛。CNP(contract net protocol)經(jīng)常被用來(lái)解決分布式環(huán)境下多節(jié)點(diǎn)之間的任務(wù)協(xié)作問(wèn)題，它是實(shí)現(xiàn)Agent之間有效協(xié)作的一種協(xié)議，也是MAS具有代表性的協(xié)作機(jī)制之一。

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

CNP節(jié)點(diǎn)之間的任務(wù)分配與接受構(gòu)成了類(lèi)似合同的關(guān)系。其工作流程為：產(chǎn)生任務(wù)的節(jié)點(diǎn)Agent(也稱(chēng)為管理Agent)根據(jù)自身的知識(shí)庫(kù)規(guī)則、當(dāng)前工作狀態(tài)等信息，向其他Agent發(fā)布任務(wù)標(biāo)書(shū)；接收到任務(wù)通知的節(jié)點(diǎn)Agent，將根據(jù)自身的知識(shí)庫(kù)規(guī)則、當(dāng)前工作狀態(tài)、預(yù)期收益等決定是否向管理Agent進(jìn)行投標(biāo)操作。當(dāng)節(jié)點(diǎn)Agent發(fā)現(xiàn)一個(gè)適合自身的任務(wù)時(shí)，它會(huì)向管理Agent提交一個(gè)激活請(qǐng)求(該請(qǐng)求可以理解為投標(biāo)標(biāo)的)，而管理Agent可能會(huì)收到多個(gè)激活請(qǐng)求(標(biāo)的)，基于任務(wù)信息、自身知識(shí)庫(kù)規(guī)則、當(dāng)前工作狀態(tài)等，管理Agent將會(huì)選擇一個(gè)最合適的Agent并給它分配任務(wù)，這個(gè)Agent就是中標(biāo)者。管理Agent與節(jié)點(diǎn)Agent之間就簽訂了完成該任務(wù)的合同。

在合同網(wǎng)協(xié)議中,管理Agent和節(jié)點(diǎn)Agent均不需要預(yù)先規(guī)定，其角色也可以根據(jù)需要互換。任何發(fā)起任務(wù)廣播通知的Agent，就成為了管理Agent，而應(yīng)答投標(biāo)的Agent就是節(jié)點(diǎn)Agent。對(duì)于制造系統(tǒng)中的工藝路線(xiàn)規(guī)劃任務(wù)以及作業(yè)調(diào)度任務(wù)，分解后的待求解任務(wù)由承擔(dān)者Agent負(fù)責(zé)完成，一旦出現(xiàn)無(wú)法完成的情況，承擔(dān)者Agent就變?yōu)楣芾鞟gent,向系統(tǒng)發(fā)布廣播通知，承擔(dān)者Agent根據(jù)自身知識(shí)庫(kù)規(guī)則，從返回的投標(biāo)當(dāng)中選擇最優(yōu)的投標(biāo)者(節(jié)點(diǎn)Agent)，將任務(wù)發(fā)送給他，建立對(duì)應(yīng)的合同。

3 基于合同網(wǎng)協(xié)議的工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度方案

工藝路線(xiàn)規(guī)劃與車(chē)間作業(yè)調(diào)度聯(lián)合，有利于提高制造車(chē)間生產(chǎn)效率，提高產(chǎn)品質(zhì)量。由于作業(yè)調(diào)度是NP問(wèn)題，特別是當(dāng)市場(chǎng)訂單變化、設(shè)備故障等意外情況出現(xiàn)時(shí)，需要對(duì)工藝路線(xiàn)、制造車(chē)間設(shè)備、人員以及資源等展開(kāi)協(xié)作，因此本文以生產(chǎn)車(chē)間常見(jiàn)的軸類(lèi)零件為例，分析基于合同網(wǎng)協(xié)議的工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度協(xié)作方案，縮短產(chǎn)品生產(chǎn)周期、提升產(chǎn)品質(zhì)量和企業(yè)經(jīng)濟(jì)效益。

3.1 經(jīng)典合同網(wǎng)協(xié)議

根據(jù)車(chē)間設(shè)備資源情況，軸類(lèi)零件的工藝路線(xiàn)可以有3種：L1，L2，L3。零件加工工序見(jiàn)表1，其中L1為最優(yōu)推薦工藝路線(xiàn)，該表構(gòu)成了任務(wù)管理Agent。

表1 零件加工工序

當(dāng)發(fā)生數(shù)控銑床故障的特殊事件，管理Agent給系統(tǒng)內(nèi)所有Agent發(fā)布一個(gè)標(biāo)記，并記錄任務(wù)需求。管理Agent發(fā)布任務(wù)：1臺(tái)數(shù)控銑床故障，需要數(shù)控銑削設(shè)備。系統(tǒng)內(nèi)其他節(jié)點(diǎn)收聽(tīng)到了任務(wù)廣播，根據(jù)自身知識(shí)庫(kù)規(guī)則，判斷是否在自身能力范圍內(nèi)，當(dāng)前生產(chǎn)條件是否適合激活響應(yīng)任務(wù)，如果系統(tǒng)中有多個(gè)任務(wù)，對(duì)多個(gè)任務(wù)進(jìn)行評(píng)價(jià)，選擇最合適的任務(wù)進(jìn)行投標(biāo)；管理Agent可能會(huì)收到好幾份投標(biāo)書(shū)，它依據(jù)自身知識(shí)庫(kù)規(guī)則，對(duì)投標(biāo)者進(jìn)行評(píng)估，然后選擇最優(yōu)的投標(biāo)者作為中標(biāo)者，并向系統(tǒng)其他Agent發(fā)布中標(biāo)通告，與中標(biāo)者簽訂合同，中標(biāo)節(jié)點(diǎn)Agent激活，完成任務(wù)。系統(tǒng)的協(xié)作流程如圖1所示。

圖1 管理Agent與節(jié)點(diǎn)Agent的協(xié)作流程圖

經(jīng)典CNP可以實(shí)現(xiàn)任務(wù)的求解，但同時(shí)也存在著一些不足，會(huì)對(duì)實(shí)際的協(xié)作過(guò)程及效率有所影響，特別是對(duì)多數(shù)量的節(jié)點(diǎn)Agent系統(tǒng)。主要有以下幾點(diǎn)：

1)任務(wù)發(fā)布。

管理Agent將任務(wù)標(biāo)書(shū)以廣播的形式發(fā)送給系統(tǒng)中所有節(jié)點(diǎn)Agent，但實(shí)際上只有部分節(jié)點(diǎn)Agent有能力去執(zhí)行這些任務(wù)，這可能會(huì)導(dǎo)致通信網(wǎng)絡(luò)堵塞，耗費(fèi)了大量的系統(tǒng)資源。

2)質(zhì)量評(píng)價(jià)。

中標(biāo)Agent完成任務(wù)后，將結(jié)果發(fā)送給管理Agent，但是管理Agent沒(méi)有對(duì)中標(biāo)Agent完成任務(wù)質(zhì)量評(píng)價(jià)，這對(duì)于管理Agent來(lái)說(shuō)，節(jié)點(diǎn)Agent就不存在能力的差別，這樣會(huì)造成系統(tǒng)的求解能力降低。

3.2 改進(jìn)合同網(wǎng)協(xié)議

工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度系統(tǒng)中節(jié)點(diǎn)Agent的數(shù)量較多，且系統(tǒng)對(duì)任務(wù)質(zhì)量要求較高，為了節(jié)省系統(tǒng)資源，提高協(xié)作效率，更好地解決任務(wù)，考慮引入信任度指標(biāo)。

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

3.3 改進(jìn)的合同網(wǎng)協(xié)議工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度協(xié)作方案

參考表1的某軸類(lèi)零件的工藝路線(xiàn)，當(dāng)突發(fā)情況發(fā)生時(shí)，如數(shù)控車(chē)床N1故障，任務(wù)分配協(xié)作的過(guò)程如下：

1)發(fā)標(biāo)。

管理Agent以廣播的形式向投標(biāo)對(duì)象發(fā)送任務(wù)信息，投標(biāo)對(duì)象選擇信任度為T(mén)rust(Nk，N_i,j)的節(jié)點(diǎn)Agent，擬定的標(biāo)書(shū)格式為：

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

其中：Contract ID為合同編號(hào)，即任務(wù)編號(hào)；Manager為管理Agent；Task為任務(wù)描述；Task_Restriction為Manager對(duì)任務(wù)完成的要求；Deadline為Manager規(guī)定的投標(biāo)截止時(shí)間。

2)投標(biāo)。

其余數(shù)控車(chē)床設(shè)備節(jié)點(diǎn)Agent收到標(biāo)書(shū)，首先閱讀任務(wù)和任務(wù)要求項(xiàng)，以及自身知識(shí)庫(kù)，判斷自身的能力及自身的情況(作業(yè)情況、資源情況等)決定是否投標(biāo)，如果決定投標(biāo)，在規(guī)定的5 s內(nèi)進(jìn)行投標(biāo)。

3)中標(biāo)。

管理Agent接收到發(fā)來(lái)的標(biāo)書(shū)，主要考慮節(jié)點(diǎn)Agent的信任度Trust，從中選擇一個(gè)合適的Agent作為中標(biāo)者。初次投標(biāo)選擇隨機(jī)。

4)流標(biāo)。

如果管理Agent沒(méi)有找到合適的中標(biāo)者，或者節(jié)點(diǎn)Agent沒(méi)有在規(guī)定的時(shí)間內(nèi)響應(yīng)，那么管理Agent宣布流標(biāo)，重新招標(biāo)。

5)簽訂合同。

數(shù)控車(chē)床N3節(jié)點(diǎn)Agent作為中標(biāo)者，在接收到管理Agent同意激活指令后，如果因狀態(tài)改變不簽訂合同或在5 s內(nèi)沒(méi)有啟動(dòng)工作，那么管理Agent將轉(zhuǎn)向下一個(gè)狀態(tài)，重新招標(biāo)。

6)任務(wù)結(jié)束。

當(dāng)任務(wù)結(jié)束時(shí)，數(shù)控車(chē)床N3節(jié)點(diǎn)Agent向管理Agent報(bào)告執(zhí)行結(jié)果，管理Agent完成對(duì)數(shù)控車(chē)床N3節(jié)點(diǎn)Agent評(píng)價(jià)，并給出獎(jiǎng)勵(lì)或懲罰信任度值。如果任務(wù)沒(méi)有正常結(jié)束，那么管理Agent將重新招標(biāo)。

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

工藝路線(xiàn)規(guī)劃與車(chē)間調(diào)度問(wèn)題是制造企業(yè)的兩個(gè)核心任務(wù)，本文開(kāi)展了基于合同網(wǎng)協(xié)議的工藝路線(xiàn)規(guī)劃與作業(yè)車(chē)間調(diào)度策略研究，設(shè)計(jì)了經(jīng)典合同網(wǎng)協(xié)議協(xié)作流程，以及信任度指標(biāo)，并對(duì)典型軸類(lèi)零件工藝進(jìn)行分析，給出了基于合同網(wǎng)協(xié)議的工藝路線(xiàn)規(guī)劃與作業(yè)調(diào)度協(xié)作方案。如何高效地綜合工藝路線(xiàn)規(guī)劃與車(chē)間調(diào)度問(wèn)題目前依然是制造企業(yè)的核心問(wèn)題，合同網(wǎng)協(xié)議等多智能體系統(tǒng)的協(xié)作協(xié)議為解決這一問(wèn)題提供了一個(gè)新的思路，其將會(huì)進(jìn)一步促進(jìn)制造業(yè)向智能制造發(fā)展。