面向開放式結(jié)構(gòu)產(chǎn)品的智能制造車間實(shí)時(shí)調(diào)度方法

吳曉強(qiáng)，田松齡，鄭淑賢，項(xiàng)忠霞

(1.天津大學(xué) 機(jī)構(gòu)理論與裝備設(shè)計(jì)教育部重點(diǎn)實(shí)驗(yàn)室，天津 300354；2.內(nèi)蒙古民族大學(xué) 機(jī)械工程學(xué)院，內(nèi)蒙古 通遼 028000；3.天津城建大學(xué) 控制與機(jī)械工程學(xué)院，天津 300384；4.天津市泰森數(shù)控科技有限公司，天津 300000)

0 引言

個(gè)性化、多功能是產(chǎn)品保持生命力的唯一途徑。隨著用戶在產(chǎn)品設(shè)計(jì)和制造過(guò)程中參與程度越來(lái)越高，開放式結(jié)構(gòu)產(chǎn)品(Open Architecture Product, OAP)既可以最大程度地滿足用戶對(duì)產(chǎn)品個(gè)性化和多功能需求，又可以滿足企業(yè)對(duì)低成本的追求[1]。OAP分為通用模塊、定制模塊和個(gè)性化模塊，這種劃分不僅有利于在設(shè)計(jì)環(huán)節(jié)縮短研發(fā)周期，還可以在制造環(huán)節(jié)提高生產(chǎn)效率并且降低制造成本。具體而言，通用模塊可以在企業(yè)現(xiàn)有制造能力下大規(guī)模實(shí)施生產(chǎn)，而企業(yè)只需對(duì)現(xiàn)有制造系統(tǒng)進(jìn)行必要的重構(gòu)即可滿足定制模塊和個(gè)性化模塊的制造需求。這要求制造系統(tǒng)更加敏捷和靈活，也對(duì)生產(chǎn)調(diào)度系統(tǒng)提出了更高的要求。

車間作為相對(duì)獨(dú)立又完整的制造系統(tǒng)，一般可以涵蓋制造系統(tǒng)中各種復(fù)雜的物質(zhì)流、信息流和能量流的轉(zhuǎn)化，因此通常是研究制造資源配置、生產(chǎn)優(yōu)化調(diào)度和制造系統(tǒng)管控的最小物化單位。車間調(diào)度，即對(duì)車間生產(chǎn)過(guò)程進(jìn)行作業(yè)計(jì)劃，并在執(zhí)行過(guò)程中合理配置制造資源。根據(jù)作業(yè)的加工特點(diǎn)，可將車間調(diào)度問(wèn)題分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。隨著調(diào)度理論及應(yīng)用研究的深入，研究者們開始逐漸關(guān)注生產(chǎn)活動(dòng)中出現(xiàn)的各類不確定性異常因素，如作業(yè)的加工超時(shí)、機(jī)床故障等。本文針對(duì)以機(jī)床故障為代表的異常事件擾動(dòng)問(wèn)題，研究了動(dòng)態(tài)重調(diào)度策略和算法，以保證車間系統(tǒng)運(yùn)行的高可靠性。

1 研究現(xiàn)狀

目前國(guó)內(nèi)外對(duì)動(dòng)態(tài)車間的研究主要集中在魯棒預(yù)調(diào)度、預(yù)—反應(yīng)式調(diào)度和完全反應(yīng)式調(diào)度3種類型調(diào)度策略。魯棒預(yù)調(diào)度是指在進(jìn)行調(diào)度的時(shí)候充分考慮車間生產(chǎn)過(guò)程中可能發(fā)生的各種動(dòng)態(tài)事件，根據(jù)現(xiàn)有信息預(yù)先生成一個(gè)調(diào)度方案，并保證該調(diào)度方案能在各種動(dòng)態(tài)事件發(fā)生時(shí)不至于過(guò)分降低性能，但可能導(dǎo)致機(jī)床利用率較低，造成資源浪費(fèi)等[2];預(yù)—反應(yīng)式調(diào)度首先要在沒(méi)有考慮各種干擾的情況下制定一個(gè)預(yù)調(diào)度方案，在動(dòng)態(tài)事件發(fā)生后對(duì)預(yù)調(diào)度方案進(jìn)行修改得到新的調(diào)度方案，缺點(diǎn)是需要獲得干擾事件完備信息[3];完全反應(yīng)式調(diào)度是在沒(méi)有預(yù)先設(shè)置調(diào)度方案情況下根據(jù)車間當(dāng)前的實(shí)際情形做出實(shí)時(shí)調(diào)度或者在線調(diào)度，缺點(diǎn)是同樣是需要獲得干擾事件完備信息以及重調(diào)度成本較高[4]。

