王芊博,張文新,王柏琳,吳子軒

(1.北京科技大學(xué) 東凌經(jīng)濟(jì)管理學(xué)院,北京 100083; 2.鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術(shù)教育部工程研究中心,北京 100083) (*通信作者電子郵箱zhangwx@manage.ustb.edu.cn)

基于Agent的混合流水車間動(dòng)態(tài)調(diào)度系統(tǒng)

王芊博1,2,張文新1,2*,王柏琳1,2,吳子軒1,2

(1.北京科技大學(xué) 東凌經(jīng)濟(jì)管理學(xué)院,北京 100083; 2.鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術(shù)教育部工程研究中心,北京 100083) (*通信作者電子郵箱zhangwx@manage.ustb.edu.cn)

針對敏捷制造調(diào)度環(huán)境的不確定性、動(dòng)態(tài)性以及混合流水車間(HFS)調(diào)度問題的特點(diǎn),設(shè)計(jì)了一種基于多Agent的混合流水車間動(dòng)態(tài)調(diào)度系統(tǒng),系統(tǒng)由管理Agent、策略Agent、工件Agent和機(jī)器Agent構(gòu)成。首先提出一種針對混合流水車間環(huán)境的插值排序(HIS)算法并集成于策略Agent中,該算法適用于靜態(tài)調(diào)度和多種動(dòng)態(tài)事件下的動(dòng)態(tài)調(diào)度。然后，設(shè)計(jì)了各類Agent間的協(xié)調(diào)機(jī)制,在生產(chǎn)過程中所有Agent根據(jù)各自的行為邏輯獨(dú)立工作并互相協(xié)調(diào)。在發(fā)生動(dòng)態(tài)事件時(shí),策略Agent調(diào)用HIS算法根據(jù)當(dāng)前車間狀態(tài)產(chǎn)生工件序列,隨后各Agent根據(jù)生成的序列繼續(xù)進(jìn)行協(xié)調(diào)直到完成生產(chǎn)。最后進(jìn)行了發(fā)生機(jī)器故障、訂單插入情況下的重調(diào)度以及在線調(diào)度等動(dòng)態(tài)調(diào)度的實(shí)例仿真,結(jié)果表明對于這些問題,HIS算法的求解效果均優(yōu)于調(diào)度規(guī)則,特別是在故障重調(diào)度中,HIS算法重調(diào)度前后的Makespan一致度達(dá)97.6%,說明系統(tǒng)能夠靈活和有效地處理混合流水車間動(dòng)態(tài)調(diào)度問題。

混合流水車間;多Agent;在線調(diào)度;機(jī)器故障;訂單插入

0 引言

混合流水車間(Hybrid Flow Shop, HFS)廣泛存在于冶金、石化、制藥等流程工業(yè)生產(chǎn)系統(tǒng)中,其生產(chǎn)調(diào)度方法具有重要的研究意義[1]。1988年,Gupta證明了HFS調(diào)度屬于NP難問題[2]。HFS調(diào)度問題根據(jù)調(diào)度環(huán)境可分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度,靜態(tài)環(huán)境下的調(diào)度可預(yù)先計(jì)劃,任務(wù)、加工時(shí)間、機(jī)器或其他資源在調(diào)度周期內(nèi)都是確定的、可知的。而動(dòng)態(tài)環(huán)境下的調(diào)度是反應(yīng)性調(diào)度,任務(wù)到達(dá)時(shí)間可能是隨機(jī)的,系統(tǒng)中存在隨機(jī)的、不可預(yù)知事件。在以往的研究中,研究的重心主要集中在靜態(tài)調(diào)度問題上,Li等[3]將鄰域搜索算法與啟發(fā)式算法結(jié)合,提出利用全優(yōu)化信息并避免搜索過程陷入局部最優(yōu)的鄰域變換方法。文獻(xiàn)[4-5]研究了具有特殊約束的HFS調(diào)度問題。在動(dòng)態(tài)調(diào)度方面,Lee[6]應(yīng)用多種調(diào)度規(guī)則對考慮工件動(dòng)態(tài)到來的HFS問題進(jìn)行了仿真研究。針對機(jī)器故障下的HFS重調(diào)度問題,李鐵克等[7]從約束變化的角度建立了動(dòng)態(tài)約束滿足模型,提出了基于局部修復(fù)的重調(diào)度算法。Kundakci等[8]將遺傳算法與啟發(fā)式算法,調(diào)度規(guī)則結(jié)合,提出混合遺傳算法用以解決作業(yè)車間動(dòng)態(tài)調(diào)度問題。針對工件動(dòng)態(tài)到來的混合流水車間環(huán)境,Rahmani等[9]考慮了重調(diào)度方案與原始調(diào)度差異帶來的成本,結(jié)合前后方案一致度和加權(quán)拖期時(shí)間建立問題模型。

現(xiàn)有的解決HFS問題的方法大多都基于集中的模型,全部的計(jì)算都在集中的模型中完成,而將機(jī)器和工件只是看作被動(dòng)接收計(jì)算結(jié)果的客體,而非參與調(diào)度過程的實(shí)體。然而實(shí)際的生產(chǎn)系統(tǒng)又是離散的、分布式的、動(dòng)態(tài)的和隨機(jī)的,因此現(xiàn)有的方法缺乏靈活性并且在發(fā)生意外事件時(shí)難以及時(shí)響應(yīng)作出調(diào)整。

