基于多Agent的柔性作業(yè)車間預(yù)先/重調(diào)度系統(tǒng)

任海英，鄒艷蕊

(北京工業(yè)大學經(jīng)濟與管理學院，北京 100124)

動態(tài)調(diào)度問題的提出，主要應(yīng)對生產(chǎn)過程中出現(xiàn)的各種干擾因素，如急件到達、加工機器故障、工件取消和工件優(yōu)先權(quán)增加等，從而保證既定預(yù)先調(diào)度計劃得以正常執(zhí)行。因此，需要根據(jù)系統(tǒng)狀況不斷地進行生產(chǎn)計劃的重調(diào)度，以保證生產(chǎn)過程的順利進行。目前，動態(tài)調(diào)度問題主要分為3類［1］:完全反應(yīng)調(diào)度、魯棒性調(diào)度和預(yù)先/重調(diào)度。完全反應(yīng)調(diào)度可以理解為實時控制，基于生產(chǎn)系統(tǒng)的當前狀態(tài)做出每個工件的調(diào)度決定。動態(tài)調(diào)度問題主要利用局部信息，其實質(zhì)為局部優(yōu)化調(diào)度，并不能滿足全局優(yōu)化的要求。魯棒性調(diào)度在調(diào)度開始前即考慮到車間調(diào)度環(huán)境中可能發(fā)生的不確定性事件，并將這些不確定性事件以某種形式集成到調(diào)度中，但冗余度過高、對實時事件反應(yīng)能力差會影響到魯棒性調(diào)度的優(yōu)化效果。預(yù)先/重調(diào)度在融合上述兩種調(diào)度的優(yōu)點，摒棄兩者弱點的基礎(chǔ)上，將其分為兩個步驟來執(zhí)行:①產(chǎn)生一個工作車間預(yù)測的理想調(diào)度，即預(yù)先調(diào)度。②執(zhí)行過程中發(fā)現(xiàn)沒有預(yù)測的干擾時，根據(jù)一定策略修改預(yù)先調(diào)度。

預(yù)先/重調(diào)度方法已經(jīng)得到了廣泛的研究，遺傳算法、啟發(fā)式算法和分派規(guī)則是預(yù)先/重調(diào)度經(jīng)常用到的方法，并且取得了豐富的成果。文獻［2］在分離圖表的基礎(chǔ)上提出重調(diào)度算法，即對受到影響的操作重新調(diào)度。文獻［3］研究了預(yù)先/重調(diào)度，在柔性制造車間領(lǐng)域結(jié)合應(yīng)用了遺傳算法和啟發(fā)式算法，不僅利用遺傳算法實現(xiàn)了預(yù)先調(diào)度，還在重調(diào)度過程中考慮了機器故障、急件到達、訂單優(yōu)先權(quán)增加和訂單取消等4種干擾，同時對每種干擾設(shè)計一整套相應(yīng)的啟發(fā)式算法，通過與分派規(guī)則比較，證明所提方法用于預(yù)先/重調(diào)度的優(yōu)越性。WONG［4］等將計劃和調(diào)度結(jié)合，基于Agent采用市場招投標的方式實現(xiàn)預(yù)先/重調(diào)度。但是這些方法不是計算量大就是效果不明顯。多Agent方法已經(jīng)廣泛應(yīng)用于生產(chǎn)調(diào)度方面，但用Agent方法研究預(yù)先/重調(diào)度還較少，沒有形成系統(tǒng)的理論。為此，筆者以柔性作業(yè)車間為調(diào)度對象，用Agent方法對其預(yù)先/重調(diào)度問題做一次初步探索。

1 預(yù)先/重調(diào)度系統(tǒng)

1.1 問題描述