傳統(tǒng)的動(dòng)態(tài)調(diào)度策略和方法在對(duì)待異常事件擾動(dòng)時(shí)，一般假設(shè)擾動(dòng)信息是完備的。以機(jī)床故障為例，在執(zhí)行重調(diào)度時(shí)假設(shè)故障修復(fù)時(shí)間已知或者服從指數(shù)分布。但這些信息在實(shí)際生產(chǎn)過(guò)程中往往是未知的，因此采用實(shí)時(shí)調(diào)度的方法更適合實(shí)際制造系統(tǒng)。實(shí)時(shí)調(diào)度是一種特殊的動(dòng)態(tài)調(diào)度方法，由于異常事件信息不完備，只能在當(dāng)前任務(wù)完成后，根據(jù)機(jī)床可用情況，在當(dāng)前待完成任務(wù)集中實(shí)時(shí)地選擇下一任務(wù)。實(shí)時(shí)調(diào)度是具有自適應(yīng)機(jī)制的調(diào)度方法，即當(dāng)監(jiān)測(cè)到動(dòng)態(tài)事件發(fā)生時(shí)，制造系統(tǒng)可以不借助任何外部控制實(shí)時(shí)地對(duì)自己的調(diào)度作出有效變化[5]。

目前，常用的實(shí)時(shí)調(diào)度方法主要有基于排序的方法和基于規(guī)則的方法[6]?；谂判虻姆椒òň植克阉鞣?、模擬退火法、遺傳算法、蟻群算法、列表尋優(yōu)法等，這類方法先確定可行性加工順序，然后對(duì)加工順序進(jìn)行優(yōu)化，最后確定每個(gè)操作的加工時(shí)間。雖然這些方法可以得到最優(yōu)的計(jì)劃方案，但共同的不足就是計(jì)算量大、收斂速度慢，從而使得解決問(wèn)題的時(shí)間主要消耗在求解問(wèn)題上?；谝?guī)則的方法是車間調(diào)度最傳統(tǒng)的方法，由于其調(diào)度規(guī)則計(jì)算復(fù)雜度低、易于實(shí)現(xiàn)，可以應(yīng)用于動(dòng)態(tài)生產(chǎn)作業(yè)計(jì)劃系統(tǒng)中，然而它不存在一個(gè)全局最優(yōu)的調(diào)度規(guī)則。

隨著感知技術(shù)、物聯(lián)網(wǎng)和服務(wù)等技術(shù)的進(jìn)步，近年來(lái)出現(xiàn)了一些新的范式試圖描述下一代制造系統(tǒng)的需求和特征，如信息物理系統(tǒng)(Cyber-Physical-Systems, CPS)、云制造、智能制造(工業(yè)4.0)和社會(huì)制造等[7]。制造系統(tǒng)運(yùn)行智能化是新興制造范式的核心目標(biāo)之一，這要求下一代制造系統(tǒng)具備自感知、自決策、自執(zhí)行和快速重構(gòu)能力。計(jì)算機(jī)和通訊技術(shù)的融合為這種系統(tǒng)創(chuàng)造了新的可能。

制造物聯(lián)網(wǎng)(Internet of Medical Things, IoMT)可以成為制造系統(tǒng)中物理系統(tǒng)與信息系統(tǒng)之間的橋梁，通過(guò)感知技術(shù)、網(wǎng)絡(luò)技術(shù)、數(shù)字孿生技術(shù)、人工智能技術(shù)和嵌入式技術(shù)等實(shí)現(xiàn)面向制造的信息空間和物理空間的深度融合。IoMT可應(yīng)用于制造車間或制造系統(tǒng)的設(shè)計(jì)和運(yùn)行過(guò)程中的狀態(tài)監(jiān)測(cè)、生產(chǎn)要素配置、工藝優(yōu)化、過(guò)程控制、物流、制造服務(wù)和產(chǎn)品服務(wù)等多種場(chǎng)景，是一種新的智能制造使能技術(shù)[8]。制造系統(tǒng)的每個(gè)物理實(shí)體都能夠識(shí)別和通訊，能夠支持生產(chǎn)系統(tǒng)運(yùn)行，從而使制造系統(tǒng)具備極大的靈活性[9]。