分布式系統(tǒng)能夠通過高效的信息傳遞及合作來解決復(fù)雜、動(dòng)態(tài)的調(diào)度問題。因此,分布式調(diào)度系統(tǒng),尤其是多Agent系統(tǒng)(Multi-Agent System, MAS)已受到越來越多學(xué)者的關(guān)注,Kouider等[10]針對作業(yè)車間調(diào)度問題開發(fā)了多Agent系統(tǒng),系統(tǒng)將問題分解為多個(gè)子問題,并由具有各自目標(biāo)和知識庫的獨(dú)立Agent來解決;Martin等[11]提出了一種通用的多Agent分布式框架,每個(gè)Agent集成特定的元啟發(fā)式算法,用以解決置換流水車間調(diào)度問題和車輛路徑問題;李應(yīng)等[12]提出結(jié)合動(dòng)態(tài)邏輯制造單元結(jié)構(gòu)的分布式多Agent控制結(jié)構(gòu)，研究了結(jié)合模糊數(shù)學(xué)規(guī)劃與模糊合同網(wǎng)的作業(yè)車間調(diào)度方案;Zhang[13]將多Agent技術(shù)與蟻群優(yōu)化算法相結(jié)合,研究了在動(dòng)態(tài)環(huán)境中的柔性作業(yè)車間調(diào)度問題。

盡管HFS調(diào)度是一類重要的車間調(diào)度問題，并且在實(shí)際生產(chǎn)中各類動(dòng)態(tài)事件時(shí)有發(fā)生,但在作者掌握的范圍內(nèi),尚未找到利用多Agent技術(shù)解決HFS動(dòng)態(tài)調(diào)度問題的公開發(fā)表文獻(xiàn), 因此本文設(shè)計(jì)了基于多Agent的HFS動(dòng)態(tài)調(diào)度系統(tǒng),系統(tǒng)能夠處理在線調(diào)度、機(jī)器故障重調(diào)度以及訂單插入重調(diào)度。

1 混合流水車間動(dòng)態(tài)調(diào)度問題

為了便于描述,記i為工件序號,i∈I={1,2,…,n};j為階段序號,j∈J={1,2,…,s};m為機(jī)器編號,m={1,2,…,mj};pij為第i個(gè)工件在第j階段的加工時(shí)間;sij為工件i在第j階段加工的開始時(shí)間;ci j為工件i在第j階段的完工時(shí)間,ci0=0;在HFS問題中,n個(gè)工件在流水線上進(jìn)行s個(gè)階段的加工,每個(gè)階段有mj≥1個(gè)同速機(jī),且至少其中一個(gè)階段的并行機(jī)數(shù)量mjgt;1。在某一階段各機(jī)器對同一工件的加工時(shí)間可能不同,工件要經(jīng)過所有階段的加工,但對于某一階段,工件可在該階段的任意一臺機(jī)器上加工,已知工件各道工序在各機(jī)器上的處理時(shí)間pij,問題的目標(biāo)是把工件i指派到階段j的機(jī)器m上,并對各機(jī)器上的指派工件進(jìn)行排序,即確定工件的指派方案和排序方案。并確定工件i在階段j的開工時(shí)間sij和完工時(shí)間ci j,以最小化最大時(shí)間表長Cmax。在本文的動(dòng)態(tài)調(diào)度研究中,考慮了三類常見的動(dòng)態(tài)調(diào)度問題:在線調(diào)度、機(jī)器故障和訂單插入。

1.1 在線調(diào)度

在經(jīng)典調(diào)度問題中,均是在已知所有作業(yè)信息的情況下進(jìn)行調(diào)度,即整個(gè)作業(yè)到達(dá)序列及每個(gè)作業(yè)的工時(shí)在調(diào)度時(shí)是已知的,這被稱為離線調(diào)度(off-line scheduling)。在線調(diào)度則是假設(shè)作業(yè)在未到來時(shí)其所有信息是未知的,調(diào)度算法必須對每個(gè)到來的工件進(jìn)行即時(shí)調(diào)度[14]。對于在線調(diào)度,主要考慮:

1)初始時(shí)刻沒有待加工工件,工件隨時(shí)間推移持續(xù)到來,新訂單在到來之前工件信息是未知的。

2)訂單到來的時(shí)間可能為生產(chǎn)開始時(shí)刻到結(jié)束前的任何時(shí)間,新加入訂單可能包含單個(gè)工件或者多個(gè)工件。

3)以最小化Makespan作為調(diào)度目標(biāo)。

1.2 機(jī)器故障

1)機(jī)器空閑時(shí)不發(fā)生故障;故障在執(zhí)行加工的過程中隨機(jī)發(fā)生,持續(xù)時(shí)間為隨機(jī)。

2)被中斷加工的工件必須重新加工。

3)機(jī)器故障不僅會導(dǎo)致工件在機(jī)器故障發(fā)生之前對機(jī)器的占用時(shí)間失去意義,并且機(jī)器需要占用時(shí)間來進(jìn)行修復(fù),因此發(fā)生機(jī)器故障會導(dǎo)致Makespan增大,重調(diào)度的目標(biāo)是最小化Makespan。

1.3 訂單插入

訂單插入是指在初始調(diào)度執(zhí)行的過程中有新的生產(chǎn)訂單到來,主要考慮:

1)在初始時(shí)刻存在已知工件信息的若干待加工工件并且初始調(diào)度由MAS產(chǎn)生。訂單在到來之前其包含的工件信息是未知的。

2)訂單加入的時(shí)間可能為生產(chǎn)開始時(shí)刻到結(jié)束前的任何時(shí)間,新加入訂單可能包含單個(gè)工件或者多個(gè)工件。

3)新訂單加入后的重調(diào)度目標(biāo)是最小化Makespan。

2 基于MAS的調(diào)度系統(tǒng)

2.1 Agent模型

多Agent調(diào)度系統(tǒng)由管理Agent、策略Agent、工件Agent、機(jī)器Agent組成。系統(tǒng)結(jié)構(gòu)如圖1表示。

