張琦琪,劉 鵬,張 濤

(1.上海財經(jīng)大學(xué)信息管理與工程學(xué)院,上海200433;2.上?？茖W(xué)技術(shù)職業(yè)學(xué)院,上海201800)

基于多Agent的板坯出/入庫協(xié)同調(diào)度系統(tǒng)

張琦琪1,2,劉 鵬1,張 濤1

(1.上海財經(jīng)大學(xué)信息管理與工程學(xué)院,上海200433;2.上?？茖W(xué)技術(shù)職業(yè)學(xué)院,上海201800)

針對板坯庫管理中的協(xié)同運輸問題,以最小化板坯出/入庫總運輸時間為目標(biāo),建立數(shù)學(xué)模型。構(gòu)建一個包括出庫板坯、入庫板坯、行車和臺車等在內(nèi)的板坯出/入庫協(xié)同調(diào)度無主控多Agent系統(tǒng),以統(tǒng)一的結(jié)構(gòu)封裝任務(wù)和資源,同時考慮板坯入庫作業(yè)和出庫作業(yè)2種任務(wù),提出在Agent之間建立投標(biāo)/仲裁機制,設(shè)計評價函數(shù)協(xié)調(diào)Agent之間的資源沖突,提高系統(tǒng)的柔性、并行性和自適應(yīng)能力。通過系統(tǒng)仿真,將出/入庫協(xié)同作業(yè)、完全出庫作業(yè)和完全入庫作業(yè)3種場景進(jìn)行比較。實驗結(jié)果表明,出/入庫協(xié)同管理系統(tǒng)可有效提高板坯庫的運輸吞吐率,且在投標(biāo)/仲裁機制的協(xié)商作用下,運輸設(shè)備利用率也顯著提高且保持均衡。

板坯出/入庫協(xié)同調(diào)度;多Agent系統(tǒng);黑板模型;投標(biāo)/仲裁機制;協(xié)同運輸;系統(tǒng)仿真

1 概述

鋼鐵企業(yè)中的板坯庫處于上游工序(連鑄)與下游工序(熱軋)之間,板坯出/入庫管理一方面需要緩沖來自上游連鑄工序的板坯進(jìn)行入庫運輸作業(yè);另一方面,還要根據(jù)下游熱軋生產(chǎn)的需求,對已經(jīng)存放在庫中的板坯進(jìn)行出庫運輸作業(yè)。在實際操作中,考慮到人工經(jīng)驗和操作靈活性,多采用出庫與入庫分時段靜態(tài)作業(yè)的方式;另外,出庫作業(yè)還受到熱軋工序批次的影響,作業(yè)隨時間分布不均勻,這些因素大大增加了板坯庫內(nèi)設(shè)備空載等待時間。因此,如何使庫中的大型運輸設(shè)備(輥道、行車和臺車等)得以合理利用、動態(tài)配置,實現(xiàn)出/入庫協(xié)同,是提高板坯庫物流系統(tǒng)運作效率、確保上下游工序協(xié)調(diào)性的關(guān)鍵所在。