由于傳感器類型、傳感器數(shù)量和信息采集參數(shù)的不同，在事件監(jiān)測(cè)中存在冗余、無(wú)法有效感知等情況，單純依靠軟件驗(yàn)證和邏輯全覆蓋的方法是很難奏效的。目前，已有越來(lái)越多的形式化驗(yàn)證方法來(lái)輔助解決IoMT下狀態(tài)監(jiān)測(cè)和事件感知難題，包括時(shí)間自動(dòng)機(jī)(Timed Automata, TA)[10]、Petri網(wǎng)[11]和圖論方法[12]等。這些方法可以在早期發(fā)現(xiàn)車間系統(tǒng)設(shè)計(jì)中的冗余、不完備和錯(cuò)誤等問(wèn)題，并可以在車間系統(tǒng)運(yùn)行過(guò)程中實(shí)時(shí)監(jiān)測(cè)出各種擾動(dòng)系統(tǒng)正常運(yùn)行的異常事件，從而提高車間系統(tǒng)設(shè)計(jì)和狀態(tài)監(jiān)測(cè)的可靠性。

IoMT環(huán)境下，制造系統(tǒng)具備極大的靈活性。一般而言，制造系統(tǒng)中任何物理實(shí)體都可以連接到IoMT上，它們之間既可以獨(dú)立完成任務(wù)也可以協(xié)作完成更為復(fù)雜的任務(wù)[13]。為加強(qiáng)IoMT環(huán)境下制造車間中各組件之間的協(xié)作，一種比較可行的方法是將制造車間系統(tǒng)設(shè)想為基于代理(Agent)的分布式協(xié)作系統(tǒng)。這種情況下，每個(gè)參與生產(chǎn)的物理實(shí)體背后都有一個(gè)特定的Agent來(lái)管理自身與其他實(shí)體間的協(xié)作，可以實(shí)現(xiàn)主動(dòng)收集數(shù)據(jù)并與其他Agent協(xié)作執(zhí)行任務(wù)，同時(shí)可以與其他實(shí)體共同協(xié)作完成制造車間狀態(tài)的實(shí)時(shí)更新和生產(chǎn)過(guò)程的管控[14]。

總之，目前復(fù)雜擾動(dòng)環(huán)境下車間重調(diào)度研究都是假設(shè)擾動(dòng)信息完備或者假設(shè)服從某種概率分布，從而實(shí)施重調(diào)度。很少有研究涉及不完備擾動(dòng)信息下車間生產(chǎn)擾動(dòng)恢復(fù)問(wèn)題?；贗oMT的多Agent方法可以實(shí)現(xiàn)對(duì)車間調(diào)度方案執(zhí)行情況的動(dòng)態(tài)跟蹤，即執(zhí)行車間實(shí)時(shí)狀態(tài)的監(jiān)測(cè)和動(dòng)態(tài)調(diào)度。

在探究近期國(guó)內(nèi)外相關(guān)研究的基礎(chǔ)上，本文提出了自適應(yīng)動(dòng)態(tài)車間調(diào)度的基本框架、車間系統(tǒng)信息描述方法和自適應(yīng)調(diào)度機(jī)理；設(shè)計(jì)了基于Petri網(wǎng)和蟻群算法的車間調(diào)度和重調(diào)度算法并運(yùn)用到實(shí)際的車間實(shí)時(shí)調(diào)度中。

2 車間實(shí)時(shí)調(diào)度問(wèn)題描述

2.1 問(wèn)題描述

車間環(huán)境下生產(chǎn)系統(tǒng)由若干臺(tái)機(jī)床組成，可以同時(shí)加工多種工件。車間調(diào)度問(wèn)題是根據(jù)加工資源分布和工藝約束確定工件的加工順序、加工機(jī)器，以獲得特定的性能指標(biāo)最優(yōu)。最小化完工期Cmax是迄今研究最多最深入的指標(biāo)形式之一。本文以最復(fù)雜的一類車間調(diào)度問(wèn)題——柔性作業(yè)車間調(diào)度問(wèn)題(Flexible Job-shop Scheduling Problem, FJSP)作為研究對(duì)象。

如表1所示為4×5車間調(diào)度實(shí)例，其中，“/”前的數(shù)據(jù)為可使用加工的機(jī)床編號(hào)，“/”后的數(shù)據(jù)為在選用機(jī)床上對(duì)應(yīng)的處理時(shí)間。

表1 車間調(diào)度問(wèn)題的加工工藝信息

續(xù)表1

2.2實(shí)時(shí)重調(diào)度問(wèn)題描述

