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

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

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