基于Agent的混合流水車間動態調度系統

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

(1.北京科技大學 東凌經濟管理學院,北京 100083; 2.鋼鐵生產制造執行系統技術教育部工程研究中心,北京 100083) (*通信作者電子郵箱zhangwx@manage.ustb.edu.cn)

基于Agent的混合流水車間動態調度系統

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

(1.北京科技大學 東凌經濟管理學院,北京 100083; 2.鋼鐵生產制造執行系統技術教育部工程研究中心,北京 100083) (*通信作者電子郵箱zhangwx@manage.ustb.edu.cn)

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

混合流水車間;多Agent;在線調度;機器故障;訂單插入

0 引言

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

現有的解決HFS問題的方法大多都基于集中的模型,全部的計算都在集中的模型中完成,而將機器和工件只是看作被動接收計算結果的客體,而非參與調度過程的實體。然而實際的生產系統又是離散的、分布式的、動態的和隨機的,因此現有的方法缺乏靈活性并且在發生意外事件時難以及時響應作出調整。

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

盡管HFS調度是一類重要的車間調度問題，并且在實際生產中各類動態事件時有發生,但在作者掌握的范圍內,尚未找到利用多Agent技術解決HFS動態調度問題的公開發表文獻, 因此本文設計了基于多Agent的HFS動態調度系統,系統能夠處理在線調度、機器故障重調度以及訂單插入重調度。

1 混合流水車間動態調度問題

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

1.1 在線調度

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

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

2)訂單到來的時間可能為生產開始時刻到結束前的任何時間,新加入訂單可能包含單個工件或者多個工件。

3)以最小化Makespan作為調度目標。

1.2 機器故障

1)機器空閑時不發生故障;故障在執行加工的過程中隨機發生,持續時間為隨機。

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

3)機器故障不僅會導致工件在機器故障發生之前對機器的占用時間失去意義,并且機器需要占用時間來進行修復,因此發生機器故障會導致Makespan增大,重調度的目標是最小化Makespan。

1.3 訂單插入

訂單插入是指在初始調度執行的過程中有新的生產訂單到來,主要考慮:

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

2)訂單加入的時間可能為生產開始時刻到結束前的任何時間,新加入訂單可能包含單個工件或者多個工件。

3)新訂單加入后的重調度目標是最小化Makespan。

2 基于MAS的調度系統

2.1 Agent模型

多Agent調度系統由管理Agent、策略Agent、工件Agent、機器Agent組成。系統結構如圖1表示。

圖1 基于多Agent的HFS調度系統結構

2.1.1 管理Agent

管理Agent(Manage Agent,MA)由工件數據庫、車間結構模塊、黑板系統和調度管理模塊構成,管理Agent結構如圖2所示。

圖2 管理Agent結構

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

2)車間結構模塊。該模塊從工件數據庫中讀取所有工件的信息并從實際車間讀取車間機器信息,然后根據這些信息動態地生成與實際車間情況對應的工件Agent群和機器Agent群。

3)黑板系統。即Agent之間交互通信所需的共享通信平臺,黑板系統存儲各個Agent公共可見的動態數據,如生產過程中機器的狀態和釋放時間、工件在各階段的加工狀態和釋放時間等,以便Agent在協調的過程中能夠更加快速地查找所需的信息來求解自己的子問題。

4)調度管理模塊。其功能是在調度開始時激活所有Agent開始工作,并且將所有機器的加工狀態、當前加工工件及工件各階段的開工和完工時間通過動態甘特圖顯示出來。

2.1.2 策略Agent

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

圖4 MAS系統Agent間協調機制

2.1.3 工件Agent

工件Agent(Job Agent, JA)是由管理Agent根據已到來的工件動態生成的,每個工件對應一個JA,JA由數據模塊、狀態顯示模塊和行為模塊組成,如圖3所示。

1)數據模塊記錄兩部分數據：一部分是靜態數據,另一部分是生產中產生的動態數據。靜態數據包括:工件的序號、各階段的加工時間等信息。動態數據包括:工件的優先值、各階段開工完工時間、各階段分配機器、各階段加工狀態等。這些數據同樣作為管理Agent中的黑板系統中的公用數據,以便其他Agent能夠快速查詢到所需的信息。