車間環(huán)境中異常事件的干擾是不可避免的。以機(jī)床故障為例，必須在一定時(shí)間實(shí)施重調(diào)度才能使生產(chǎn)系統(tǒng)運(yùn)行平穩(wěn)。由于機(jī)床故障的維修結(jié)束時(shí)間不確定，重調(diào)度時(shí)必須強(qiáng)調(diào)3個(gè)方面：①對(duì)不同的維修結(jié)束時(shí)間都具有自適應(yīng)能力；②重調(diào)度不能過(guò)于頻繁；③重調(diào)度后方案仍需滿足最小化完工期min(Cmax)。

以表1所示車間系統(tǒng)為例，在tb=14tick時(shí)機(jī)床Mb=M3發(fā)生故障，此時(shí)需要實(shí)時(shí)監(jiān)控故障機(jī)床的狀態(tài)stk。td時(shí)刻機(jī)床Mb有兩種狀態(tài)：故障和修復(fù)。機(jī)床故障狀態(tài)定義為(2,Δtb)，其中Δtb=td-tb；機(jī)床修復(fù)狀態(tài)定義為(1,tr)，其中tr=td-tb。因此，故障機(jī)床的實(shí)時(shí)狀態(tài)可以表示為：

(1)

如果在td時(shí)刻不發(fā)生重調(diào)度，調(diào)度結(jié)果如圖1a所示；如果發(fā)生重調(diào)度，調(diào)度結(jié)果如圖1b所示。顯然，重調(diào)度的結(jié)果一般會(huì)好于不發(fā)生重調(diào)度的結(jié)果，但是重調(diào)度后各工序相對(duì)于原始調(diào)度變化較大，調(diào)整成本較高。

3 車間環(huán)境生產(chǎn)系統(tǒng)實(shí)時(shí)調(diào)度模型

3.1 基于自動(dòng)機(jī)的異常事件監(jiān)測(cè)模型

在車間生產(chǎn)過(guò)程中，存在大量的擾動(dòng)因素，如機(jī)器設(shè)備故障、緊急訂單和訂單取消等。這些異常擾動(dòng)事件的存在，使車間實(shí)際運(yùn)行狀況同計(jì)劃之間發(fā)生偏差，表現(xiàn)為工序完成加工時(shí)間與初始調(diào)度工序預(yù)計(jì)完成時(shí)間不一致。即使一個(gè)工序的偏差，也會(huì)直接影響其相關(guān)聯(lián)工序的實(shí)際執(zhí)行，進(jìn)而可能導(dǎo)致整個(gè)系統(tǒng)生產(chǎn)執(zhí)行情況急劇惡化。

異常擾動(dòng)事件的分類方法有很多，一般分為資源相關(guān)擾動(dòng)事件和任務(wù)相關(guān)擾動(dòng)事件。

(1)資源相關(guān)擾動(dòng)事件

資源相關(guān)擾動(dòng)事件包括機(jī)器故障、機(jī)器維護(hù)、操作中斷、工具磨損、誤操作等。資源相關(guān)擾動(dòng)事件造成的影響為機(jī)器突發(fā)性或預(yù)先性不可用，即在某段確定或者隨機(jī)的時(shí)間區(qū)間內(nèi)無(wú)法提供加工服務(wù)。

(2)任務(wù)相關(guān)擾動(dòng)事件

任務(wù)相關(guān)擾動(dòng)事件包括工件優(yōu)先級(jí)變化、計(jì)劃外新工件到達(dá)、工期變化、工件撤銷、工件返工等。任務(wù)相關(guān)擾動(dòng)事件造成工件就緒時(shí)間延遲，工件優(yōu)先級(jí)提高從而需要緊急處理，新工件到達(dá)使得加工資源相對(duì)不足。

異常事件的擾動(dòng)導(dǎo)致車間實(shí)際生產(chǎn)過(guò)程中存在很大的隨機(jī)性、時(shí)變性和不確定性。車間生產(chǎn)過(guò)程監(jiān)測(cè)的目標(biāo)是跟蹤在制品的生產(chǎn)過(guò)程并及時(shí)發(fā)現(xiàn)、解析生產(chǎn)過(guò)程中的異常事件。RFID電子標(biāo)簽提供了可以讀寫的數(shù)據(jù)載體的功能，它可以記錄在制品在生產(chǎn)過(guò)程中的身份(IDentification, ID)和當(dāng)前狀態(tài)。一個(gè)完整的RFID系統(tǒng)通常包括讀寫器、標(biāo)簽、中間件、傳輸網(wǎng)絡(luò)和上層應(yīng)用等。RFID異常事件監(jiān)測(cè)中間件本質(zhì)上是將狀態(tài)模型和異常事件監(jiān)測(cè)模型引入到中間件中形成異常事件監(jiān)測(cè)中間件。