圖1 基于多Agent的HFS調(diào)度系統(tǒng)結(jié)構(gòu)

2.1.1 管理Agent

管理Agent(Manage Agent,MA)由工件數(shù)據(jù)庫、車間結(jié)構(gòu)模塊、黑板系統(tǒng)和調(diào)度管理模塊構(gòu)成,管理Agent結(jié)構(gòu)如圖2所示。

圖2 管理Agent結(jié)構(gòu)

1)工件數(shù)據(jù)庫。在調(diào)度開始之前MAS的訂單處理模塊將已存在的訂單所包含的所有工件信息記錄在管理Agent的工件數(shù)據(jù)庫中以便其他Agent在需要時(shí)查詢工件相關(guān)信息。如果在生產(chǎn)的過程中有訂單加入,訂單處理模塊立即將新加入工件的信息記錄在工件數(shù)據(jù)庫。

2)車間結(jié)構(gòu)模塊。該模塊從工件數(shù)據(jù)庫中讀取所有工件的信息并從實(shí)際車間讀取車間機(jī)器信息,然后根據(jù)這些信息動(dòng)態(tài)地生成與實(shí)際車間情況對應(yīng)的工件Agent群和機(jī)器Agent群。

3)黑板系統(tǒng)。即Agent之間交互通信所需的共享通信平臺,黑板系統(tǒng)存儲各個(gè)Agent公共可見的動(dòng)態(tài)數(shù)據(jù),如生產(chǎn)過程中機(jī)器的狀態(tài)和釋放時(shí)間、工件在各階段的加工狀態(tài)和釋放時(shí)間等,以便Agent在協(xié)調(diào)的過程中能夠更加快速地查找所需的信息來求解自己的子問題。

4)調(diào)度管理模塊。其功能是在調(diào)度開始時(shí)激活所有Agent開始工作,并且將所有機(jī)器的加工狀態(tài)、當(dāng)前加工工件及工件各階段的開工和完工時(shí)間通過動(dòng)態(tài)甘特圖顯示出來。

2.1.2 策略Agent

策略Agent(Strategy Agent,SA)是產(chǎn)生高效調(diào)度結(jié)果的核心一環(huán)。在生產(chǎn)開始或者發(fā)生動(dòng)態(tài)事件時(shí),策略Agent會調(diào)用所選擇的算法產(chǎn)生初始序列(在本文中,將SA產(chǎn)生的工件序列稱為Strategy序列),隨即工件Agent和機(jī)器Agent根據(jù)所產(chǎn)生的Strategy序列按照集成的行為邏輯進(jìn)行協(xié)調(diào)并開始生產(chǎn),因此策略Agent產(chǎn)生排序方案的好壞直接影響了最終調(diào)度結(jié)果的質(zhì)量。調(diào)度規(guī)則和啟發(fā)式算法因?yàn)橛?jì)算速度快、反應(yīng)靈活,被廣泛用于解決調(diào)度問題,因此本文將采用構(gòu)造啟發(fā)式算法指導(dǎo)SA的工件排序,提出了一種針對混合流水車間環(huán)境的插值排序(HFS-aimed Interpolation Sorting, HIS)算法。除了HIS算法以外,SA也集成了NEH算法和多種調(diào)度規(guī)則作為產(chǎn)生Strategy序列的可選算法。

圖4 MAS系統(tǒng)Agent間協(xié)調(diào)機(jī)制

2.1.3 工件Agent

工件Agent(Job Agent, JA)是由管理Agent根據(jù)已到來的工件動(dòng)態(tài)生成的,每個(gè)工件對應(yīng)一個(gè)JA,JA由數(shù)據(jù)模塊、狀態(tài)顯示模塊和行為模塊組成,如圖3所示。

1)數(shù)據(jù)模塊記錄兩部分?jǐn)?shù)據(jù)：一部分是靜態(tài)數(shù)據(jù),另一部分是生產(chǎn)中產(chǎn)生的動(dòng)態(tài)數(shù)據(jù)。靜態(tài)數(shù)據(jù)包括:工件的序號、各階段的加工時(shí)間等信息。動(dòng)態(tài)數(shù)據(jù)包括:工件的優(yōu)先值、各階段開工完工時(shí)間、各階段分配機(jī)器、各階段加工狀態(tài)等。這些數(shù)據(jù)同樣作為管理Agent中的黑板系統(tǒng)中的公用數(shù)據(jù),以便其他Agent能夠快速查詢到所需的信息。

2)狀態(tài)顯示模塊用狀態(tài)圖的形式顯示出工件當(dāng)前所處狀態(tài)。

3)行為模塊集成了JA與其他Agent的協(xié)調(diào)邏輯。

圖3 機(jī)器Agent及工件Agent結(jié)構(gòu)

2.1.4 機(jī)器Agent

機(jī)器Agent,也稱為資源Agent(Resource Agent, RA)是由管理Agent根據(jù)讀取的實(shí)際車間信息而生成。每臺機(jī)器對應(yīng)一個(gè)RA。與JA相似,RA由數(shù)據(jù)模塊、狀態(tài)顯示模塊和行為模塊構(gòu)成,如圖3所示,但其中內(nèi)容有所不同。

1)數(shù)據(jù)模塊中的靜態(tài)數(shù)據(jù)包括:機(jī)器序號、機(jī)器類型;動(dòng)態(tài)數(shù)據(jù)包括:機(jī)器釋放時(shí)間、已安排在機(jī)器上加工的工件和機(jī)器當(dāng)前狀態(tài)。這些數(shù)據(jù)同樣作為黑板系統(tǒng)里的公用數(shù)據(jù)。

