多agen車間調(diào)度模型及其仿真

車間規(guī)劃問題（jsps）在公司的生產(chǎn)和業(yè)務活動中起著非常重要的作用。主要用于研究不同設備上的幾個零件。在已知每個操作的加工時間和每個零件的加工順序的情況下，有必要確定每個機器上所有零件的加工開始時間或完成時間或加工序列，以使加工性能指標最佳。由于資源和工藝的限制，jsps成為一個尖銳的問題。目前,解決車間調(diào)度的方法主要有:運籌學方法、基于規(guī)則的方法、系統(tǒng)仿真、解析模型、鄰域搜索、人工智能以及多Agent系統(tǒng)(multi-agentsystem,MAS)等.其中,研究比較熱門的是基于MAS的方法,它主要是模擬合同網(wǎng)(contractnetprotocol,CNP)的競標機制來實現(xiàn)任務在設備上的分配.但是它卻存在著兩個方面的局限:1)從Agent本身角度看,CNP忽略了Agent之間的隱含關聯(lián)和系統(tǒng)任務環(huán)境中的各種關系,Agent的能力受到制約,系統(tǒng)的調(diào)度方案不優(yōu)化;2)從調(diào)度策略角度看,一個不斷調(diào)整、不斷反復的CNP談判過程很難滿足底層車間強調(diào)系統(tǒng)整體性的調(diào)度目標.本文針對車間調(diào)度問題的實際特點,將靜態(tài)的智能算法與動態(tài)的多Agent思想相融合,提出了一種結(jié)合通用部分全局規(guī)劃(generalizedpartialglobalplanning,GPGP)機制與多種智能算法的MAS車間調(diào)度模型,并構(gòu)建了一個柔性強且Agent可自我動態(tài)調(diào)度的仿真系統(tǒng).1基于模型的界面、一個假設、一個假設正如上述局限,UMASS的Decker和Lesser提出了GPGP協(xié)同機制.為了便于建模,兩位學者還提出了一種獨立于問題領域的任務分析環(huán)境模擬語言(taskanalysis,environmentmodelingandsimulation,TAEMS).同時GPGP主要由5種協(xié)同機制構(gòu)成,是一種可以擴充的模塊化協(xié)同方法.1本地調(diào)度單元選擇和排序假設BtA(x)表示代理A在時刻t主觀信仰x,即形成x的信念,當代理和時間在可以忽略不計的情況下,可以寫成B(x),其中x可以是任務組、子任務、可執(zhí)行的方法以及相互關系,也可以是一元或多元變量;D(Τ)表示任務或任務組的最終完成期限;本地調(diào)度單元選擇和排序可執(zhí)行方法的依據(jù)是效用函數(shù)U,U=∑T∈E∑Τ∈EQ(Τ,D(Τ)),其中Q(T,t)表示時刻t的T的質(zhì)量;Do型承諾C(Do(T,q))表示在時刻t滿足Q(T,t)≥q,并且完成任務T;Deadline型承諾C(DL(T,q,tdl))表示在時刻t滿足[Q(T,t)≥q]∧[t≤tdl],并且完成任務T;在本地調(diào)度單元產(chǎn)生的調(diào)度S是包含一系列方法Mn和開始時間tn的集合,S={〈M1,t1〉,〈M2,t2〉,…,〈Mn,tn〉}.2本地協(xié)同關系集合x定義1.集合P稱為AgentA的本地任務?方法信念集合,P={x|task(x)∧?a∈A\A,┐BA(BAr(x)a(x))},其中A為所有Agent的集合,Ar(x)為x的到達時間,task(x)為由x構(gòu)成的所有任務集合(組),subtask(x)為由x構(gòu)成的所有子任務集合.定義2.集合PCR稱為本地協(xié)同關系集合,PCR={r|T1∈P∧T2?P∧[r(T1,T2)∨r(T2,T1)]},其中,r(x,y)表示由x到y(tǒng)的有序關系.定義3.集合CR稱為本地關系集合,它包含PCR以及所有非本地任務間的關系.策略1:①首先建模于“detect-coordination-relationship”,并返回PCR;②將協(xié)同關系、本地任務等相關內(nèi)容與其他Agent進行交流;ifr(T1,T2)∈PCRandT1∈PthenrandT1willcommunicatedbyagentAtothesetofagents{a|BA(Ba(T2))};③擴充更新CR.3策略2.2.2策略2.1:或者傳遞滿足其他Agent承諾的所必須的結(jié)果.策略2.2:或者執(zhí)行策略2.1的同時,還傳遞與任務組相關的最后結(jié)果.策略2.3:或者傳遞所有結(jié)果.除策略2.1外,其余都采取廣播式傳播,策略2.1只傳遞給那些已經(jīng)建立承諾的Agent,即{A∈A|B(BA(C(T)))}.4調(diào)度s中的承諾傳遞定義4.RCR被稱為潛在冗余集合,RCR={r∈CR|[r=subtask(T,M,min)]∧[?M∈M,method(M)]}.策略3:①首先考慮RCR;②對于所有當前時刻t調(diào)度S中的方法,如果它是潛在冗余,那么就與它達成承諾,并把承諾傳遞給其他方法,即[〈M,tM〉∈S]∧[subtask(T,M,min)∈RCR]∧[M∈M]?[C(Do(M,Qest(M,D(M),S)))∈C]∧[comm(M,Others(M),t)∈Γ],其中,comm(M,Mˉˉˉˉ,t)comm(Μ,Μˉ,t)表示方法M與方法MˉˉˉˉΜˉ在時刻t進行通信;③Agent必須避免執(zhí)行該方法,直到所有非本地承諾全部完成;④查看冗余集合中的所有承諾,一旦出現(xiàn),便隨即指派一個Agent去執(zhí)行該承諾;⑤所有其他Agent取消它們的承諾.5潛在的前因子關系定義5.HPCR被稱為潛在前者強關系.諸如enable(T1,T2),只有完成T1,才能完成T2.T1較T2先完成,并且這是強制性的要求,不能更改,因此enable被稱為潛在前者強關系,T1被稱為這種關系的前者.策略4:①HPCR?CR;②考察當前時刻t調(diào)度S中HPCR的前者方法的質(zhì)量,并通過本地和全局的所設定的最終期限,執(zhí)行該前者,即③選擇合適的最早開始時間tearly.對于強制關系,必須及時處理,達成承諾.6機制5：非強制性關系的處理包括促進factor，阻礙hint關系2多agent模型基于GPGP協(xié)同機制的MAS車間調(diào)度系統(tǒng)主要由管理Agent、執(zhí)行Agent、任務Agent以及資源Agent構(gòu)成,并可以彼此通信,如圖1所示:2.1本企業(yè)域內(nèi)作業(yè)減少檢測中心為上級系統(tǒng),生成任務agent,提供統(tǒng)計信息查詢管理Agent是作業(yè)車間和上層計劃系統(tǒng)的接口,如圖1.當它與上層計劃系統(tǒng)相連時,它會依據(jù)車間生產(chǎn)能力,從上層計劃系統(tǒng)接受任務和工藝流程,生成任務Agent,同時向上級系統(tǒng)傳遞任務調(diào)度結(jié)果和作業(yè)完成情況,提供車間統(tǒng)計信息的查詢;當它與任務Agent相連時,它會為任務Agent動態(tài)調(diào)整屬性,接收任務Agent的任務調(diào)度信息和狀態(tài)信息,響應任務Agent的請求并作出相應的處理;當它與執(zhí)行Agent相連時,它會從執(zhí)行Agent獲取車間的可用資源信息,以此進行任務的請求,同時它會根據(jù)車間運轉(zhuǎn)的情況和任務狀態(tài)向執(zhí)行Agent發(fā)出調(diào)度指令.2.2任務系統(tǒng)的調(diào)度優(yōu)化作為任務方和服務方的中介,執(zhí)行Agent的目標是:有效地利用資源Agent提供的加工服務完成任務Agent的加工任務,實現(xiàn)“初始宏觀調(diào)度”.執(zhí)行Agent維護著一個待調(diào)度工序注冊表和一個可用資源注冊表.收到調(diào)度指令后,它首先考察任務集合中的各任務Agent是否已經(jīng)進行任務分解,然后對已分解的工序按照某種規(guī)則(如先到者優(yōu)先等)進行排序,并更新工序注冊表和資源注冊表,最后推理工序在設備上的分配方案.執(zhí)行Agent內(nèi)部實現(xiàn)調(diào)度的模塊是推理機,這是一個以兼容多種智能算法為核心的推理模塊,它可以針對不同任務的調(diào)度要求,從算法庫中選擇不同的智能算法,進行智能推理,實現(xiàn)系統(tǒng)的多目標優(yōu)化.圖2給出了執(zhí)行Agent結(jié)構(gòu)圖:2.3任務agent組成任務Agent隨任務的到來而產(chǎn)生,隨任務的完成而消亡.一個任務Agent代表一類工件,負責該類工件所有工序的加工.任務Agent會根據(jù)管理Agent和資源Agent傳來的信息修改自身屬性,并且通過任務分解模塊把任務分解成子任務或工序.同時,為了配合GPGP協(xié)同機制,它要根據(jù)任務環(huán)境以及各Agent的實際情況,應用TAEMS語言,構(gòu)造全局任務視圖.因此任務Agent由任務分解模塊、協(xié)同模塊和信念數(shù)據(jù)庫3部分組成,如圖3所示:2.4資源agent的“資源調(diào)度”每個資源Agent對應著車間中的一類加工設備,它們維護著這些設備的能力信息和狀態(tài)信息.類似于任務Agent的組成,資源Agent只是額外多出一個調(diào)度模塊,如圖4所示:通過在執(zhí)行代理上注冊,資源Agent向系統(tǒng)發(fā)出任務請求.獲得任務后,它和任務Agent建立起相關連接,更新注冊信息.由于資源Agent內(nèi)部也嵌入了任務分解模塊,它會根據(jù)任務的結(jié)構(gòu)信息,構(gòu)建本地任務視圖.與相關的Agent通信,獲得與其他Agent的任務間關系,建立部分全局任務視圖.再應用GPGP協(xié)調(diào)機制,達成任務間的承諾(承諾包括:完成時間、完成質(zhì)量、通信方式等),形成本地的虛擬任務.一般情況下,GPGP會利用強制性關系,忽略非強制性關系.然后,資源Agent利用調(diào)度模塊對自身的方法和任務進行調(diào)度,其中包括虛擬任務(即承諾).資源Agent執(zhí)行調(diào)度方案后,將其完成信息和結(jié)果送到任務Agent處,至此實現(xiàn)“微觀再調(diào)度”的過程.對于失敗的方法或任務,資源Agent根據(jù)部分全局任務視圖,選擇替換方案,或?qū)⑹⌒畔l(fā)送到執(zhí)行Agent和任務Agent處,由執(zhí)行Agent重新分配,直到系統(tǒng)任務的全部完成.3優(yōu)化和系統(tǒng)準備3.1智能推理機多目標優(yōu)化本系統(tǒng)的二級多目標優(yōu)化主要體現(xiàn)在工序的排序和推理機的智能推理.這主要基于以下原因:1)實際的生產(chǎn)調(diào)度往往是多目標的,如急件任務要求完工時間盡可能早;大批量零件要求降低庫存和在制品數(shù)量,以減少對資金的占用等;2)傳統(tǒng)的單一優(yōu)化算法往往不是顧此失彼,就是效果不理想;3)智能推理機每次可以處理一批任務的調(diào)度,避免了由于單個代理談判模型可能帶來的混亂.對于工序的多目標優(yōu)化,系統(tǒng)根據(jù)調(diào)度的要求,設置了如下8種規(guī)則:臨界比小者優(yōu)先;緩沖期短者優(yōu)先;加工時間短者優(yōu)先;先到者優(yōu)先;后到者優(yōu)先;交貨早者優(yōu)先;交貨晚者優(yōu)先;特權指定優(yōu)先.在“初始宏觀調(diào)度”前,對工序按著一定規(guī)則進行排序,有利于減輕推理機的工作壓力,有利于實現(xiàn)整體任務的多目標優(yōu)化.對于推理機的多目標優(yōu)化,系統(tǒng)根據(jù)每種優(yōu)化算法的特點和適用場合,選擇了如表1所示的適合于JSSP的智能調(diào)度算法.在調(diào)度的過程中,推理機將根據(jù)相關任務的屬性(如:加工設備、工件數(shù)、工序數(shù))、調(diào)度規(guī)模以及優(yōu)化目標,從算法庫中選取合適的優(yōu)化算法,對工序進行優(yōu)化調(diào)度.這樣不僅實現(xiàn)了“初始宏觀調(diào)度”,完成了任務的多目標優(yōu)化,還提高了推理機的優(yōu)化效果,縮短了運算時間.3.2資源調(diào)度如前所述,本系統(tǒng)的調(diào)度步驟如下所示:Step1.更新執(zhí)行Agent的待調(diào)度工序注冊表和可用資源注冊表的信息;Step2.任務Agent分解工序,并構(gòu)建全局任務視圖;Step3.執(zhí)行Agent使用推理機將注冊表中的工序分配到具體資源設備上,實現(xiàn)“初始宏觀調(diào)度”;Step4.在資源Agent中執(zhí)行GPGP協(xié)同控制,實現(xiàn)“微觀再調(diào)度”:Step4.1.從全局任務視圖中,讀取本地任務視圖;Step4.2.相關視圖交換,形成部分全局任務視圖;Step4.3.協(xié)同關系檢測;Step4.4.判斷本地關系集合CR是否為空.如果為不為空,gotoStep4.1;Step4.5.應用GPGP機制,作出承諾并接受虛擬任務;Step4.6.資源Agent的調(diào)度模塊進行本地任務調(diào)度;Step4.7.資源設備執(zhí)行該調(diào)度;Step5.通知執(zhí)行Agent更新任務集合,gotoStep1.4模擬分析的數(shù)據(jù)分析4.1仿真實驗條件在仿真系統(tǒng)中,我們使用了1個管理Agent,1個執(zhí)行Agent,1個任務Agent,6個資源Agent.9個Agent分別運行在同一局域網(wǎng)內(nèi)的3臺PC中,其中管理Agent和任務Agent共用一臺,執(zhí)行Agent一臺,資源Agent一臺,操作系統(tǒng)均為Windows2000server,數(shù)據(jù)庫為MicrosoftSQL2000.同時我們假定:1)仿真實驗的任務為生產(chǎn)某大型復雜機車的靜電變速箱(electrostaticvoltagegear-box)、側(cè)減震器(sideshockabsorber)、葉輪機(impeller)以及萬向軸(universalaxletree),具體任務參數(shù)見表2;2)資源設備涉及立車、搖臂鉆、鏜、加工中心、平衡機以及機床,每個資源Agent有多臺同類設備和工人;3)根據(jù)調(diào)度的要求,工序排序規(guī)則選擇為交貨早者優(yōu)先;4)由于產(chǎn)品的零件龐雜,工序繁瑣,規(guī)模比較大,所以執(zhí)行Agent的智能推理機選取了遺傳禁忌算法對工序進行智能優(yōu)化調(diào)度,具體參數(shù)如下:種群大小為40;選擇概率為0.89;變異率為0.35;迭代代數(shù)為60.系統(tǒng)啟動后,管理Agent接受上層計劃系統(tǒng)傳送的任務訂單,并對其進行維護.任務Agent接到任務訂單后,將任務進行分解,生成加工計劃.然后,任務Agent向執(zhí)行Agent發(fā)布任務訂單,執(zhí)行Agent進行二級多目標優(yōu)化,實現(xiàn)“初始宏觀調(diào)度”,如圖5所示.最后,資源Agent接收推理機的調(diào)度結(jié)果,并進行GPGP協(xié)同控制,完成對系統(tǒng)生產(chǎn)資源和設備的“微觀再調(diào)度”,如圖6所示.4.2定期維護的deadli型承諾我們借鑒了由美國卡羅萊納州海岸大學的Graham博士和特拉華州立大學的Decker博士共同研發(fā)的DECAF仿真Agent軟件,模擬了車間調(diào)度的GPGP協(xié)同機制,較智能地實現(xiàn)了Agent動態(tài)調(diào)度.這里僅以生產(chǎn)“啟動變速箱體”為例進行說明.車床I、車床II、立車、臥鏜以及搖臂鉆,它們通過智能推理機的推理分別獲得鉆孔循環(huán)、鏜孔(bore)以及攻絲(tap)的子任務,這是系統(tǒng)任務“啟動變速箱體”的3個組成部分.實驗事先假定存在如圖7所示的全局任務視圖,其中上銑面和攻絲具有使能關系,下銑面和鏜孔具有促進關系,并設定如表3所示的仿真參數(shù).由設計標準(DTC)Agent調(diào)度程序構(gòu)建的“鉆孔循環(huán)”的本地執(zhí)行順序(或本地時刻表)為:側(cè)銑面(side-mill)→上銑面(top-mill)→下銑面(bottom-mill).在與其他Agent交互任務視圖和能力信息之前,鏜孔和攻絲所擁有的本地任務視圖如圖8和圖9所示:根據(jù)整體任務視圖,鏜孔與相關的Agent通信,交換任務視圖,獲取能力信息,并挖掘其中的任務關系,最終構(gòu)建出自己的部分全局任務視圖,如圖10所示.圖10中下銑面能夠促進鏜孔的質(zhì)量,因此鏜孔作出利用促進關系的決定.于是,鉆孔循環(huán)重新規(guī)劃本地執(zhí)行順序為下銑面→側(cè)銑面→上銑面,用DTC給鏜孔提供一個Deadline型承諾:在時刻5之前,完成下銑面的加工,以至鏜孔在時刻5和時刻10之間能夠被加工,直到它的最后期限.再考慮上銑面與攻絲的關系.類似于鏜孔,攻絲產(chǎn)生的部分全局任務視圖,如圖11所示.由于攻絲與上銑面的使能關系要比鏜孔和下銑面的促進關系重要得多,因此鉆孔循環(huán)必須推翻它和鏜孔的承諾,重新計劃和攻絲合作,形成一個新的Deadline型承諾:在時刻5之前,完成上銑面的加工任務,以致攻絲能夠被執(zhí)行.任務在被執(zhí)行時,資源Agent將會對其所屬設備的生產(chǎn)過程進行監(jiān)控.如圖10,當臥鏜出現(xiàn)故障時,臥鏜的狀態(tài)會由“正?！弊?yōu)椤肮收稀?此時,臥鏜Agent會根據(jù)圖10,發(fā)送信息給相關資源Agent,并將故障臥鏜的狀態(tài)置為“維修”,同時尋找狀態(tài)為“空閑”的臥鏜.倘若找到,將原臥鏜上的工件和工人轉(zhuǎn)移至“空閑”的臥鏜,當故障修理完畢后,臥鏜Agent便將原故障臥鏜狀態(tài)置為“空閑”.倘若臥鏜Agent無法找到其他臥鏜或者無法重新利用GPGP協(xié)同關系進行本地調(diào)度,則將所有在圖10中與臥鏜所對應的功能方法有聯(lián)系的關系類型置為“阻礙”,并且將“失敗”信息發(fā)送到執(zhí)行Agent和啟動變速箱Agent處,由執(zhí)行Agent重新分配,直到系統(tǒng)任務完成為止.4.3gpgp的動態(tài)調(diào)度效果為了驗證GPGP協(xié)同機制的先進,我們分別測試了基于GPGP協(xié)同機制的MAS車間調(diào)度系