任海英，鄒艷蕊

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中:dj為工件j的工期;ct為當(dāng)前時(shí)刻;Rjm為工件j在第m臺(tái)機(jī)器加工前的剩余加工時(shí)間，即，Sjm為工件j在第m臺(tái)機(jī)器加工前的剩余工序集合。

1.4 重調(diào)度策略

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

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

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

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

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

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

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

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

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

1.4.3 機(jī)器故障談判策略

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

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

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

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

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

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

Else{工件的下一道工序的開(kāi)始時(shí)間-加工時(shí)間}

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

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

if(工件加工列表在兩個(gè)工件之間有空位置存在)then{工件相應(yīng)工序的開(kāi)始時(shí)間=空位置的開(kāi)始時(shí)間，工件加工列表索引號(hào)=空位置之前的工件工序+1}

Else{開(kāi)始時(shí)間=機(jī)器上最后一道工序的完成時(shí)間，工件加工列表索引號(hào)=工件最后一道工序的索引號(hào)+1};

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

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

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

1.4.4 急件到達(dá)談判策略

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

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

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

if(機(jī)器當(dāng)前有工件)then{急件的開(kāi)始時(shí)間=機(jī)器當(dāng)前工件的完成時(shí)間}

if(機(jī)器當(dāng)前沒(méi)有工件)then{急件的開(kāi)始時(shí)間=急件的到達(dá)時(shí)間}。

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 機(jī)器故障實(shí)驗(yàn)

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

2.2.2 急件到達(dá)實(shí)驗(yàn)

在急件到達(dá)實(shí)驗(yàn)中，分別測(cè)算0、1、2、3個(gè)急件到達(dá)的情況，急件到達(dá)的目標(biāo)函數(shù)如表3所示。

2.2.3 結(jié)果分析

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

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

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

3 結(jié)論

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

表2 機(jī)器故障目標(biāo)函數(shù)結(jié)果

表3 急件到達(dá)目標(biāo)函數(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］.微計(jì)算機(jī)信息，2011，27(1):14-16.

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