2)狀態顯示模塊用狀態圖的形式顯示出工件當前所處狀態。

3)行為模塊集成了JA與其他Agent的協調邏輯。

圖3 機器Agent及工件Agent結構

2.1.4 機器Agent

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

1)數據模塊中的靜態數據包括:機器序號、機器類型;動態數據包括:機器釋放時間、已安排在機器上加工的工件和機器當前狀態。這些數據同樣作為黑板系統里的公用數據。

2)狀態顯示模塊用狀態圖的形式來顯示機器當前的狀態。

3)行為模塊集成RA與其他Agent的協調邏輯。

2.2 Agent間協調機制

HFS動態調度系統的四類Agent間協調機制如圖4所示,具體描述如下:

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

2)在生產開始后每個RA和JA分別獨立進行工作,二者的協調機制如下:

生產開始時,所有待加工工件都釋放到第一階段,所有機器初始釋放時間都為0。對于每個JA,當工件釋放時,就請求安排到釋放時間最早的空閑機器上。

當RA接收到JA的安排請求時,如果同時只接到一個JA發出的請求,則立即安排對應工件進行加工;否則如果接收到多個JA同時發出的安置請求,則選擇其中優先值最大的工件安排加工,并向被選擇工件發送消息通知請求被接受,對另外的工件則通知其請求被拒絕。

當JA接收到拒絕通知時,則重新查詢空閑機器,如果有則向其RA發送安置請求。

每當有機器釋放時,RA去查詢當前已經釋放到機器對應階段但還未開始加工的等待工件,如果有則安排其中優先值最大的工件開始加工。

每當工件完成一階段的加工時就立即釋放到下一階段,同時JA向下一階段的機器發送安置請求,直到所有階段完成,該工件完成加工。直到所有工件完成加工生產結束。

3 動態調度策略與算法

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

3.1 機器故障處理策略

當故障發生時,故障機器RA更新機器信息:將其狀態標為故障,將中斷工件從已安排工件隊列中刪除,更新釋放時間為當前時刻加上故障修復時間。隨即向該工件JA發送故障消息,當中斷工件JA收到故障消息時,更新工件信息,該工件重新釋放到故障階段。管理Agent查詢此時在第一階段中所有已釋放但未開始加工工件,如果超過一個則調用HIS算法重新產生Strategy序列，否則Strategy序列不變。在策略Agent調用算法產生新的Strategy序列之后通知MA,MA根據新隊列通知各JA更新優先值,并通知所有JA和RA繼續工作。處理過程各Agent的協調機制如圖5所示。

圖5 機器故障重調度處理機制

3.2 新訂單加入的處理策略

當生產的過程中有訂單插入或者當在線調度訂單到來時,到來工件立刻釋放到第一階段,管理Agent查詢此時在第一階段中已釋放未加工工件,如果有兩個或以上則通知策略Agent調用HIS算法重新產生Strategy序列。策略Agent產生新的Strategy序列之后通知MA,MA根據新隊列通知各JA更新優先值,并通知所有JA和RA繼續進行工作。處理過程各Agent的協調機制如圖6所示。

3.3 HIS算法

調度規則和啟發式算法因為計算速度快、反應靈活,被廣泛用于解決調度問題。目前,已有多位學者對混合流水車間下的多種構造啟發式算法進行了比較研究。文獻[15]研究了5種Flowshop的啟發式算法運用于HFS問題以期最小化Makespan和Mean Flow Time,結果表明NEH算法在所有指標上更優；文獻[16]以最小化Makespan和拖期時間為目標研究了5種啟發式算法和多種調度規則在HFS問題中的應用,結果同樣表明NEH法的表現明顯優于其他算法。為了能在敏捷生產要求下產生良好的調度效果,本文針對混合流水車間環境,基于NEH算法的設計思路,提出了HIS算法。

3.3.1 主算法——插值排序法

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

HIS算法表述如下:

圖6 訂單插入重調度處理機制

3.3.2 機器分配及排序子算法

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

機器分配機制和機器上的工件排序機制的調度思想如下。

對于工件:

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

THEN請求安排到釋放時間最小的空閑機器上;

ELSE加入等待隊列;

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

THEN

