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

張琦琪,劉 鵬,張 濤

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

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

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

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

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

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

1 概述

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

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

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

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

2 問題描述及建模

2.1 問題描述

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

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

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

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

I:計(jì)劃出庫或入庫的板坯集合;

Timei:板坯i計(jì)劃出庫或入庫時(shí)間;

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

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

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

T:計(jì)劃展望期。

定義決策變量如下:

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

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

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

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

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

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

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

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

3.1.2 Agent構(gòu)造

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

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

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

(1)板坯Agent

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

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

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

2)知識

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

3)行為規(guī)則

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

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

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

圖3 入庫板坯Agent行為

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

(2)行車Agent

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

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

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

2)知識

行車運(yùn)行能力信息,即行車運(yùn)輸規(guī)則、與板坯Agent和與臺(tái)車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通信,判斷是否滿足板坯出庫批次,若滿足,則運(yùn)輸板坯出庫并更新狀態(tài),若不滿足,則在上料口空載等待。

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

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

(3)臺(tái)車Agent

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

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

主要包括臺(tái)車配置信息和臺(tái)車位移范圍的信息。

2)知識

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

3)行為規(guī)則

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

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

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

3.1.3 黑板模型

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

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

3.2 協(xié)商機(jī)制

本文引入市場行為中的投標(biāo)/仲裁機(jī)制來協(xié)調(diào)資源沖突。當(dāng)一個(gè)Agent有任務(wù)需要其他Agent合作完成時(shí),就向其他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)包括一輛臺(tái)車和多輛行車,以臺(tái)車Agent為例,構(gòu)造Agent間的協(xié)商機(jī)制。

符號說明:

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

道所需時(shí)間(即滿載運(yùn)行時(shí)間);

Timei:板坯i計(jì)劃出庫或入庫時(shí)間;

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

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

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

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

設(shè)計(jì)臺(tái)車的評價(jià)函數(shù)FTrolley如下:

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

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

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

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

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

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

表1 板坯運(yùn)輸時(shí)間均值統(tǒng)計(jì)

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

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

4.2 資源利用率分析

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

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

表2 資源利用率

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

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

5 結(jié)束語

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

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

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

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

[4] 計(jì)明軍,劉豐碩,李郭記,等.基于裝卸協(xié)同作業(yè)的集裝箱碼頭集卡調(diào)度及配置優(yōu)化[J].大連海事大學(xué)學(xué)報(bào),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] 李浩淵,汪定偉.集裝箱碼頭動(dòng)態(tài)集卡配置的并行仿真優(yōu)化方法[J].系統(tǒng)仿真學(xué)報(bào),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的集裝箱自動(dòng)化碼頭協(xié)同作業(yè)系統(tǒng)模型[J].計(jì)算機(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)工程理論與實(shí)踐,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é)基金資助項(xiàng)目(71171126);教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20130078110001);教育部留學(xué)回國人員科研啟動(dòng)基金資助項(xiàng)目;上海市哲學(xué)社會(huì)科學(xué)規(guī)劃基金資助項(xiàng)目(2011BGL015);上海財(cái)經(jīng)大學(xué)研究生創(chuàng)新基金資助項(xiàng)目(CXJJ-2013-435);上海市金融信息技術(shù)研究重點(diǎn)實(shí)驗(yàn)室開放課題基金資助項(xiàng)目。

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

2014-02-17

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

中文引用格式:張琦琪,劉 鵬,張 濤.基于多Agent的板坯出/入庫協(xié)同調(diào)度系統(tǒng)[J].計(jì)算機(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.