筆者對柔性作業(yè)車間調(diào)度問題做出如下描述:某車間有多臺機器并生產(chǎn)多種產(chǎn)品，將每種產(chǎn)品的一個計劃加工批次看作一個工件，其需要若干工序完成，每道工序可在一臺或多臺機器上完成。假定每道工序加工前的準備時間和生產(chǎn)單元間的運輸時間與產(chǎn)品和批量無關(guān)，均記入加工時間，且加工過程中除設(shè)備外的其他資源充足，無須調(diào)度。工件預(yù)先到達車間，每個工件都有各自的工期。預(yù)先調(diào)度的目標是最小化平均滯后:

式中:Cj為工件j的完工時間;dj為工件j的工期;n為工件的數(shù)量。

在調(diào)度執(zhí)行過程中，會產(chǎn)生多種類型的干擾，因此需要重調(diào)度以促進調(diào)度繼續(xù)可行。重調(diào)度的目標為:①在干擾發(fā)生后的最短反應(yīng)時間內(nèi)保證調(diào)度的可行性;②保證預(yù)先調(diào)度目標的優(yōu)化;③最小化與預(yù)先調(diào)度背離。由于在處理干擾過程中，會出現(xiàn)加工工具轉(zhuǎn)移和開始時間改變導致攜帶成本的情況，因此，筆者應(yīng)用開始時間背離解釋重調(diào)度方案的優(yōu)劣，其中開始時間背離為重調(diào)度與預(yù)先調(diào)度之間工件的工序完成時間差的總和，即:開始時間背離=Delay+Rush;Delay為完成時間差為正值的總和;Rush為完成時間差為負值的總和。

1.2 調(diào)度系統(tǒng)的Agent指標

(1)工件Agent(PA)。每個工件對應(yīng)唯一的PA，其主要負責為對應(yīng)的工序選擇最優(yōu)機器，并達到最優(yōu)目標。所謂最優(yōu)目標，即在工期前完成加工任務(wù)且完成時間最短。PA屬性主要包含:工件號、工件類型、工件的工序列表、釋放時間、工期，以及機器投標列表等。

(2)機器Agent(MA)。每臺機器對應(yīng)唯一的MA，其主要負責投標工作和選擇加工工件等。MA的屬性主要包含:機器類型和狀態(tài)、工件招標列表、中標列表、等待列表、加工列表和機器故障等。MA的目標是使自身收益最大化。

(3)工序Agent(SA)。工件的每一道工序?qū)?yīng)唯一的SA，同時工序信息記錄在SA中。工序信息包含:工序最早開始時間、工序加工開始時間和完成時間、可加工該道工序的備選機器及其加工時間等。調(diào)度過程中，SA從數(shù)據(jù)庫中讀取與其對應(yīng)的機器信息和時間信息，將其發(fā)送至相應(yīng)PA，并放入工件工序列表。SA主要用來記錄工序狀態(tài)，屬非智能型的反應(yīng)式Agent，用于工序招標和評標，并將中標安排到相應(yīng)機器。

1.3 預(yù)先調(diào)度策略

筆者采用多對多協(xié)商機制建立調(diào)度系統(tǒng)，其協(xié)商和調(diào)度流程按如下5個步驟進行:

(1)工件信息注冊、機器信息注冊以及Agent指派。工件抵達車間后，系統(tǒng)賦予每個工件一個唯一的PA。PA從數(shù)據(jù)庫中讀取相應(yīng)工件的到期日和工序列表信息，并將相應(yīng)工件注冊到工件列表。同時，車間中的機器均具有一個MA，其保證將所有機器注冊至機器列表中［5］。

(2)PA向相應(yīng)MA進行招標。PA完成一道工序后，會隨即從工序列表中選擇下一道工序，并向選中工序的所有可選機器MA發(fā)出招標信息，招標信息放在工件招標列表中，主要包括工件類型和機器類型。PA進入投標等待階段。

(3)MA統(tǒng)籌其招標工件，并發(fā)出投標。MA主要根據(jù)Arrange原則計算工件相應(yīng)工序的開始時間和完成時間，填寫投標標書后發(fā)送至向其招標的工件PA，同時將投標標書放入機器投標列表中。MA進入中標等待階段。