2)狀態(tài)顯示模塊用狀態(tài)圖的形式來顯示機(jī)器當(dāng)前的狀態(tài)。

3)行為模塊集成RA與其他Agent的協(xié)調(diào)邏輯。

2.2 Agent間協(xié)調(diào)機(jī)制

HFS動(dòng)態(tài)調(diào)度系統(tǒng)的四類Agent間協(xié)調(diào)機(jī)制如圖4所示,具體描述如下:

1)初始調(diào)度的生成與交互:調(diào)度開始時(shí),SA調(diào)用指定的算法或者調(diào)度規(guī)則產(chǎn)生初始序列,在本文中將SA產(chǎn)生的工件序列稱為Strategy序列。SA在產(chǎn)生Strategy序列之后將通知MA,MA根據(jù)工件在Strategy序列中的位置,對各JA賦予相應(yīng)的優(yōu)先值(在Strategy序列中靠前的工件優(yōu)先值更大),并通知RA和JA生產(chǎn)開始。

2)在生產(chǎn)開始后每個(gè)RA和JA分別獨(dú)立進(jìn)行工作,二者的協(xié)調(diào)機(jī)制如下:

生產(chǎn)開始時(shí),所有待加工工件都釋放到第一階段,所有機(jī)器初始釋放時(shí)間都為0。對于每個(gè)JA,當(dāng)工件釋放時(shí),就請求安排到釋放時(shí)間最早的空閑機(jī)器上。

當(dāng)RA接收到JA的安排請求時(shí),如果同時(shí)只接到一個(gè)JA發(fā)出的請求,則立即安排對應(yīng)工件進(jìn)行加工;否則如果接收到多個(gè)JA同時(shí)發(fā)出的安置請求,則選擇其中優(yōu)先值最大的工件安排加工,并向被選擇工件發(fā)送消息通知請求被接受,對另外的工件則通知其請求被拒絕。

當(dāng)JA接收到拒絕通知時(shí),則重新查詢空閑機(jī)器,如果有則向其RA發(fā)送安置請求。

每當(dāng)有機(jī)器釋放時(shí),RA去查詢當(dāng)前已經(jīng)釋放到機(jī)器對應(yīng)階段但還未開始加工的等待工件,如果有則安排其中優(yōu)先值最大的工件開始加工。

每當(dāng)工件完成一階段的加工時(shí)就立即釋放到下一階段,同時(shí)JA向下一階段的機(jī)器發(fā)送安置請求,直到所有階段完成,該工件完成加工。直到所有工件完成加工生產(chǎn)結(jié)束。

3 動(dòng)態(tài)調(diào)度策略與算法

如2.1.2節(jié)中對策略Agent調(diào)度思想的描述,本文提出的重調(diào)度方法在發(fā)生動(dòng)態(tài)事件時(shí),只根據(jù)當(dāng)前車間的狀態(tài)調(diào)用插值排序算法HIS重新產(chǎn)生Strategy序列。在重新生成Strategy序列之后,所有JA和MA能立即根據(jù)新的Strategy序列按照預(yù)先設(shè)定的協(xié)調(diào)機(jī)制繼續(xù)進(jìn)行工作。也就是說,在重調(diào)度時(shí)不需要改變JA和MA之間的協(xié)調(diào)機(jī)制,只需要SA調(diào)用 HIS算法重新產(chǎn)生Strategy序列。因此,即使在系統(tǒng)中存在多種動(dòng)態(tài)事件,或有動(dòng)態(tài)事件多次連續(xù)發(fā)生的情況下,MAS系統(tǒng)都可以迅速地進(jìn)行重調(diào)度并保證生產(chǎn)即刻繼續(xù)進(jìn)行,具有較好的適應(yīng)性和靈活性。本章將針對動(dòng)態(tài)環(huán)境特征,設(shè)計(jì)機(jī)器故障和訂單插入的調(diào)度策略,并給出HIS算法。

3.1 機(jī)器故障處理策略

當(dāng)故障發(fā)生時(shí),故障機(jī)器RA更新機(jī)器信息:將其狀態(tài)標(biāo)為故障,將中斷工件從已安排工件隊(duì)列中刪除,更新釋放時(shí)間為當(dāng)前時(shí)刻加上故障修復(fù)時(shí)間。隨即向該工件JA發(fā)送故障消息,當(dāng)中斷工件JA收到故障消息時(shí),更新工件信息,該工件重新釋放到故障階段。管理Agent查詢此時(shí)在第一階段中所有已釋放但未開始加工工件,如果超過一個(gè)則調(diào)用HIS算法重新產(chǎn)生Strategy序列，否則Strategy序列不變。在策略Agent調(diào)用算法產(chǎn)生新的Strategy序列之后通知MA,MA根據(jù)新隊(duì)列通知各JA更新優(yōu)先值,并通知所有JA和RA繼續(xù)工作。處理過程各Agent的協(xié)調(diào)機(jī)制如圖5所示。

圖5 機(jī)器故障重調(diào)度處理機(jī)制

3.2 新訂單加入的處理策略

當(dāng)生產(chǎn)的過程中有訂單插入或者當(dāng)在線調(diào)度訂單到來時(shí),到來工件立刻釋放到第一階段,管理Agent查詢此時(shí)在第一階段中已釋放未加工工件,如果有兩個(gè)或以上則通知策略Agent調(diào)用HIS算法重新產(chǎn)生Strategy序列。策略Agent產(chǎn)生新的Strategy序列之后通知MA,MA根據(jù)新隊(duì)列通知各JA更新優(yōu)先值,并通知所有JA和RA繼續(xù)進(jìn)行工作。處理過程各Agent的協(xié)調(diào)機(jī)制如圖6所示。

3.3 HIS算法