在狀態(tài)模型中，時(shí)間自動(dòng)機(jī)模型用來(lái)建立監(jiān)測(cè)參數(shù)與復(fù)雜事件模式的連接，并提供更清晰便捷的形式化語(yǔ)言及相應(yīng)編譯器?；跔顟B(tài)模型的RFID異常事件監(jiān)測(cè)中間件處理事件的過(guò)程是根據(jù)標(biāo)簽讀取事件,最終解析到異常事件。因此，根據(jù)本研究的需求也包含簡(jiǎn)單事件處理模塊、復(fù)雜事件處理模塊和異常事件處理模塊3個(gè)模塊。RFID異常事件監(jiān)測(cè)中間件中狀態(tài)模型的執(zhí)行流程如圖2所示。

3.2 基于多代理系統(tǒng)的實(shí)時(shí)調(diào)度模型

多代理(Multi-Agent)方法提供了一種動(dòng)態(tài)靈活、能快速響應(yīng)車間運(yùn)行環(huán)境變化的生產(chǎn)管控方法。利用Multi-Agent技術(shù)，可以提升制造信息感知過(guò)程中的物聯(lián)化、智能化處理程度。IoMT下多Agent系統(tǒng)運(yùn)行模型如圖3所示，模型的數(shù)據(jù)結(jié)構(gòu)和接口之間的關(guān)系用有向線段表示。該模型由4種類型的Agent構(gòu)成：運(yùn)輸Agent(Transport Entity Agent, TEA)、調(diào)度Agent(Scheduling Agent, SA)、設(shè)備Agent(Machine Entity Agents, MEA)和任務(wù)Agent(Task Agent, TA)。TEA表示車間內(nèi)工件的運(yùn)輸，SA表示工序優(yōu)先級(jí)的計(jì)算，MEA表示車間中的機(jī)床、倉(cāng)儲(chǔ)物流設(shè)備，TA表示車間中加工的工件。

如圖4所示為制造系統(tǒng)Agent之間主要的交互過(guò)程，以及當(dāng)異常事件擾動(dòng)發(fā)生時(shí)Agent系統(tǒng)的重調(diào)度機(jī)制。

4 車間環(huán)境生產(chǎn)系統(tǒng)實(shí)時(shí)調(diào)度方法

4.1 組合式調(diào)度規(guī)則表達(dá)

智能搜索算法在求解車間調(diào)度問(wèn)題時(shí)，可以得到良好的最優(yōu)近似解，但是隨著問(wèn)題規(guī)模的增大以及不確定因素的擾動(dòng)，計(jì)算成本往往很高，很難滿足車間實(shí)時(shí)調(diào)度要求?；诜峙湟?guī)則調(diào)度方法的求解時(shí)間復(fù)雜度低，響應(yīng)速度快，與智能搜索算法相比更適合應(yīng)用在實(shí)時(shí)性要求較高的場(chǎng)景中。

分配規(guī)則又稱為啟發(fā)式調(diào)度規(guī)則，是制造系統(tǒng)車間調(diào)度的一種傳統(tǒng)方法。車間調(diào)度分配規(guī)則實(shí)際上是貪婪策略在車間調(diào)度領(lǐng)域的應(yīng)用，即調(diào)度優(yōu)化只針對(duì)局部和短期目標(biāo)，簡(jiǎn)化計(jì)算模型，提高計(jì)算速度。車間調(diào)度分配規(guī)則缺乏全局優(yōu)化，但由于生產(chǎn)環(huán)境的不確定性越來(lái)越大，算法的全局優(yōu)化對(duì)系統(tǒng)運(yùn)行的影響越來(lái)越小。相比之下，該算法的有效性和可實(shí)現(xiàn)性成為人們關(guān)注的焦點(diǎn)。分配規(guī)則具有計(jì)算復(fù)雜度低、易于實(shí)現(xiàn)、實(shí)時(shí)性高和具有一定優(yōu)化能力等優(yōu)點(diǎn)。因此，資源分配規(guī)則可以用來(lái)實(shí)現(xiàn)調(diào)度方案的快速更新。

根據(jù)車間調(diào)度的特點(diǎn)，調(diào)度規(guī)則不僅需要確定處理順序，還需要選擇處理設(shè)備，因此可以分為確定工序的加工順序和為工序選擇加工設(shè)備兩類。常見(jiàn)的車間調(diào)度和分配規(guī)則具體描述如下：