目前,關(guān)于板坯庫的研究多聚焦于入庫決策[1]或出庫決策[2-3]的制定,涉及庫內(nèi)運輸問題的研究很少。但在集裝箱碼頭裝/卸貨協(xié)同運輸?shù)南嚓P(guān)研究中,文獻(xiàn)[4]同時考慮裝/卸過程,研究了集卡運輸路線及數(shù)量配備問題。文獻(xiàn)[5]針對集卡運輸,建立以等待時間和運輸時間加權(quán)和最小為目標(biāo)的模型并求解。文獻(xiàn)[6]構(gòu)建集裝箱碼頭整體作業(yè)仿真系統(tǒng),研究動態(tài)集卡配置對裝/卸作業(yè)的影響。這些研究為本文同時兼顧出/入庫2種運輸任務(wù)提供了很好的理論或?qū)嵺`支持。然而,板坯出/入庫調(diào)度是在運輸空間和位移方式都受限的情況下,研究多種設(shè)備協(xié)同運輸?shù)膯栴},系統(tǒng)運行時存在并行、協(xié)調(diào)、競爭等多種關(guān)系,這使板坯出/入庫協(xié)同調(diào)度問題變得十分復(fù)雜。

多Agent系統(tǒng)(Multi-Agent System,MAS)[7]是從問題的局部出發(fā),通過自底向上方式形成的一種分布式人工智能系統(tǒng)。多Agent系統(tǒng)因其在計算時間和空間上的并行性與分布性,比較適合解決生產(chǎn)調(diào)度和管理領(lǐng)域的問題[8-10]。在沖突協(xié)商方面,可以基于合同網(wǎng)協(xié)議[11]和擬市場機制[12-13]等策略。文獻(xiàn)[14]采用MAS方法將碼頭裝卸作業(yè)抽象為一系列智能體行為,構(gòu)建自動化碼頭協(xié)同運輸作業(yè)系統(tǒng)。文獻(xiàn)[15]將MAS技術(shù)應(yīng)用于分布式電梯群控系統(tǒng),基于擬市場協(xié)商機制建模以降低平均候梯時間和平均乘梯時間。文獻(xiàn)[16]以典型的流程工業(yè)過程為對象,提出熱連軋機工業(yè)生產(chǎn)過程多智能體系統(tǒng)的體系結(jié)構(gòu),并設(shè)計了相應(yīng)的協(xié)調(diào)控制機制。以上研究表明,多Agent系統(tǒng)在解決分布式動態(tài)調(diào)度問題中具有優(yōu)勢。然而,以上系統(tǒng)均使用控制Agent或管理Agent等主控角色指揮整個系統(tǒng)的協(xié)同工作,隨著問題規(guī)模的擴大,主控Agent會因其通信量過大而降低系統(tǒng)的整體性能。

本文設(shè)計并實現(xiàn)一種無主控的自治系統(tǒng),構(gòu)建一個包括出庫板坯、入庫板坯、行車和臺車等在內(nèi)的板坯出/入庫協(xié)同調(diào)度模型,將入庫作業(yè)和出庫作業(yè)劃分為多個子工序,以統(tǒng)一結(jié)構(gòu)封裝任務(wù)(板坯)和資源(運輸設(shè)備),并依據(jù)自身不同的屬性,形成各自的行為規(guī)則,平等主動地參與到系統(tǒng)運作中;根據(jù)設(shè)備的物理狀態(tài)(位置、負(fù)載情況等)和板坯的出/入庫計劃時間等因素,確定Agent的評價函數(shù),以仲裁的方式協(xié)商解決資源沖突,最后通過系統(tǒng)仿真實驗對出/入庫協(xié)同作業(yè)、完全入庫作業(yè)和完全出庫作業(yè)3種場景的運輸性能進(jìn)行比較分析。

2 問題描述及建模

2.1 問題描述

板坯出/入庫協(xié)同調(diào)度系統(tǒng)實際上是一個離散事件動態(tài)系統(tǒng)。系統(tǒng)的隨機性主要體現(xiàn)在同一板坯的2次調(diào)度所用時間可能不同,這主要是由:(1)運輸設(shè)備在完成上一次任務(wù)后的停止位置不確定; (2)入庫板坯和出庫板坯可以選擇多條入庫路徑或出庫路徑。

問題描述如下:在不考慮板坯倒垛的情況下,已知準(zhǔn)備出/入庫的板坯集I、板坯計劃出/入庫時間Timei和板坯庫中所有運輸設(shè)備集J。運輸設(shè)備在某一時間只能服務(wù)一塊板坯,一塊板坯在某一時間只能被一個運輸設(shè)備服務(wù),且各種運輸設(shè)備的運輸時間不確定,求板坯集的最小出/入庫總運輸時間。

2.2 數(shù)學(xué)模型

為了能更準(zhǔn)確地表述模型,引入如下符號體系:

I:計劃出庫或入庫的板坯集合;

Timei:板坯i計劃出庫或入庫時間;

J:板坯庫內(nèi)所有運輸設(shè)備的集合;

Ji:未知向量,表示板坯i的出/入庫路徑,對應(yīng)于相應(yīng)的解;

Mi:已知集合,表示板坯i的可行出/入庫路徑集(板坯的出/入庫運輸有特定的規(guī)則);

T:計劃展望期。

定義決策變量如下:

其中,i表示出庫或入庫的板坯,i∈I;j表示板坯庫中的運輸設(shè)備,j∈J;t表示時間,t∈T。令 τij1={t|Xijt=1}表示板坯i被設(shè)備j響應(yīng)的時間;τij2={t|Zijt=1}表示板坯i被設(shè)備j完成運輸任務(wù)的時間。建立模型如下:

其中,式(1)表示最小化板坯的出/入庫總運輸時間;式(2)表示對于運輸設(shè)備j,完成板坯i運輸任務(wù)的時間不小于響應(yīng)板坯i的時間;式(3)和式(4)表示運輸設(shè)備j從響應(yīng)板坯i的申請到完成板坯i的運輸任務(wù)期間,不允許響應(yīng)其他板坯的申請,即運輸任務(wù)不允許中斷;式(5)和式(6)表示一塊板坯同一時刻只能被一臺設(shè)備服務(wù),且運輸任務(wù)不允許中斷;式(7)表示運輸設(shè)備j響應(yīng)板坯i申請的時間不早于板坯i計劃出庫/入庫時間;式(8)保證服務(wù)于板坯i的設(shè)備工藝路線(出/入庫路徑)的可行性。

3 板坯出/入庫協(xié)同調(diào)度系統(tǒng)

3.1 系統(tǒng)設(shè)計

板坯出/入庫協(xié)同調(diào)度系統(tǒng)屬于典型的多環(huán)節(jié)復(fù)雜動態(tài)系統(tǒng),且各工序環(huán)節(jié)相互制約,受很多隨機因素的影響,解析方法的求解結(jié)果對分析實際設(shè)備的并行工作行為和資源利用情況能力有限。因此,本文采用MAS技術(shù),設(shè)計并實現(xiàn)了一個基于主動實體協(xié)作的系統(tǒng)。根據(jù)系統(tǒng)的全局目標(biāo),將整個系統(tǒng)分解為出/入庫板坯、行車和臺車等多個智能Agent族群。這樣,各個Agent的局部目標(biāo)將歸結(jié)為最小化Agent的空載等待時間,即最大化Agent的資源利用率。整個系統(tǒng)由板坯調(diào)度計劃信息庫、智能Agent族群和黑板模型構(gòu)成,如圖1所示。

圖1 板坯出/入庫協(xié)同調(diào)度MAS系統(tǒng)

3.1.1 板坯調(diào)度計劃信息庫

板坯調(diào)度計劃信息庫主要包括板坯庫配置信息、庫內(nèi)板坯信息、連鑄工序生產(chǎn)計劃和熱軋工序生產(chǎn)計劃等信息。板坯庫配置信息是與倉庫物理環(huán)境相關(guān)的信息,包括倉庫規(guī)模、庫內(nèi)運輸設(shè)備配置情況等;庫內(nèi)板坯信息記錄板坯庫中現(xiàn)存板坯位置信息,包括板坯所處跨位、垛位等;連鑄生產(chǎn)計劃和熱軋生產(chǎn)計劃是根據(jù)板坯出/入庫決策產(chǎn)生的當(dāng)日計劃出/入庫板坯時序信息。系統(tǒng)通過訪問信息庫,根據(jù)計劃板坯的出/入庫時序,創(chuàng)建出庫和入庫的板坯Agent(Slab Agent),當(dāng)一塊板坯的出/入庫任務(wù)完成后,板坯Agent生命周期結(jié)束,并更新信息庫中的庫內(nèi)板坯記錄。

3.1.2 Agent構(gòu)造

主要包括板坯Agent、行車Agent和臺車Agent 3種族群。每個Agent的內(nèi)部都由知識庫、推理機、行為、通信、控制與決策5種構(gòu)件組成,如圖2所示。每個Agent都是以決策與控制為核心,通過通信構(gòu)件實時觀察外界環(huán)境變化,并根據(jù)知識庫中的領(lǐng)域知識等進(jìn)行推理,利用評價函數(shù),評價效用并確定行為,并再次通過通信構(gòu)件將行為結(jié)果反饋給系統(tǒng)。這里,將輥道運輸板坯的運動轉(zhuǎn)化為板坯的自主行為,這樣任務(wù)和資源即可不加區(qū)分地以統(tǒng)一結(jié)構(gòu)封裝。系統(tǒng)中所有Agent根據(jù)自身狀態(tài)(當(dāng)前位置、負(fù)載情況等)主動參與到系統(tǒng)的運行中。

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

Agent構(gòu)造的說明如下:

(1)板坯Agent

根據(jù)板坯的類型,分為出庫板坯Agent和入庫板坯Agent。出庫板坯Agent處理已存放在板坯庫中的冷坯,入庫板坯Agent處理經(jīng)過上游連鑄工序產(chǎn)生的熱坯。

1)數(shù)據(jù)

主要包括板坯i計劃出庫或入庫時間Timei、出庫板坯的起始位置(跨位、垛位)、批次信息、入庫板坯的目標(biāo)位置(跨位、垛位)等。

2)知識

出庫板坯和入庫板坯的能力信息,即輥道設(shè)備的運輸規(guī)則和板坯Agent與普通行車Agent的通信規(guī)則。

3)行為規(guī)則

Setp 1根據(jù)板坯i計劃出庫或入庫時間Timei,創(chuàng)建并初始化出庫板坯 Agent或入庫板坯Agent。

Setp 2出庫板坯Agent向所在跨的行車Agent發(fā)出庫申請,加入出庫申請隊列等待行車。入庫板坯Agent觀察板坯庫中的環(huán)境(包括各跨的緩沖床、輥道前方等資源是否空閑)。

Setp 3入庫板坯Agent依據(jù)圖3所示規(guī)則完成狀態(tài)的更新:靜止、垂直位移或水平位移。靜止,表示輥道處于等待狀態(tài);垂直位移,表示繼續(xù)在輥道上運輸前往下一個跨區(qū);水平位移,表示入庫板坯被推入緩沖床并向所在跨的行車 Agent發(fā)出入庫申請。

圖3 入庫板坯Agent行為

Setp 4重復(fù)以上步驟,直到所有出庫板坯加入出庫申請隊列或入庫板坯被推入緩沖床。

(2)行車Agent

行車Agent處理板坯庫中各個跨內(nèi)水平運送板坯的作業(yè),分為普通行車Agent和上料行車Agent,用于確保板坯按批次出庫。

1)數(shù)據(jù)

主要包括行車配置信息和每輛行車位移范圍的信息等。

2)知識

行車運行能力信息,即行車運輸規(guī)則、與板坯Agent和與臺車Agent的通信規(guī)則等。

3)行為規(guī)則

Setp 1根據(jù)數(shù)據(jù)和知識,創(chuàng)建并初始化上料行車Agent,轉(zhuǎn)Step2;創(chuàng)建并初始化普通行車Agent,轉(zhuǎn)Step3。

Setp 2上料行車Agent與普通行車Agent通信,判斷是否滿足板坯出庫批次,若滿足,則運輸板坯出庫并更新狀態(tài),若不滿足,則在上料口空載等待。

Setp 3普通行車Agent判斷當(dāng)前自身的狀態(tài),如果是滿載,則根據(jù)承載板坯的目標(biāo)位置,確定是否需要向臺車Agent發(fā)出送坯申請(將板坯送上臺車)并確定自身行為;如果是空載,普通行車Agent觀察本跨內(nèi)所有的出庫申請、入庫申請和從臺車上接取板坯取坯申請,然后根據(jù)當(dāng)前所處的位置及各個板坯計劃出/入庫時間Timei等因素,利用評價函數(shù)FCrane確定自身行為。

Setp 4重復(fù)Step2或Step3,直到所有批次出庫任務(wù)完成或所有出庫申請、入庫申請、取坯申請全部得到響應(yīng)。

(3)臺車Agent

臺車Agent處理板坯庫中各個跨間垂直運送板坯的臺車作業(yè)。

1)數(shù)據(jù)

主要包括臺車配置信息和臺車位移范圍的信息。

2)知識

臺車運行能力信息,即臺車運輸規(guī)則、與行車Agent的通信規(guī)則等。

3)行為規(guī)則

Setp 1根據(jù)數(shù)據(jù)和知識創(chuàng)建并初始化臺車Agent。

Setp 2臺車Agent判斷自身的狀態(tài),如果是滿載,則根據(jù)承載板坯的目標(biāo)位置來確定自身的行為,同時發(fā)送取坯申請,通知目標(biāo)跨的行車Agent接取板坯;如果是空載,則根據(jù)所有行車Agent的送坯申請、自身所處位置、板坯計劃出/入庫的時間Timei等因素,利用評價函數(shù)FTrolley,確定自身行為。

Setp 3重復(fù)Step2,直到所有的送坯申請全部得到響應(yīng)。

3.1.3 黑板模型

黑板模型體現(xiàn)了平行協(xié)商機制,是一個開放的公共數(shù)據(jù)區(qū),允許參與協(xié)商的各方在黑板上進(jìn)行信息共享,是一種信息透明度極高的民主合作方式下的協(xié)商機制。具體來講,入庫板坯Agent、出庫板坯Agent、普通行車 Agent、上料行車 Agent和臺車Agent將需要傳遞的信息,以廣播的方式,寫在系統(tǒng)的一個公共數(shù)據(jù)區(qū)內(nèi),具體包含全局?jǐn)?shù)據(jù)和局部數(shù)據(jù)2個部分。全局?jǐn)?shù)據(jù)是與出/入庫協(xié)同調(diào)度系統(tǒng)全局相關(guān)的數(shù)據(jù),包括系統(tǒng)時鐘、出/入庫板坯數(shù)量等。局部數(shù)據(jù)主要與各Agent族群相關(guān),記錄Agent之間的通信信息,包括板坯Agent向行車Agent發(fā)出的出庫申請或入庫申請及響應(yīng)集合、行車Agent向臺車Agent發(fā)出的送坯申請及響應(yīng)集合、臺車Agent向行車Agent發(fā)出的取坯申請及響應(yīng)集合等。圖4表明了各種Agent之間傳遞信息的情況。

圖4 系統(tǒng)通信序列

3.2 協(xié)商機制

本文引入市場行為中的投標(biāo)/仲裁機制來協(xié)調(diào)資源沖突。當(dāng)一個Agent有任務(wù)需要其他Agent合作完成時,就向其他Agent廣播有關(guān)該任務(wù)的信息,即招標(biāo);接到招標(biāo)信息的Agent檢查自身解決該問題的能力,然后發(fā)出投標(biāo)參數(shù);最后由發(fā)出招標(biāo)信息的Agent評估投標(biāo)參數(shù),選出最合適的中標(biāo)者并與之合作。假設(shè)系統(tǒng)包括一輛臺車和多輛行車,以臺車Agent為例,構(gòu)造Agent間的協(xié)商機制。

符號說明:

JC:表示發(fā)出送坯申請的行車集合,JC?J;

道所需時間(即滿載運行時間);

Timei:板坯i計劃出庫或入庫時間;

α:行車上的板坯i計劃出庫或入庫的時間Timei對應(yīng)的權(quán)值;

β:為臺車運行時間對應(yīng)的權(quán)值;

γ:為行車運行時間對應(yīng)的權(quán)值;

Batchi:當(dāng)板坯i為出庫板坯但不屬于當(dāng)前出庫批次時,Batchi為0;當(dāng)板坯i為入庫板坯或板坯i屬于當(dāng)前出庫批次時,Batchi為1。

設(shè)計臺車的評價函數(shù)FTrolley如下:

其中,Q為一個較大的常數(shù);Timei和是行車發(fā)出送坯申請時提供給臺車的報價,臺車結(jié)合自身因素完成評價,從發(fā)出送坯申請的行車集合JC中選擇一臺行車響應(yīng)送坯申請。

同理,普通行車Agent在收到來自本跨的入庫申請、出庫申請、取坯申請時,會依據(jù)Timei和行車空載移動到申請板坯i的時間2個因素來評價效用。式(10)為普通行車Agent的評價函數(shù)。

4 仿真實驗

本文以某著名鋼廠板坯庫的入庫和出庫運輸作業(yè)實際工藝路線為基礎(chǔ),將板坯出/入庫作業(yè)分解成輥道垂直運輸、行車水平運輸和臺車垂直運輸?shù)裙ば?設(shè)計多Agent板坯出/入庫協(xié)同調(diào)度系統(tǒng)。實驗采用NetLogo仿真軟件,相關(guān)參數(shù)為:板坯庫幾何尺寸為668 m×668 m;單入口,單出口;輥道4段,普通行車4輛,臺車1輛,上料行車1輛。實驗中入庫板坯目標(biāo)位置和出庫板坯的起始位置隨機產(chǎn)生,行車和臺車的初始位置隨機設(shè)定;所有設(shè)備的空/滿載運輸速度均為2 m/s,板坯在不同工序上的中轉(zhuǎn)作業(yè)時間為0。

4.1 出/入庫協(xié)同作業(yè)分析

假設(shè)出/入庫板坯全部為連鑄-離線軋制板坯(CCR),即考慮所需出/入庫運輸工序最復(fù)雜的情況。板坯的計劃入庫頻率為15塊/h,出庫計劃隨時間分布不均勻,以批次為單位進(jìn)行(每批板坯數(shù)≥5)。統(tǒng)計完全入庫作業(yè)、完全出庫作業(yè)和出/入庫協(xié)同作業(yè)3種場景下運輸板坯的作業(yè)時間,如表1所示。其中,出(或入)庫時間是指指板坯i的計劃出(或入)庫時間Timei與實際出(或入)庫時間的差值;出(或入)庫等待時間是指出(或入)庫時間之內(nèi)板坯處于靜止?fàn)顟B(tài)的總時間;總運輸時間是指系統(tǒng)完成所有運輸作業(yè)的總工作時間。平均吞吐率是指出/入庫板坯總數(shù)除以總運輸時間。

表1 板坯運輸時間均值統(tǒng)計

在完全入庫作業(yè)中,板坯處于等待狀態(tài)的時間很短,基本上到達(dá)入庫口后就會被推入目標(biāo)跨的緩沖床,且入庫路徑的選擇上大都不需要臺車中轉(zhuǎn),減小了運輸時間。在完全出庫作業(yè)中,由于受到出庫作業(yè)工藝路線集的約束,出庫作業(yè)大都需要使用臺車,而臺車的運能和數(shù)量都是有限的,所以與入庫作業(yè)相比,出庫作業(yè)時間較長,而且處于等待狀態(tài)的時間也明顯增加。

在出/入庫協(xié)同作業(yè)中,入庫板坯由于需要與出庫板坯競爭行車,因此滿載等待時間顯著增加,導(dǎo)致平均入庫時間增加;而出庫作業(yè)的時間與完全出庫作業(yè)相比并沒有明顯增加,這說明,出/入庫協(xié)同作業(yè)的多Agent系統(tǒng)能夠利用投標(biāo)/仲裁機制,充分發(fā)揮運輸設(shè)備空閑時間的作用,在入庫作業(yè)的同時進(jìn)行出庫操作,提高設(shè)備的利用率和并行性。當(dāng)出庫批次為2時,雖然出/入庫作業(yè)的等待時間都有增加,但是系統(tǒng)總的工作時間增長并不大,系統(tǒng)的并行能力得到充分發(fā)揮。系統(tǒng)平均吞吐率表明,出/入庫協(xié)同作業(yè)下,系統(tǒng)的并行能力大大提高,雖然板坯的總數(shù)增加了,但是,從整體角度而言,平均每塊板坯的運輸時間卻減少了。當(dāng)出庫批次增加為3時,無論是出庫板坯還是入庫板坯都會因為競爭資源陷入長時間的滿載等待中,系統(tǒng)整體性能下降。在實際生產(chǎn)中,可以增加直接熱裝板坯(DHCR)數(shù)量,以便同時緩解CCR出庫和入庫兩方面的運輸壓力。

4.2 資源利用率分析

資源利用率反映板坯庫內(nèi)的各種運輸設(shè)備在運輸過程中的使用情況,計算公式為:

通過仿真實驗,分別統(tǒng)計完全入庫作業(yè)、完全出庫作業(yè)和出/入庫協(xié)同作業(yè)3種場景下,普通行車和臺車的資源利用率,如表2所示。

表2 資源利用率

由表2可知,在完全入庫作業(yè)中,根據(jù)實際的入庫板坯數(shù)量,4輛普通行車的利用率基本保持均衡,且處于一個比較低的水平,存在大量的空載等待時間,同時臺車的利用率較低,只有目標(biāo)位于出庫口所在跨的入庫板坯需要臺車中轉(zhuǎn)。在完全出庫作業(yè)中,行車1和臺車的利用率都有一定的增加,但系統(tǒng)設(shè)備的利用率偏差較大,設(shè)備利用不均衡現(xiàn)象顯著。

與前2種情況相比,出/入庫協(xié)同作業(yè)中所有設(shè)備的利用率均明顯增加,空閑等待時間減少,并且保持均衡。其中,行車1和臺車的利用率增長明顯,這表明出庫作業(yè)大都依賴臺車中轉(zhuǎn)完成,且行車1除了負(fù)責(zé)來自本跨的出庫操作,還要接收經(jīng)臺車中轉(zhuǎn)而帶來的其他跨的出庫板坯,因此利用率增加,整個系統(tǒng)設(shè)備能力得到充分發(fā)揮。

5 結(jié)束語

板坯出/入調(diào)度系統(tǒng)是在同時兼顧出庫作業(yè)和入庫作業(yè)的前提下,采用多種運輸設(shè)備協(xié)同運輸?shù)姆植际讲⑿邢到y(tǒng)。本文以某鋼廠板坯庫庫內(nèi)運輸調(diào)度作業(yè)為背景,以最小化板坯出/入庫總運輸時間為目標(biāo)建立數(shù)學(xué)模型;基于MAS的計算機仿真方法,設(shè)計并實現(xiàn)了一個無主控的板坯出/入庫協(xié)同調(diào)度系統(tǒng),并基于招標(biāo)/投標(biāo)的協(xié)商機制,設(shè)計評價函數(shù)以仲裁方式協(xié)調(diào)資源沖突;最后通過系統(tǒng)仿真實驗對出/入庫協(xié)同作業(yè)、完全入庫作業(yè)和完全出庫作業(yè)3種運輸場景進(jìn)行比較,結(jié)果表明,出/入庫協(xié)同作業(yè)有效提高了板坯庫系統(tǒng)的運輸吞吐率,另外在投標(biāo)/仲裁機制的協(xié)商作用下,其運輸設(shè)備利用率也提高明顯且保持均衡。

[1] 涂雪平,施燦濤,李鐵克.基于模糊匹配的板坯入庫優(yōu)化決策問題模型及求解[J].北京科技大學(xué)學(xué)報, 2011,33(3):376-382.

[2] 徐駿馳,杜 斌,朱 俊,等.基于混合遺傳算法的板坯入庫優(yōu)化算法[J],控制工程,2009,16(5):547-550.

[3] 李耀華,王 偉,胡國奮,等.熱軋板坯庫出庫計劃編制模型與算法研究[J].計算機集成制造系統(tǒng),2006, 12(3):377-381.

[4] 計明軍,劉豐碩,李郭記,等.基于裝卸協(xié)同作業(yè)的集裝箱碼頭集卡調(diào)度及配置優(yōu)化[J].大連海事大學(xué)學(xué)報,2010,36(1):47-50.

[5] Lee D,Cao J X,Shi Q X.A Heuristic Algorithm for Yard Truck Schedule Problem in Container Terminals[J]. Tsinghua Science and Technology,2010,15(4):467-474.

[6] 李浩淵,汪定偉.集裝箱碼頭動態(tài)集卡配置的并行仿真優(yōu)化方法[J].系統(tǒng)仿真學(xué)報,2009,21(14): 4243-4247.

[7] Minsky M.The Society of Mind[M].New York,USA: Simon&Schuster,1988.

[8] Caridi M,Cavalieri S.Multi-agent Systems in Production Planning and Control:An Overview[J].Production Planning&Control,2004,15(2):106-118.

[9] Shen Weining,Wang Lihui,Hao Qi.Agent-based Distributed Manufacturing Process Planning and Scheduling:A State-of-the-artSurvey[J].IEEE Transactions on Systems,Man and Cybernetics,Part C: Applications and Reviews,2006,36(4):563-577.

[10] 趙 博,范玉順.MAS技術(shù)在生產(chǎn)調(diào)度研究中的應(yīng)用[J].控制與決策,2003,18(1):1-6.

[11] Smith R G.The Contract Net Protocol:High-level Communication and Control in a Distributed Problem Solver[J]. IEEE Transactions on Computers,1980,29(12):1104-1113.

[12] Adhau S,Mittal M L,Mittal A.A Multi-Agent System For Distributed Multi-Project Scheduling:An Auctionbased Negotiation Approach[J].Engineering Applications of Artificial Intelligence,2012,25(8):1738-1751.

[13] Siwamogsatham T,Saygin C.Auction-based Distributed Scheduling and Control Scheme for Flexible Manufacturing Systems[J].International Journal of Production Research, 2004,42(3):547-572.

[14] 王祥雪,朱 瑾.基于MAS的集裝箱自動化碼頭協(xié)同作業(yè)系統(tǒng)模型[J].計算機應(yīng)用研究,2013,30(4): 1072-1075.

[15] 王遵彤,孫 棟,喬 非,等.分布式電梯群控系統(tǒng)多目標(biāo)調(diào)度算法[J].控制理論與應(yīng)用,2010,27(5): 602-608.

[16] 董 潔,尹怡欣,彭開香.流程工業(yè)多智能體系統(tǒng)協(xié)調(diào)控制[J].系統(tǒng)工程理論與實踐,2008,(10):119-124.

編輯 顧逸斐

Slab Discharge/Location Coordinate Scheduling System Based on Multi-Agent

ZHANG Qiqi1,2,LIU Peng1,ZHANG Tao1
(1.School of Information Management and Engineering,Shanghai University of Finance and Economics,Shanghai 200433,China; 2.Shanghai Vocational College of Science and Technology,Shanghai 201800,China)

According to the collaborative transportation problem of the slab yard,this paper constructs a mathematical model to minimize the total slab discharge/location transportation time and designs an autonomous Multi-Agent System (MAS)including different roles,for example,the slab,the crane and the trolley.In this system,loading the slab into the yard and discharging the slab from the yard are considered at the same time.In addition,in order to coordinate the resource conflict,a multi-Agent negotiation and scheduling strategy based on biding-arbitration mechanism is incorporated into the system using evaluation functions.In system simulation,the slab discharge/location coordinate system is compared with single location or single discharge system respectively,and the results show that the transportation throughput of the coordinate system is better than the single ones,and facility utilization is effective and balanced.

slab discharge/location coordinate scheduling;Multi-Agent System(MAS);blackboard model;bidingarbitration mechanism;collaborative transportation;system simulation

1000-3428(2015)01-0289-07

A

C934

10.3969/j.issn.1000-3428.2015.01.055

國家自然科學(xué)基金資助項目(71171126);教育部高等學(xué)校博士學(xué)科點專項科研基金資助項目(20130078110001);教育部留學(xué)回國人員科研啟動基金資助項目;上海市哲學(xué)社會科學(xué)規(guī)劃基金資助項目(2011BGL015);上海財經(jīng)大學(xué)研究生創(chuàng)新基金資助項目(CXJJ-2013-435);上海市金融信息技術(shù)研究重點實驗室開放課題基金資助項目。

張琦琪(1977-),女,講師、博士研究生,主研方向:生產(chǎn)計劃與調(diào)度,智能優(yōu)化方法;劉 鵬、張 濤(通訊作者),教授、博士。

2014-02-17

2014-03-17 E-mail:taozhang@mail.shufe.edu.cn

中文引用格式:張琦琪,劉 鵬,張 濤.基于多Agent的板坯出/入庫協(xié)同調(diào)度系統(tǒng)[J].計算機工程,2015,41(1):289-295.

英文引用格式:Zhang Qiqi,Liu Peng,Zhang Tao.Slab Discharge/Location Coordinate Scheduling System Based on Multi-Agent[J].Computer Engineering,2015,41(1):289-295.