調(diào)度規(guī)則和啟發(fā)式算法因?yàn)橛?jì)算速度快、反應(yīng)靈活,被廣泛用于解決調(diào)度問題。目前,已有多位學(xué)者對混合流水車間下的多種構(gòu)造啟發(fā)式算法進(jìn)行了比較研究。文獻(xiàn)[15]研究了5種Flowshop的啟發(fā)式算法運(yùn)用于HFS問題以期最小化Makespan和Mean Flow Time,結(jié)果表明NEH算法在所有指標(biāo)上更優(yōu)；文獻(xiàn)[16]以最小化Makespan和拖期時(shí)間為目標(biāo)研究了5種啟發(fā)式算法和多種調(diào)度規(guī)則在HFS問題中的應(yīng)用,結(jié)果同樣表明NEH法的表現(xiàn)明顯優(yōu)于其他算法。為了能在敏捷生產(chǎn)要求下產(chǎn)生良好的調(diào)度效果,本文針對混合流水車間環(huán)境,基于NEH算法的設(shè)計(jì)思路,提出了HIS算法。

3.3.1 主算法——插值排序法

與NEH相似,HIS算法同樣對所有待安排加工工件進(jìn)行迭代插入并計(jì)算Cmax,最終將所有工件插入后形成Strategy序列。區(qū)別在于,NEH針對置換流水車間的環(huán)境計(jì)算Cmax,并且只用于靜態(tài)調(diào)度;HIS則針對混合流水車間環(huán)境,考慮了在多Agent系統(tǒng)的協(xié)調(diào)機(jī)制下的機(jī)器分配機(jī)制和機(jī)器上的工件排序機(jī)制。根據(jù)Strategy序列,按照多Agent系統(tǒng)協(xié)調(diào)機(jī)制下的機(jī)器分配策略和機(jī)器上的工件排序策略,產(chǎn)生工件的分配和在機(jī)器上的排序,在工件的分配和排序確定后,Strategy序列對應(yīng)的Cmax就被確定下來。并且在進(jìn)行動(dòng)態(tài)調(diào)度時(shí),HIS算法將考慮當(dāng)前車間的加工狀態(tài)——即在各工件和機(jī)器當(dāng)前加工狀態(tài)的基礎(chǔ)上,根據(jù)Strategy序列對當(dāng)前尚未開始加工的工件進(jìn)行機(jī)器分配和排序,進(jìn)而計(jì)算出Strategy序列對應(yīng)的Cmax。因此,HIS算法能有效地解決動(dòng)態(tài)環(huán)境下的混合流水車間調(diào)度問題,同時(shí)也很容易擴(kuò)展到靜態(tài)調(diào)度問題。

HIS算法表述如下:

圖6 訂單插入重調(diào)度處理機(jī)制

3.3.2 機(jī)器分配及排序子算法

HIS算法針對混合流水車間各階段的多機(jī)環(huán)境,在Strategy序列確定后,按照多Agent系統(tǒng)的機(jī)器分配機(jī)制和機(jī)器上的工件排序機(jī)制將工件分配到機(jī)器上,一旦工件的機(jī)器分配和排序確定,Strategy序列對應(yīng)的Makespan就確定下來。

機(jī)器分配機(jī)制和機(jī)器上的工件排序機(jī)制的調(diào)度思想如下。

對于工件:

IF(工件在釋放時(shí)如果有空閑機(jī)器)

THEN請求安排到釋放時(shí)間最小的空閑機(jī)器上;

ELSE加入等待隊(duì)列;

IF(工件被拒絕安排到機(jī)器上)

THEN

{ IF(此時(shí)還有空閑機(jī)器)

THEN請求安排到釋放時(shí)間最小的空閑機(jī)器上;

ELSE加入等待隊(duì)列;

}

對于機(jī)器:

IF(有工件請求安排到機(jī)器上)

THEN

{ IF(接收到的是單個(gè)工件請求)

THEN將工件安排到機(jī)器上;

ELSE選擇優(yōu)先值最大的工件安排加工,拒絕其他工件的請求;

}

IF(機(jī)器釋放)

THEN

{ IF(等待隊(duì)列不為空)

THEN從等待隊(duì)列選擇優(yōu)先值最大的工件安排加工;

具體步驟為:

Step1 初始化。讀取所有工件在各階段的加工狀態(tài),對于j=1,2,…,s建立在階段j尚未安排加工的工件的集合Cj,定義ci, j-1為工件j階段的釋放時(shí)間,對于j=2,3,…,s,如果工件i在j-1階段已安排加工則讀取ci, j-1,對于j=1,對于所有在初始調(diào)度時(shí)已存在工件在階段j的釋放時(shí)間ci0=0。令階段數(shù)j=1。

Step2 若此時(shí)Cj≠?,則

1)找到此階段釋放時(shí)間最小的機(jī)器m,記錄其釋放時(shí)間tm。

2)查看所有工件在j階段的釋放時(shí)間即ci, j-1,若對于所有工件有ci, j-1gt;tm，即如果在機(jī)器釋放時(shí)所有工件尚未釋放,則轉(zhuǎn)到3);否則轉(zhuǎn)到4)。

3)選擇ci, j-1最小的工件i,如有多個(gè)工件ci, j-1相同,則根據(jù)在Strategy序列中的相對位置選擇優(yōu)先值最大的工件(Strategy序列中靠前的工件優(yōu)先值更大)設(shè)其為i,將i安排到機(jī)器m上,更新工件的此階段完工時(shí)間即令ci j=ci, j-1+pij,更新機(jī)器釋放時(shí)間tm=ci, j-1+pij,將工件i從Cj中刪除。