(1)加工時(shí)間最短規(guī)則(Shortest Processing Time, SPT) 工序優(yōu)先選擇加工時(shí)間短的機(jī)器加工。

(2)最早完成加工規(guī)則(Earliest Completion Processing, ECP) 工序優(yōu)先選擇可以最早完成該工序加工任務(wù)的機(jī)器加工。

(3)剩余工序最多規(guī)則(Most Work Remaining, MWR) 優(yōu)先選擇剩余工序多的工件進(jìn)行加工。

(4)剩余工序最多規(guī)則(Least Work Remaining, LWR) 優(yōu)先選擇剩余工序少的工件進(jìn)行加工。

(5)剩余加工時(shí)間最多規(guī)則(Maximum Processing Remaining, MPR) 優(yōu)先選擇剩余加工時(shí)間多的工件進(jìn)行加工。

(6)剩余加工時(shí)間最少規(guī)則(Least Processing Remaining, LPR) 優(yōu)先選擇剩余加工時(shí)間少的工件進(jìn)行加工。

簡(jiǎn)單分配規(guī)則是根據(jù)不同的調(diào)度優(yōu)化目標(biāo)分別提出的。通常情況下，一個(gè)優(yōu)先級(jí)規(guī)則只能對(duì)單個(gè)調(diào)度目標(biāo)問(wèn)題進(jìn)行優(yōu)化，包括工件加工時(shí)間、最小完成時(shí)間、交貨期和均衡負(fù)載等。FJSP通常包括兩個(gè)子問(wèn)題：確定工序的加工順序和選擇加工設(shè)備。使用單一簡(jiǎn)單分配規(guī)則時(shí)，其優(yōu)化性能一般較差且穩(wěn)定性不理想，難以滿足調(diào)度的要求。

將多種簡(jiǎn)單分配規(guī)則組合到一起形成新的組合分配規(guī)則，往往可以起到取長(zhǎng)補(bǔ)短的作用，得到的解優(yōu)化效果較好，且針對(duì)不同規(guī)模的調(diào)度問(wèn)題穩(wěn)定性較好。按照規(guī)則的組合方式分類，組合分配規(guī)則可以分為線性組合分配規(guī)則和非線性組合分配規(guī)則兩種。前者需要確定規(guī)則的數(shù)量和權(quán)重，由于規(guī)則之間可能存在相關(guān)或者沖突關(guān)系，且量綱可能不統(tǒng)一，需要做大量的組合規(guī)則的挖掘和調(diào)整才能取得相對(duì)滿意的結(jié)果，這直接制約了該組合方式在求解FJSP等復(fù)雜問(wèn)題或大規(guī)模問(wèn)題時(shí)的應(yīng)用。非線性組合規(guī)則不局限于線性加權(quán)，靈活性更好，比較適合求解復(fù)雜、大規(guī)模車間調(diào)度問(wèn)題。

在求解FJSP時(shí)，本文提出一種分層非線性組合規(guī)則方法，可以根據(jù)不同的優(yōu)先級(jí)規(guī)則分別解決一個(gè)子問(wèn)題，并通過(guò)組合得到調(diào)度問(wèn)題的解。若將每種規(guī)則看做一個(gè)SA，則最終的調(diào)度方案可以看做是兩個(gè)SA之間的協(xié)商(規(guī)則組合)。本研究將求解選擇加工設(shè)備子問(wèn)題SA(規(guī)則)稱為一級(jí)SA(規(guī)則)，求解工序的加工順序子問(wèn)題SA(規(guī)則)稱為二級(jí)SA(規(guī)則)。根據(jù)車間調(diào)度問(wèn)題的特點(diǎn)，提出了與優(yōu)化最小化完工期min(Cmax)相關(guān)的4種組合規(guī)則：SPT和MWR、SPT和MPR、SPT和ECP、ECP和MPR。

4.2 分層組合規(guī)則實(shí)時(shí)調(diào)度方法流程

假定已經(jīng)確定了最有利于實(shí)現(xiàn)調(diào)度目標(biāo)要求的分層組合規(guī)則，基于該組合規(guī)則下的實(shí)時(shí)調(diào)度方法流程如圖5所示，包含如下5個(gè)具體步驟：

步驟1SA檢視TA中所有未完成工序，生成等待加工工序集合O，并為O中每一個(gè)等待加工工序生成可加工設(shè)備集合OM。

步驟2SA檢視MEA中所有加工設(shè)備的工作狀態(tài)，生成加工設(shè)備最早空閑時(shí)間集合Tidle。

步驟3用一級(jí)SA(規(guī)則)排序OM中的元素，根據(jù)Tidle計(jì)算優(yōu)先級(jí)并生成隊(duì)列QM。