(4)PA選擇MA。PA根據(jù)最小完成時間確定中標機器［6］，并將相應(yīng)工件的工序添加至MA工件招標列表中。

(5)MA選擇中標工件。若工件中標列表中有多個工件，MA則根據(jù)關(guān)鍵比率CR(見式(2))選擇工件，若CR相同，MA則利用SPT規(guī)則選擇工件。MA將選中的工件放入工件加工列表，然后對選中工件的下一道工序繼續(xù)招標，其余未被選中工件，離開機器的工件中標列表，重新招標。

式中:dj為工件j的工期;ct為當前時刻;Rjm為工件j在第m臺機器加工前的剩余加工時間，即，Sjm為工件j在第m臺機器加工前的剩余工序集合。

1.4 重調(diào)度策略

1.4.1 重調(diào)度假設(shè)條件

條件1 忽略重調(diào)度時間，一旦重調(diào)度完成，相應(yīng)工件立刻進入加工狀態(tài)。

條件2 所有干擾隨機產(chǎn)生，且不會在重調(diào)度的過程中產(chǎn)生。

條件3 采用不間斷策略，即受到影響的工件完成重調(diào)度后，該工件在新機器上重新開始加工。

條件4 僅考慮機器故障和急件到達兩種干擾。假設(shè)可準確估計機器故障發(fā)生時的故障持續(xù)時間，假設(shè)急件到達時其重要性遠大于普通工件。

1.4.2 重調(diào)度的基本思路

采用受到影響的工件重新調(diào)度方法，要點是識別受到影響的工件，并對其進行重新調(diào)度。

對于機器故障，在機器故障的這段時間加工的工序必然受到影響，相應(yīng)的工件完成時間也會受到影響。有時受到影響的工件工序會導致延遲后的完成時間大于加工計劃中隨后工序的開始時間，這就導致調(diào)度不可行，因此需要對直接和間接受到影響的工件工序進行識別，將它們放入受到影響的工件列表(AO)中，由Agent重新進行招標和調(diào)度安排［7］。

對于急件到達，急件直接插入到能夠加工它的機器上進行加工，同時將機器上預(yù)先安排的工件工序加入到AO中重新進行招標和調(diào)度安排。

1.4.3 機器故障談判策略

(1)定義機器故障開始時間、故障持續(xù)時間和機器號為機器故障，當故障機器MA識別到受影響的PA后，會解除二者之間的合作關(guān)系。識別方法如下:

If((工件相應(yīng)工序的開始時間≤故障開始時間and工件相應(yīng)工序的結(jié)束時間＞故障開始時間)或者(工件的開始時間≥故障開始時間and工件的開始時間＜故障開始時間+故障持續(xù)時間))

Then{MA將該工件相應(yīng)工序放入到AO中，并將其從工件加工列表中刪除，設(shè)置工件的加工狀態(tài)為未加工}

(2)AO列表中的PA向能夠加工它的MA進行招標。檢查AO，如果列表中工件工序之前的工序并沒有在AO中(保證工件的前后兩道工序不同時招標)，則工件的相應(yīng)工序向能夠加工它的機器進行招標，招標信息包括最早開始時間和最晚開始時間，計算公式如下:

最早開始時間=max{故障開始時間，前續(xù)工序的完成時間}

最晚開始時間=If(它是最后一道工序){工件的最后期限-加工時間}

Else{工件的下一道工序的開始時間-加工時間}

(3)MA安排受到影響的工件并向工件投標。投標MA根據(jù)工件相應(yīng)工序最小松散時間(最晚開始時間-最早開始時間)選擇加工工件，并安排工件。安排方式如下:

在工件相應(yīng)工序的最早開始時間之后

if(工件加工列表在兩個工件之間有空位置存在)then{工件相應(yīng)工序的開始時間=空位置的開始時間，工件加工列表索引號=空位置之前的工件工序+1}