4)若只有一個(gè)工件滿足ci, j-1≤tm,即在機(jī)器釋放時(shí)只有一個(gè)工件i已釋放,則將此工件安排到機(jī)器上,更新工件此階段的完工時(shí)間ci j,更新機(jī)器的釋放時(shí)間tm,將工件i從Cj中刪除;否則若有多個(gè)工件滿足ci, j-1≤tm,即在機(jī)器釋放時(shí)有多個(gè)工件已釋放,則根據(jù)Strategy序列選擇優(yōu)先值最大的工件i安排到機(jī)器上,更新工件此階段的完工時(shí)間ci j,更新機(jī)器釋放時(shí)間tm,將工件從未安排集合Cj中刪除。

5)若Cj≠?則轉(zhuǎn)到1);否則轉(zhuǎn)到Step3。

Step3 若此時(shí)j=s,則轉(zhuǎn)到Step4;否則j=j+1并轉(zhuǎn)到Step2。

Step4 檢查所有工件在最后一階段完工時(shí)間cis,最大值即為此Strategy序列對應(yīng)的Cmax。

4 仿真實(shí)驗(yàn)

采用Anylogic7.3.6作為多智體(multi-Agent)建模工具。實(shí)驗(yàn)環(huán)境為CPU Intel Core I5 CPU @ 2.20 GHz/RAM 8 GB。

4.1 在線調(diào)度

在線調(diào)度的仿真中,仿真了不同的工件到來頻率下和不同工件總數(shù)的在線調(diào)度,工件在各階段的加工時(shí)間pij∈[5,30],共5個(gè)階段,每個(gè)階段有3臺同速并行機(jī),0時(shí)刻到達(dá)10個(gè)工件,第一組測試隨后每隔20個(gè)時(shí)間單位到達(dá)10個(gè)工件;第二組隨后每隔30個(gè)時(shí)間單位達(dá)到10個(gè)工件。兩組測試分別仿真了總共到來100個(gè)工件和共到來200個(gè)工件的情況。策略Agent分別選擇HIS算法以及常用的調(diào)度規(guī)則產(chǎn)生Strategy序列,隨后工件Agent和機(jī)器Agent根據(jù)Stretegy序列進(jìn)行協(xié)調(diào)并完成生產(chǎn),對比各自對應(yīng)的最大完工時(shí)間Cmax,參與對比的調(diào)度規(guī)則包括:最短加工時(shí)間優(yōu)先(Shortest Processing Time first, SPT)、最長加工時(shí)間優(yōu)先(Longest Processing Time first, LPT)、最大剩余加工時(shí)長優(yōu)先(Most Work Remaining First, MWRF)、最小剩余加工時(shí)長優(yōu)先(Least Work Remaining First, LWRF)、最大總加工時(shí)長優(yōu)先(Most Total Work First,MTWF)、最小總加工時(shí)長優(yōu)先(Least Total Work First, LTWF)。實(shí)驗(yàn)結(jié)果如表1所示。

表1 在線調(diào)度實(shí)驗(yàn)結(jié)果(每次到達(dá)10個(gè)工件)

仿真結(jié)果表明,在兩種不同的訂單到來頻率下,在不同數(shù)量工件的情況下,本文提出的多Agent調(diào)度系統(tǒng),能夠迅速地在訂單到來之時(shí)及時(shí)對未安排加工的工件進(jìn)行重調(diào)度,實(shí)驗(yàn)結(jié)果表明在HIS算法產(chǎn)生排序方案的基礎(chǔ)上最終的Cmax明顯優(yōu)于其他調(diào)度規(guī)則產(chǎn)生的排序方案的基礎(chǔ)上完成加工的Cmax。

4.2 故障重調(diào)度

在故障重調(diào)度的仿真中,工件數(shù)量為20個(gè),共計(jì)3個(gè)階段,每個(gè)階段有3臺同速機(jī),工件在各階段的加工時(shí)間服從均勻分布,pij∈[5,30],在調(diào)度開始時(shí),策略Agent調(diào)用HIS算法產(chǎn)生靜態(tài)調(diào)度下的Strategy序列,隨后所有工件Agent和機(jī)器Agent根據(jù)Strategy序列進(jìn)行協(xié)調(diào)并開始生產(chǎn)。故障隨機(jī)產(chǎn)生,故障參數(shù)如表2所示。

表2 故障參數(shù)表

注：T表示初始調(diào)度中故障機(jī)器上最后一個(gè)操作的完工時(shí)間。

同時(shí)將調(diào)度規(guī)則與HIS算法進(jìn)行重調(diào)度結(jié)果對比。運(yùn)用調(diào)度規(guī)則進(jìn)行重調(diào)度時(shí),在發(fā)生故障后根據(jù)選擇調(diào)度規(guī)則賦予工件在各階段的優(yōu)先值,各Agent根據(jù)優(yōu)先值進(jìn)行協(xié)調(diào)并完成加工。

表3 故障重調(diào)度實(shí)驗(yàn)算例

表4 故障重調(diào)度實(shí)驗(yàn)結(jié)果