步驟4用二級(jí)SA(規(guī)則)排序O中的元素，按照優(yōu)先級(jí)生成隊(duì)列Q，把其中優(yōu)先級(jí)最高的工序記作QT。

步驟5工序QT跟加工設(shè)備隊(duì)列QM中的元素按照優(yōu)先級(jí)順序進(jìn)行匹配，完成工序調(diào)度，返回步驟1，直到TA沒(méi)有等待加工工序。

實(shí)現(xiàn)制造系統(tǒng)健康穩(wěn)定運(yùn)行就必須保證調(diào)度時(shí)間與實(shí)際執(zhí)行時(shí)間協(xié)調(diào)一致，這同時(shí)也是檢測(cè)和處理異常事件的基礎(chǔ)。為保證任務(wù)檢測(cè)的準(zhǔn)確性，采用調(diào)度模型與實(shí)際生產(chǎn)過(guò)程同步時(shí)間推進(jìn)機(jī)制，調(diào)度模型中每當(dāng)一個(gè)新動(dòng)作觸發(fā)時(shí)，都會(huì)通過(guò)制造執(zhí)行系統(tǒng)將動(dòng)作指令發(fā)送給車間設(shè)備。與此同時(shí)，將暫停調(diào)度模型的運(yùn)行，直到執(zhí)行現(xiàn)場(chǎng)反饋回其對(duì)應(yīng)的動(dòng)作狀態(tài)發(fā)生了變化才再次開啟模型運(yùn)行。

一旦制造系統(tǒng)中出現(xiàn)擾動(dòng)，可以等待擾動(dòng)恢復(fù)或執(zhí)行重調(diào)度，例如制造系統(tǒng)在遇到機(jī)床損壞的擾動(dòng)時(shí)可以自適應(yīng)地選擇兩種策略，保持原有分配方案不變而只更新工序的開始時(shí)間，也可以根據(jù)車間實(shí)際的運(yùn)行狀態(tài)更新調(diào)度方案。

5 實(shí)驗(yàn)

5.1 簡(jiǎn)單問(wèn)題標(biāo)準(zhǔn)算例實(shí)驗(yàn)

為了檢驗(yàn)多Agent方法求解車間生產(chǎn)管控問(wèn)題的性能，在Windows 7環(huán)境下，計(jì)算機(jī)CPU主頻為2 GHz，內(nèi)存為2.0 GB，利用MATLAB編程，對(duì)典型算例進(jìn)行測(cè)試。本研究選擇Ouz等[15]提供的標(biāo)準(zhǔn)算例問(wèn)題，重點(diǎn)關(guān)注中小型實(shí)例。所獲得的最大完工時(shí)間與已知下限的百分比偏差PD(Percentage deviation)用作性能度量：

PD=(Cmax-LB)/LB×100%。

(2)

式中：Cmax為最大完工時(shí)間;LB為理論最優(yōu)解或目前為止所報(bào)道的最優(yōu)解。如表2所示為對(duì)比實(shí)驗(yàn)計(jì)算結(jié)果。

表2 中小型實(shí)例的百分比偏差比較

續(xù)表2

續(xù)表2

如圖6所示為ECP+MWR獲得的算例P20S5T07最佳解決方案的甘特圖，相同的工件用相同的顏色表示，縱坐標(biāo)為加工設(shè)備編號(hào)，橫坐標(biāo)為時(shí)間軸，求解得到最優(yōu)解為1 125。

5.2 復(fù)雜問(wèn)題標(biāo)準(zhǔn)算例實(shí)驗(yàn)

基于ECP+MWR組合規(guī)則，選擇由Brandimarte[16]提出的BR數(shù)據(jù)集作為算法有效性驗(yàn)證算例。將Cmax與每個(gè)問(wèn)題實(shí)例的最優(yōu)解下界LB從PD的角度進(jìn)行對(duì)比分析。將本章測(cè)試結(jié)果與相關(guān)文獻(xiàn)中的結(jié)果進(jìn)行對(duì)比，包括Mastrolilli等[17]提出的禁忌搜索(Tabu Search, TS)算法、Gao等[18]提出的遺傳算法(hybrid Genetic Algorithm, hGA)和田松齡等[19]提出的蟻群算法(Petri nets-based-Asynchronous Parallel Ant Colony Optimization, PN-APACO)。對(duì)比結(jié)果如表3所列。

表3 求解BR數(shù)據(jù)算例對(duì)比結(jié)果比較

續(xù)表3