Else{開始時間=機器上最后一道工序的完成時間，工件加工列表索引號=工件最后一道工序的索引號+1};

工件相應(yīng)工序的完成時間=開始時間+加工時間。MA將完成時間和等待加工列表索引號寫入投標標書發(fā)送給相應(yīng)PA。MA刪除相應(yīng)的招標信息。

(4)PA選擇MA。工件選擇最小完成工序時間的機器，并將相應(yīng)工件的工序放入到工件等待加工列表。PA刪除相應(yīng)的投標信息。

(5)機器加工工件。PA檢查工件的后續(xù)工序和相應(yīng)機器工件等待加工列表中的下一道工序是否受到影響，如果受到影響，放入到AO中，并進行招標。

1.4.4 急件到達談判策略

(1)急件PA到達系統(tǒng)。干擾屬性包括工件類型，工件的到達時間。系統(tǒng)通過工件類型從數(shù)據(jù)庫中調(diào)出工件的相關(guān)屬性，來產(chǎn)生急件［8］。

(2)急件的相應(yīng)工序向能夠加工它的機器進行招標。相應(yīng)內(nèi)容如預(yù)先調(diào)度。

(3)MA安排急件。由于是急件，因此優(yōu)先級高于其他普通工件，安排方式如下:

if(機器當前有工件)then{急件的開始時間=機器當前工件的完成時間}

if(機器當前沒有工件)then{急件的開始時間=急件的到達時間}。

并將信息發(fā)送給相應(yīng)機器，內(nèi)容如預(yù)先調(diào)度。

(4)急件選擇機器。同機器故障談判策略的步驟(4)。

(5)急件離開機器。機器加工完急件后，急件的下一道工序進行招標，轉(zhuǎn)到步驟(2);MA檢查工件等待加工列表中的后續(xù)工件是否受到影響，如果受到影響，則將后續(xù)工件工序放入到AO中，按照機器故障談判策略選擇機器進行加工。

2 仿真實驗

筆者采用 CHRYSSLOURIS等［9］的實驗方法測試上述模型的有效性，假設(shè)實驗條件為:車間擁有4個工作中心、9種機器和10種工件，每種工件的工序在1到5之間不等，且某些工序可被不同機器加工，實驗所用數(shù)據(jù)參考文獻［10］的附錄A(主要包含工件數(shù)量、工件工序數(shù)、加工時間和加工機器類型等)。仿真實驗將上述數(shù)據(jù)錄入數(shù)據(jù)庫，并利用Eclipse平臺連接數(shù)據(jù)庫，讀取相應(yīng)的工件信息、工序信息和加工進度等。當10種工件同時到達車間時，干擾是隨機產(chǎn)生的，機器故障的開始時間是0到MakeSpan之間的隨機數(shù)，機器故障的持續(xù)時間是0到500之間的隨機數(shù)。急件也是隨機產(chǎn)生的，急件的到達時刻是0到MakeS-pan之間的隨機數(shù)。每次試驗進行10次，取其平均數(shù)。為了比較，筆者采用Jain的初始調(diào)度(遺傳算法)和right-shift重新調(diào)度方法分別與預(yù)先調(diào)度和重調(diào)度結(jié)果比較(由于Jain是可中斷調(diào)度，無法與其比較)，證明所提出方法的優(yōu)越性。工期的設(shè)定采用TWK規(guī)則:

式中:rj為工件j的釋放時間;Pj為工件j的加工時間;K為工期緊急度系數(shù)，將K設(shè)為1.5。

2.1 預(yù)先調(diào)度結(jié)果

預(yù)先調(diào)度結(jié)果如圖1所示，預(yù)先調(diào)度目標函數(shù)的結(jié)果如表1所示。

圖1 預(yù)先調(diào)度結(jié)果

表1 預(yù)先調(diào)度目標函數(shù)的結(jié)果