根據(jù)故障參數(shù)產(chǎn)生實(shí)驗(yàn)算例,共進(jìn)行20次故障重調(diào)度仿真。故障發(fā)生階段、發(fā)生時(shí)間、持續(xù)時(shí)間、中斷前工件已加工時(shí)間如表3所示,初始調(diào)度Cmax、調(diào)用HIS算法及調(diào)度規(guī)則重調(diào)度后的Cmax如表4所示。在多代理調(diào)度系統(tǒng)的生產(chǎn)過程中發(fā)生故障的即時(shí)重調(diào)度機(jī)制下,能夠在故障發(fā)生時(shí)迅速重新計(jì)算Strategy隊(duì)列,各Agent根據(jù)新的Strategy隊(duì)列能夠立刻重新開始協(xié)調(diào)工作并且使生產(chǎn)得以繼續(xù)進(jìn)行。在20次實(shí)驗(yàn)中仿真結(jié)果表明在多Agent調(diào)度系統(tǒng)下,調(diào)用HIS算法產(chǎn)生新的Strategy序列并根據(jù)新序列完成重調(diào)度,初始調(diào)度和重調(diào)度Cmax的時(shí)間相似度為97.6%,實(shí)驗(yàn)結(jié)果表明HIS算法的調(diào)度效果優(yōu)于調(diào)度規(guī)則,能夠很大程度消除故障對于最大完工時(shí)間的影響。圖7為算例3故障前后的甘特圖,其中:圖7(a)是調(diào)用HIS算法形成的初始調(diào)度甘特圖,初始調(diào)度Makespan為155;圖7(b)是在初始調(diào)度基礎(chǔ)上,在階段2發(fā)生故障時(shí)調(diào)用HIS算法進(jìn)行重調(diào)度后的甘特圖,其中故障發(fā)生時(shí)間為26,持續(xù)時(shí)間為12,機(jī)器發(fā)生故障前已加工時(shí)間為19,重調(diào)度后Makespan為156。

圖7 故障重調(diào)度前后甘特圖

表5 訂單插入重調(diào)度實(shí)驗(yàn)結(jié)果

4.3 訂單插入動(dòng)態(tài)調(diào)度

在訂單插入動(dòng)態(tài)調(diào)度仿真中,工件數(shù)量為20,階段數(shù)為3,工件加工時(shí)間服從均勻分布pij∈[5,30],插入訂單到來時(shí)間T=U[0.1,0.9]*Cmax,插入訂單包含工件數(shù)量為隨機(jī)1～5。為了對比HIS算法的重調(diào)度效果,將HIS算法與調(diào)度規(guī)則進(jìn)行對比實(shí)驗(yàn)。訂單插入發(fā)生后,在調(diào)用HIS算法重調(diào)度時(shí),會產(chǎn)生新的Strategy序列,隨后各Agent根據(jù)產(chǎn)生的序列繼續(xù)協(xié)調(diào)并完成生產(chǎn)。在調(diào)用調(diào)度規(guī)則進(jìn)行重調(diào)度時(shí),根據(jù)所選擇的調(diào)度規(guī)則賦予工件在各階段的優(yōu)先值,隨后各Agent根據(jù)工件優(yōu)先值進(jìn)行協(xié)調(diào)并完成生產(chǎn)。實(shí)驗(yàn)結(jié)果如表5所示,算例7插單前以及插單后用兩種方法進(jìn)行重調(diào)度甘特圖對比如圖8所示。

圖8 訂單插入重調(diào)度前后甘特圖

圖8中：圖8(a)為初始調(diào)度甘特圖；圖8(b)為初始調(diào)度基礎(chǔ)上在t=22時(shí)刻插入工件j20、j21、j22,調(diào)用HIS算法重調(diào)度形成的甘特圖,Makespan為167；圖8(c)為在訂單插入后將新到工件插入到Strategy序列末尾,即運(yùn)用先進(jìn)先出(First In First Out,FIFO)規(guī)則完成加工后的甘特圖,Makespan為178。

5 結(jié)語

大多數(shù)現(xiàn)有的解決HFS問題的算法都集中于模型,所有的計(jì)算都集中在模型完成,將機(jī)器和工件當(dāng)作接受調(diào)度結(jié)果的客體,缺乏靈活性。本文設(shè)計(jì)了基于Agent的混合流水車間調(diào)度系統(tǒng),設(shè)計(jì)了各Agent之間的協(xié)調(diào)機(jī)制,從而將工件和機(jī)器視為參與調(diào)度過程的實(shí)體?；贜EH算法的設(shè)計(jì)思路,針對混合流水車間問題以及動(dòng)態(tài)調(diào)度問題的特點(diǎn),提出了系統(tǒng)的核心算法(HIS),該算法適用于靜態(tài)調(diào)度和多種動(dòng)態(tài)調(diào)度問題。在發(fā)生動(dòng)態(tài)事件時(shí),系統(tǒng)能迅速根據(jù)當(dāng)前車間中機(jī)器和工件的加工狀態(tài)由策略Agent調(diào)用HIS算法產(chǎn)生新的排序方案,根據(jù)新的排序方案,工件Agent和機(jī)器Agent能即刻繼續(xù)協(xié)調(diào)工作以完成工件在機(jī)器上的分配和排序。最終仿真結(jié)果表明,此MAS產(chǎn)生的調(diào)度效果比多種調(diào)度規(guī)則更優(yōu),能夠適應(yīng)多種動(dòng)態(tài)事件同時(shí)并存的動(dòng)態(tài)生產(chǎn)環(huán)境。

References)

[1] LINN R, ZHANG W. Hybrid flow shop scheduling: a survey[J]. Computers amp; Industrial Engineering, 1999, 37(1/2): 57-61.

[2] GUPTA J N D. Two-stage, hybrid flowshop scheduling problem[J]. Journal of the Operational Research Society, 1988, 39(4): 359-364.

[3] LI J Q, PAN Q K, WANG F T. A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem[J]. Applied Soft Computing, 2014, 24(24): 63-77.

[4] LI J Q, PAN Q K. Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm[J]. Information Sciences, 2015, 316 (C): 487-502.

[5] NADERI B, ZANDIEH M, KHALEGHI G B A, et al. An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness[J]. Expert Systems with Applications, 2009, 36(6): 9625-9633.

[6] LEE G C. Estimating order lead times in hybrid flowshops with different scheduling rules[J]. Computers amp; Industrial Engineering, 2009, 56(4): 1668-1674.