{ IF(此時還有空閑機器)

THEN請求安排到釋放時間最小的空閑機器上;

ELSE加入等待隊列;

}

對于機器:

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

THEN

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

THEN將工件安排到機器上;

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

}

IF(機器釋放)

THEN

{ IF(等待隊列不為空)

THEN從等待隊列選擇優先值最大的工件安排加工;

具體步驟為:

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

Step2 若此時Cj≠?,則

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

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

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

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

5)若Cj≠?則轉到1);否則轉到Step3。

Step3 若此時j=s,則轉到Step4;否則j=j+1并轉到Step2。

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

4 仿真實驗

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

4.1 在線調度

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

表1 在線調度實驗結果(每次到達10個工件)

仿真結果表明,在兩種不同的訂單到來頻率下,在不同數量工件的情況下,本文提出的多Agent調度系統,能夠迅速地在訂單到來之時及時對未安排加工的工件進行重調度,實驗結果表明在HIS算法產生排序方案的基礎上最終的Cmax明顯優于其他調度規則產生的排序方案的基礎上完成加工的Cmax。

4.2 故障重調度

在故障重調度的仿真中,工件數量為20個,共計3個階段,每個階段有3臺同速機,工件在各階段的加工時間服從均勻分布,pij∈[5,30],在調度開始時,策略Agent調用HIS算法產生靜態調度下的Strategy序列,隨后所有工件Agent和機器Agent根據Strategy序列進行協調并開始生產。故障隨機產生,故障參數如表2所示。

表2 故障參數表

注：T表示初始調度中故障機器上最后一個操作的完工時間。

同時將調度規則與HIS算法進行重調度結果對比。運用調度規則進行重調度時,在發生故障后根據選擇調度規則賦予工件在各階段的優先值,各Agent根據優先值進行協調并完成加工。

表3 故障重調度實驗算例

表4 故障重調度實驗結果

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

圖7 故障重調度前后甘特圖

表5 訂單插入重調度實驗結果

4.3 訂單插入動態調度

在訂單插入動態調度仿真中,工件數量為20,階段數為3,工件加工時間服從均勻分布pij∈[5,30],插入訂單到來時間T=U[0.1,0.9]*Cmax,插入訂單包含工件數量為隨機1～5。為了對比HIS算法的重調度效果,將HIS算法與調度規則進行對比實驗。訂單插入發生后,在調用HIS算法重調度時,會產生新的Strategy序列,隨后各Agent根據產生的序列繼續協調并完成生產。在調用調度規則進行重調度時,根據所選擇的調度規則賦予工件在各階段的優先值,隨后各Agent根據工件優先值進行協調并完成生產。實驗結果如表5所示,算例7插單前以及插單后用兩種方法進行重調度甘特圖對比如圖8所示。

圖8 訂單插入重調度前后甘特圖

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

5 結語

大多數現有的解決HFS問題的算法都集中于模型,所有的計算都集中在模型完成,將機器和工件當作接受調度結果的客體,缺乏靈活性。本文設計了基于Agent的混合流水車間調度系統,設計了各Agent之間的協調機制,從而將工件和機器視為參與調度過程的實體。基于NEH算法的設計思路,針對混合流水車間問題以及動態調度問題的特點,提出了系統的核心算法(HIS),該算法適用于靜態調度和多種動態調度問題。在發生動態事件時,系統能迅速根據當前車間中機器和工件的加工狀態由策略Agent調用HIS算法產生新的排序方案,根據新的排序方案,工件Agent和機器Agent能即刻繼續協調工作以完成工件在機器上的分配和排序。最終仿真結果表明,此MAS產生的調度效果比多種調度規則更優,能夠適應多種動態事件同時并存的動態生產環境。

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] 李鐵克, 肖擁軍, 王柏琳. 基于局部性修復的HFS機器故障重調度[J]. 管理工程學報, 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] 李應, 楊善林, 鄭家強. 敏捷制造系統的基于Agent的混合調度[J]. 系統仿真學報, 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] 龍田, 石宇強, 王俊佳. 柔性作業車間在線調度問題的仿真建模與分析[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。

國家自然科學基金資助項目(71231001);中央高校基本科研業務費專項資金資助項目(FRF-BD-16-006A);北京市自然科學基金資助項目(9174038)。

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

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.