與Jain的遺傳算法相比，多Agent方法的平均滯后、MakeSpan和機器利用率都有相應(yīng)程度的提高，平均滯后提高13.01%，MakeSpan提高4.60%，機器利用率提高5.21%。

2.2 重調(diào)度結(jié)果

2.2.1 機器故障實驗

在機器故障實驗中，分別測算隨機產(chǎn)生0、6、9、12、15、18、21 次故障的機器，與 right-shift方法比較結(jié)果如表2所示。

2.2.2 急件到達實驗

在急件到達實驗中，分別測算0、1、2、3個急件到達的情況，急件到達的目標函數(shù)如表3所示。

2.2.3 結(jié)果分析

(1)與預(yù)先調(diào)度相比，重調(diào)度系統(tǒng)在受到干擾影響之后，其平均滯后、MakeSpan和MeanFlowTime都有相應(yīng)程度的增大，機器利用率也相應(yīng)下降。

(2)隨著干擾程度的加深，各預(yù)先調(diào)度目標函數(shù)受到影響，開始時間背離也相應(yīng)增大。

(3)從表2和表3可以看出，當干擾發(fā)生時，相比right-shift方法，多Agent方法的各目標函數(shù)得到相應(yīng)優(yōu)化。

3 結(jié)論

建立了多Agent的柔性車間預(yù)先/重調(diào)度系統(tǒng)，用Java語言進行程序設(shè)計，以平均滯后為預(yù)先調(diào)度主要目標，開始時間背離為重調(diào)度目標進行仿真實驗，通過將預(yù)先調(diào)度與Jain的遺傳算法、重調(diào)度與right-shift方法相比較，結(jié)果表明了筆者所提出的方法的優(yōu)越性。由于只考慮機器故障和急件到達兩種干擾，因此對其他干擾進行策略設(shè)計和實驗，并對所提干擾處理策略進行優(yōu)化，將是筆者下一步的研究目標。

表2 機器故障目標函數(shù)結(jié)果

表3 急件到達目標函數(shù)結(jié)果

［1］VIEIRA G E，HERRMANN J W，LIN E.Rescheduling manufacturing systems:a framework of strategies，policies，and methods ［J］.Journal of scheduling，2003(6):39-62.

［2］ABUMAIZAR R J，SVESTKA J A.Rescheduling job shops under random disruptions［J］.International Journal of Production Research，1997，35(7):2065-2082.

［3］JAIN A K，ELMARAGHY H A.Production scheduling/rescheduling in flexible manufacturing［J］.International Journal of Production Research，1997，35(1):281-309.

［4］WONG T N，LEUNG C W，MAK K L，et al.Integrated process planning and scheduling/rescheduling-an agent-based approach［J］.International Journal of Production Research，2006，44(15):3627-3655.

［5］WONG T N，LEUNG C W，MAK K L，et al.An agent-based negotiation approach to integrate process planning and scheduling［J］.Int J Prod Res，2006，44(7):1331–1351.

［6］任海英，鄒艷蕊.基于多Agent協(xié)商的柔性車間調(diào)度系統(tǒng)［J］.微計算機信息，2011，27(1):14-16.

［7］李賢，王占杰.基于工藝路線的多Agent車間調(diào)度系統(tǒng)設(shè)計與實現(xiàn)［D］.遼寧:大連理工大學圖書館，2007.

［8］CHURCH L K，UZSOY R.Analysis of periodic and event-driven rescheduling policies in dynamic shops［J］.International Journal of Computer Integrated Manufacturing，1992，5(3):153-163.

［9］CHRYSSOLOURIS G，PIERCE J E，DICKE K.A decision-making approach to the operation of flexible manufacturing systems［J］.The International Journal of Flexible Manufacturing Systems，1992，3(4):309-330.

［10］SIWAMOGSATHAM T，SAYGIN C.Auction-based distributed scheduling and control scheme for flexible manufacturing systems［J］.Int J Prod Res，2004，42(3):547-572.