[7] 李鐵克, 肖擁軍, 王柏琳. 基于局部性修復(fù)的HFS機(jī)器故障重調(diào)度[J]. 管理工程學(xué)報(bào), 2010, 24(3): 45-49. (LI T K, XIAO Y J, WANG B L. HFS rescheduling under machine failures based on local repair [J]. Journal of Industrial Engineering and Engineering Management, 2010, 24(3): 45-49.)

[8] KUNDAKCI N, KULAK O. Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem [J]. Computers amp; Industrial Engineering, 2016, 96 (C): 31-51.

[9] RAHMANI D, RAMEZANIAN R. A stable reactive approach in dynamic flexible flow shop scheduling with unexpected disruptions: a case study[J]. Computers amp; Industrial Engineering, 2016, 98(10): 360-372.

[10] KOUIDER A, BOUZOUIA B. Multi-Agent job shop scheduling system based on co-operative approach of idle time minimisation[J]. International Journal of Production Research, 2012, 50(2): 409-424.

[11] MARTIN S, OUELHADJ D, BEULLENS P, et al. A multi-Agent based cooperative approach to scheduling and routing[J]. European Journal of Operational Research, 2016, 254(1): 169-178.

[12] 李應(yīng), 楊善林, 鄭家強(qiáng). 敏捷制造系統(tǒng)的基于Agent的混合調(diào)度[J]. 系統(tǒng)仿真學(xué)報(bào), 2009, 21(12): 3763-3767. (LI Y, YANG S L, ZHENG J Q. Multi-Agent based hybrid scheduling strategy agile manufacturing system[J]. Journal of System Simulation, 2009, 21(12): 3763-3767.)

[13] ZHANG S, WONG T N. Flexible job-shop scheduling/rescheduling in dynamic environment: a hybrid MAS/ACO approach[J]. International Journal of Production Research, 2016, 55(11): 3173-3196.

[14] 龍?zhí)? 石宇強(qiáng), 王俊佳. 柔性作業(yè)車間在線調(diào)度問題的仿真建模與分析[J]. 機(jī)械設(shè)計(jì)與制造, 2015(12): 27-30. (LONG T, SHI Y Q, WANG J J. Simulation modeling and analysis for online flexible job-shop scheduling problem [J]. Machine Design amp; Manufacture, 2015(12): 27-30.)

[15] BRAH S A, LUAN L L. Heuristics for scheduling in a flow shop with multiple processors[J]. European Journal of Operational Research, 1999, 113(1): 113-122.

[16] GUINET A G P, SOLOMON M M. Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time[J]. International Journal of Production Research, 1996, 34(6): 1643-1654.

Agent-baseddynamicschedulingsystemforhybridflowshop

WANG Qianbo1,2, ZHANG Wenxin1,2*, WANG Bailin1,2, WU Zixuan1,2

(1.DonlinksSchoolofEconomicsandManagement,UniversityofScienceandTechnologyBeijing,Beijing100083,China;2.EngineeringResearchCenterofMESTechnologyforIronamp;SteelProductionofMinistryofEducation,Beijing100083,China)

Aiming at the uncertainty and dynamism in agile manufacturing and the features of Hybrid Flow Shop (HFS) scheduling problem, a multi-Agent based dynamic scheduling system for hybrid flow shop was developed, which consists of management Agent, strategy Agent, job Agent and machine Agent. First, a HFS aimed Interpolation Sorting (HIS) algorithm was proposed and integrated into the strategy Agent, which is suitable for static scheduling and dynamic scheduling under a variety of dynamic events. Then the coordination mechanism between the various Agents was designed. In the process of production, all Agents worked independently and coordinate with each other according to their behavioral logic. If a dynamic event occurred, the strategy Agent called HIS algorithm to generate the sequence of jobs according to the current workshop state, and then the Agents continued to coordinate according to the generated sequence until the production was finished. Finally, simulations of dynamic scheduling such as machine failure, rush order and online scheduling were carried out. The experimental results show that compared with a variety of scheduling rules, HIS algorithm has better schedule results than those by scheduling rules in these cases; especially in machine breakdown rescheduling, the consistency of makespan before and after rescheduling was up to 97.6%, which means that the HFS dynamic scheduling system is effective and flexible.

Hybrid Flow Shop (HFS); multi-Agent; online scheduling; machine breakdown; rush order

2017- 05- 22;

2017- 07- 31。

國家自然科學(xué)基金資助項(xiàng)目(71231001);中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(FRF-BD-16-006A);北京市自然科學(xué)基金資助項(xiàng)目(9174038)。

王芊博(1989—),男,遼寧遼陽人,碩士研究生,主要研究方向:生產(chǎn)計(jì)劃與調(diào)度、人工智能算法; 張文新(1966—),男,河北保定人,副教授,博士,主要研究方向:先進(jìn)制造管理、電子商務(wù); 王柏琳(1983—),女,河北石家莊人,講師,博士,主要研究方向:先進(jìn)制造管理、智能優(yōu)化方法。

1001- 9081(2017)10- 2991- 08

10.11772/j.issn.1001- 9081.2017.10.2991

TP273.2

A

This work is partially supported by the National Natural Science Foundation of China (71231001), the Fundamental Research Funds for the Central Universities (FRF-BD-16-006A), the Beijing Natural Science Foundation (9174038).

WANGQianbo, born in 1989, M. S. candidate. His research interests include production planning and scheduling, artificial intelligence algorithm.

ZHANGWenxin, born in 1966, Ph. D., associate professor. His research interests include advanced manufacturing management, e-commerce.

WANGBailin, born in 1983, Ph. D., lecturer. Her research interests include advanced manufacturing management, intelligent optimization method.