5.3 工程實(shí)例

為驗(yàn)證本文所提方法在策略車間調(diào)度工程問(wèn)題中的應(yīng)用，在數(shù)字孿生環(huán)境下設(shè)計(jì)了柔性作業(yè)車間調(diào)度虛擬仿真平臺(tái)，包含8個(gè)工件和10臺(tái)生產(chǎn)設(shè)備，工程實(shí)驗(yàn)的生產(chǎn)數(shù)據(jù)如表4所示。進(jìn)一步，為了驗(yàn)證異常事件監(jiān)測(cè)方法、分層組合規(guī)則和基于多代理系統(tǒng)的實(shí)時(shí)調(diào)度的工程應(yīng)用效果，在仿真環(huán)境下設(shè)計(jì)了2個(gè)工件和2個(gè)工位異常事件監(jiān)測(cè)場(chǎng)景，異常事件參數(shù)設(shè)置如表5所示。實(shí)驗(yàn)所需車間仿真運(yùn)行環(huán)境以及各工位和工件編號(hào)如圖7所示。

表4 生產(chǎn)數(shù)據(jù)

表5 異常事件參數(shù)設(shè)置

異常事件監(jiān)測(cè)實(shí)驗(yàn)結(jié)果如圖8所示，基于多代理系統(tǒng)的實(shí)時(shí)調(diào)度實(shí)驗(yàn)結(jié)果如圖9所示，圖中要素的含義與圖6相同。

5.4 結(jié)果討論

在車間生產(chǎn)過(guò)程監(jiān)測(cè)實(shí)驗(yàn)中，P001工件在L02工位的加工時(shí)間超過(guò)給定閾值，發(fā)生偏離生產(chǎn)計(jì)劃異常事件；P002工件在L02工位加工完成后沒(méi)有在L01工位出現(xiàn)，發(fā)生工序不匹配異常事件。實(shí)驗(yàn)結(jié)果表明，自動(dòng)機(jī)模型可以有效監(jiān)測(cè)車間生產(chǎn)過(guò)程中的異常事件。

車間生產(chǎn)管控標(biāo)準(zhǔn)算例的實(shí)驗(yàn)結(jié)果表明，多Agent可以用于車間生產(chǎn)管控問(wèn)題的求解。根據(jù)調(diào)度優(yōu)化目標(biāo)組合分析選擇的優(yōu)先級(jí)規(guī)則，在ECP和MWR的組合規(guī)則下，所有問(wèn)題的平均PD為4.591%，小于其他對(duì)比組合規(guī)則，更接近于理論最優(yōu)解。因此，基于多Agent車間監(jiān)測(cè)與管控方法中，ECP和MWR的組合規(guī)則的求解性能優(yōu)于其他組合。

在復(fù)雜問(wèn)題標(biāo)準(zhǔn)算例實(shí)驗(yàn)中，基于ECP+MWR組合規(guī)則得到的結(jié)果平均PD為35.56%，接近于各種對(duì)比元啟發(fā)算法，考慮到本文提出的方法不需要迭代優(yōu)化，因此滿足實(shí)時(shí)調(diào)度的需求。

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

本文研究了面向開放式結(jié)構(gòu)產(chǎn)品的IoMT驅(qū)動(dòng)的生產(chǎn)車間制造過(guò)程的監(jiān)測(cè)和管控方法，包括異常事件監(jiān)測(cè)方法和基于多Agent的車間擾動(dòng)事件快速響應(yīng)方法。從車間生產(chǎn)過(guò)程監(jiān)測(cè)實(shí)驗(yàn)和車間生產(chǎn)管控的實(shí)驗(yàn)結(jié)果可以得出：①基于自動(dòng)機(jī)模型可以有效監(jiān)測(cè)車間生產(chǎn)過(guò)程中的異常事件；②基于多Agent可以用于車間生產(chǎn)管控問(wèn)題的求解，且ECP和MWR組合規(guī)則得到方案的平均PD為4.591%，更接近于理論最優(yōu)解；③IoMT下制造車間的管控過(guò)程是在制造設(shè)備之間協(xié)商的基礎(chǔ)上完成的，是一種基于車間事件監(jiān)測(cè)的完全分布式協(xié)調(diào)與決策機(jī)制。

在很多實(shí)際應(yīng)用中，往往涉及多個(gè)性能指標(biāo)的優(yōu)化，如執(zhí)行時(shí)間、服務(wù)開銷等，下一步將考慮研究基于車間環(huán)境下多目標(biāo)實(shí)時(shí)調(diào)度優(yōu)化問(wèn)題。