姜　雪，全雄文，陳秋雙

(南開(kāi)大學(xué)計(jì)算機(jī)與控制工程學(xué)院，天津300071)

?

基于真實(shí)吐露貪婪機(jī)制的多Agent單機(jī)調(diào)度問(wèn)題

姜雪，全雄文，陳秋雙

(南開(kāi)大學(xué)計(jì)算機(jī)與控制工程學(xué)院，天津300071)

在分布式環(huán)境下，從組合拍賣的角度出發(fā)研究了多Agent的單機(jī)調(diào)度問(wèn)題，設(shè)計(jì)了一種貪婪機(jī)制.該貪婪機(jī)制包括貪婪分配算法和貪婪支付算法兩部分，首先貪婪分配算法以資源Agent收益最大為目標(biāo)解決組合拍賣中的競(jìng)勝標(biāo)問(wèn)題，然后貪婪支付算法以第二價(jià)格支付的形式確定中標(biāo)者應(yīng)該支付的最小費(fèi)用.本文證明了該貪婪機(jī)制的真實(shí)吐露性，并通過(guò)算例說(shuō)明設(shè)計(jì)機(jī)制的可行性與有效性.最后進(jìn)行仿真實(shí)驗(yàn)比較該貪婪機(jī)制與線性規(guī)劃方法的求解效果，結(jié)果表明，對(duì)大規(guī)模問(wèn)題，該機(jī)制能夠快速得到使系統(tǒng)總收益近似最優(yōu)的調(diào)度方案.

多Agent單機(jī)調(diào)度；組合拍賣；真實(shí)吐露；貪婪機(jī)制

1　引　言

21世紀(jì)，在制造業(yè)全球化的大背景下，多企業(yè)的協(xié)同設(shè)計(jì)制造現(xiàn)象越來(lái)越普遍.國(guó)際分工和企業(yè)間分工日益深化和細(xì)化，對(duì)于非核心業(yè)務(wù)，企業(yè)通常以原始設(shè)備制造商(original equipment manufacturer，OEM)等方式外包給其他企業(yè).典型的如小米公司，其2013年產(chǎn)值突破了300億元.小米手機(jī)的設(shè)計(jì)由其設(shè)計(jì)部通過(guò)互聯(lián)網(wǎng)聯(lián)合小米發(fā)燒友共同完成，生產(chǎn)由多個(gè)OEM協(xié)同實(shí)現(xiàn)，這種模式被業(yè)界稱“小米模式”.當(dāng)前這種基于互聯(lián)網(wǎng)的協(xié)同設(shè)計(jì)和生產(chǎn)模式[13]受到了廣泛關(guān)注，已成為實(shí)現(xiàn)我國(guó)制造業(yè)結(jié)構(gòu)轉(zhuǎn)型的一個(gè)重要途徑.為了實(shí)現(xiàn)“分散資源集中使用，集中資源分散服務(wù)”的目標(biāo)，必須建立面向服務(wù)的制造資源公共服務(wù)平臺(tái).但是，現(xiàn)有的制造資源服務(wù)平臺(tái)提供的預(yù)定與收費(fèi)規(guī)則都很簡(jiǎn)單，缺乏互相之間的協(xié)調(diào)機(jī)制和對(duì)資源的優(yōu)化配置功能.這就需要設(shè)計(jì)更加高效合理的運(yùn)營(yíng)模式，在滿足客戶Agent對(duì)制造資源服務(wù)需求的同時(shí)，保證資源Agent的收益，這樣才能吸引和鼓勵(lì)更多的資源Agent參與和提供制造服務(wù)，實(shí)現(xiàn)制造資源的整合和優(yōu)化配置.

在處理分布式環(huán)境下的多Agent調(diào)度問(wèn)題時(shí)，由于Agent可能不愿意或無(wú)法與其他Agent或統(tǒng)一協(xié)調(diào)者交換所有的私有信息，因此如何恰當(dāng)?shù)乇硎竟行畔⑴c各Agent私有信息，設(shè)計(jì)有效的協(xié)調(diào)通訊協(xié)議，在合理的計(jì)算時(shí)間內(nèi)得到合理的分配方案就成為多Agent調(diào)度技術(shù)面臨的主要困難.而拍賣機(jī)制是一種用來(lái)繞過(guò)技術(shù)和計(jì)算困難的主要手段.首先，拍賣可以很好的保護(hù)Agent的獨(dú)立性和私有信息；其次，拍賣可以提供激勵(lì)機(jī)制，使得參與拍賣的Agent都能透露自己對(duì)于不同調(diào)度方案的真實(shí)估價(jià).

自從Myerson[4]提出最優(yōu)拍賣設(shè)計(jì)以來(lái)，拍賣機(jī)制的設(shè)計(jì)一直是許多研究者關(guān)注的研究主題[58].近年來(lái)，將組合拍賣機(jī)制應(yīng)用于分布式機(jī)器調(diào)度領(lǐng)域已引起許多學(xué)者的關(guān)注，Kutanoglu等[9]證明了組合拍賣與機(jī)器調(diào)度中經(jīng)典的拉格朗日松弛算法之間的等價(jià)關(guān)系，為組合拍賣應(yīng)用于機(jī)器調(diào)度問(wèn)題提供了理論依據(jù)；呂賜興等[10]將基于多Agent的協(xié)商策略應(yīng)用于敏捷生產(chǎn)調(diào)度中，利用拉格朗日對(duì)偶理論和組合拍賣機(jī)制之間的聯(lián)系，采用拉格朗日乘子作為時(shí)段(time slot)的價(jià)格，通過(guò)對(duì)該價(jià)格的調(diào)整來(lái)解決工件之間的沖突，協(xié)調(diào)可行調(diào)度方案的形成過(guò)程；Attanasio等[11]對(duì)幾種不同的價(jià)格更新機(jī)制進(jìn)行了比較；Liu等[12]則將機(jī)器調(diào)度中的不確定因素(如機(jī)器故障、工件動(dòng)態(tài)到達(dá)等)引入到組合拍賣的模型中，建立了采用拍賣機(jī)制解決動(dòng)態(tài)分布式機(jī)器調(diào)度問(wèn)題的框架，并通過(guò)仿真實(shí)驗(yàn)證明了在分布式環(huán)境下基于拍賣機(jī)制的調(diào)度方法優(yōu)于傳統(tǒng)的集中式調(diào)度方法；王剛等[7，8]在基于拍賣的多Agent協(xié)調(diào)調(diào)度方面對(duì)單機(jī)和并行機(jī)多Agent調(diào)度問(wèn)題進(jìn)行了研究，設(shè)計(jì)了一種基于重復(fù)叫價(jià)的組合拍賣機(jī)制和啟發(fā)式算法.文獻(xiàn)[10-12]均將連續(xù)時(shí)間離散化，將離散后的時(shí)間段作為商品進(jìn)行拍賣，文獻(xiàn)[7，8]采用多回合的拍賣形式.這種離散的多回合的組合拍賣形式，算法的收斂速度與拍賣輪次密切相關(guān)，在線計(jì)算量大，求解耗時(shí)長(zhǎng)，在實(shí)際操作中有諸多不便.相比之下，本文設(shè)計(jì)的貪婪機(jī)制是單回合的組合拍賣形式且無(wú)需將連續(xù)時(shí)間離散化，機(jī)制相對(duì)簡(jiǎn)單，具有很好的實(shí)時(shí)性.

本文針對(duì)制造資源服務(wù)平臺(tái)的需要，研究分布式環(huán)境下基于拍賣機(jī)制的多Agent資源共享、分配和協(xié)調(diào)調(diào)度的單機(jī)調(diào)度模型和方法.設(shè)計(jì)了一種基于單回合拍賣的貪婪機(jī)制，從理論上證明了該機(jī)制是真實(shí)吐露的，并用計(jì)算實(shí)例對(duì)此性質(zhì)進(jìn)行了驗(yàn)證，最后通過(guò)數(shù)值實(shí)驗(yàn)對(duì)該貪婪機(jī)制與線性規(guī)劃方法的求解效果進(jìn)行比較，并對(duì)結(jié)果進(jìn)行深入分析.

2　基于組合拍賣的多Agent單機(jī)調(diào)度問(wèn)題

2.1問(wèn)題描述

在分布式環(huán)境下有客戶Agent(i)，i=1，2，...，n，每個(gè)客戶Agent(i)有一個(gè)工件Ji需要加工；一資源Agent擁有一臺(tái)機(jī)器提供加工服務(wù)，該機(jī)器任一時(shí)刻只能加工一個(gè)工件.各客戶Agent的私有信息不能共享.所有工件的就緒時(shí)間均為資源Agent的規(guī)劃期的初始時(shí)刻0，工件Ji的加工時(shí)間為pi、交付期為di，在交付期前完工的客戶Agent(i)可獲得收益vi.為了在規(guī)定時(shí)間內(nèi)完工，客戶Agent(i)愿意支付一定的費(fèi)用bi，但不能超過(guò)他從該工件獲得的收益，即bi≤vi，客戶Agent(i)的效用為ui=vi-bi.若工件未在交付期前完工，客戶Agent獲得的收益為0.本文采用基于需求的投標(biāo)語(yǔ)言[13]，即客戶Agent(i)以〈pi，di，bi〉三元組的形式進(jìn)行投標(biāo).

2.2符號(hào)說(shuō)明

si為工件Ji的開(kāi)始加工時(shí)間；

M為一足夠大的正整數(shù)；

xi為0-1變量，xi=1表示工件Ji獲得所需的資源，否則xi=0；

yij為0-1變量，表示工件Ji和工件Jj加工的先后順序，yij=1表示工件Ji在工件Jj之前開(kāi)始加工，yij=0表示工件Ji在工件Jj之后開(kāi)始加工；

N(i)為客戶Agent(i)后第一個(gè)在沒(méi)有工件Ji時(shí)可中標(biāo)，但是有Ji時(shí)失標(biāo)的投標(biāo)者；

K(i)為排序表中客戶Agent(i)后的第一個(gè)投標(biāo)者；

li為客戶Agent(i)對(duì)其投標(biāo)加工時(shí)段的單位時(shí)間投標(biāo)值，即bi/pi；

Si=〈pi，di〉為客戶Agent(i)投標(biāo)的加工時(shí)段，即di之前長(zhǎng)度為pi的連續(xù)時(shí)間段；

θi=〈pi，di，bi〉為客戶Agent(i)的類型，表示其愿意為di之前長(zhǎng)度為pi的連續(xù)時(shí)間段支付的費(fèi)用為bi.以最大化資源Agent收益為目標(biāo)時(shí)，客戶Agent(i)在真實(shí)吐露的情況下，其愿意為Si支付的最大費(fèi)用應(yīng)等于其收益，即bi=vi.

2.3線性規(guī)劃方法

本文以最大化資源Agent收益為目標(biāo)，決策調(diào)度方案.競(jìng)勝標(biāo)模型為

用CPLEX對(duì)上述競(jìng)勝標(biāo)模型求解，得最優(yōu)調(diào)度方案，然后中標(biāo)者以投標(biāo)價(jià)格進(jìn)行支付.

2.4貪婪機(jī)制的設(shè)計(jì)

貪婪機(jī)制包括貪婪分配算法和貪婪支付算法兩部分.貪婪分配算法解決競(jìng)勝標(biāo)問(wèn)題，決策調(diào)度方案，貪婪支付算法確定投標(biāo)者的支付費(fèi)用.針對(duì)分布式環(huán)境下多Agent的單機(jī)調(diào)度問(wèn)題，本文以資源Agent收益最大為目標(biāo)，從拍賣的角度出發(fā)設(shè)計(jì)了一種貪婪機(jī)制.該機(jī)制的工作過(guò)程如下：

階段1收集客戶Agent(i)，i=1，2，...，n的投標(biāo)方案；

階段2根據(jù)投標(biāo)方案用貪婪分配算法決策機(jī)器可用加工時(shí)段的調(diào)度方案；

階段3貪婪支付算法計(jì)算中標(biāo)客戶Agent的支付費(fèi)用.

其中貪婪分配算法基于單位時(shí)間投標(biāo)值求解機(jī)器可用加工時(shí)段的調(diào)度方案，具體步驟如下：

步驟1li←bi/pi，i=1，2，...，n，對(duì)li按從大到小進(jìn)行排序，得到的序列記為L(zhǎng)；

步驟2t←0；

步驟3依次檢查L(zhǎng)中的l[i]對(duì)應(yīng)的工件J[i]，將其放在機(jī)器可用時(shí)段的初始時(shí)刻t，若其完工時(shí)間t+p[i]超過(guò)了交付期則失標(biāo)；若未超過(guò)交付期則中標(biāo)，且其開(kāi)始加工時(shí)間si為機(jī)器可用時(shí)段的初始時(shí)刻t，t←t+p[i].

貪婪支付算法用于確定客戶Agent的支付費(fèi)用，規(guī)則如下：

情形1若xi=0，則客戶Agent(i)的支付費(fèi)用為0；

情形2若xi=1，且存在N(i)，則客戶Agent(i)的支付費(fèi)用為pilN(i)；

情形3若xi=1，且不存在N(i)，則客戶Agent(i)的支付費(fèi)用為pilK(i).

2.5貪婪機(jī)制的真實(shí)吐露性

為了說(shuō)明本文設(shè)計(jì)的機(jī)制是真實(shí)吐露的，作出下列定義：

定義1真實(shí)吐露：機(jī)制是真實(shí)吐露的，如果對(duì)于各客戶Agent，投標(biāo)自己的真實(shí)類型時(shí)得到的效用大于等于其投標(biāo)的其他任何類型所得到的效用.

定義2偏好關(guān)系?：客戶Agent(i)投標(biāo)的加工時(shí)段為Si=〈pi，di〉，如果工件Ji的加工時(shí)間縮短或交付期延后，用表示，其中，則；對(duì)于投標(biāo)類型其中

定義3簡(jiǎn)單投標(biāo)者：假設(shè)客戶Agent(i)的真實(shí)類型為θi=〈pi，di，bi〉，客戶Agent(i)對(duì)Si=〈pi，di〉大于這一加工時(shí)段的估價(jià)為vi(Si)=bi，即其愿意為Si支付的最大費(fèi)用為bi，則其對(duì)加工時(shí)段S的估價(jià)為

定義4單調(diào)性(針對(duì)分配算法)：如果Agent(i)投標(biāo)θi= 〈pi，di，bi〉時(shí)中標(biāo)，則當(dāng)其投標(biāo)=時(shí)，i仍中標(biāo).即為更少的物品組合投入更多的錢，并不會(huì)使中標(biāo)者失標(biāo)；反之，為更多物品組合投入更少的錢，也不會(huì)使失標(biāo)者中標(biāo).

在客戶Agent為簡(jiǎn)單投標(biāo)者，分配算法滿足單調(diào)性的機(jī)制中，對(duì)于每一個(gè)客戶Agent的類型θ= 〈p，d，b〉存在一個(gè)臨界估價(jià)bc，當(dāng)b＞bc時(shí)，其中標(biāo)；當(dāng)b＜bc時(shí)，其失標(biāo)；當(dāng)b=bc時(shí)，不確定其是否中標(biāo).

定義5臨界性(針對(duì)支付算法)：中標(biāo)的客戶Agent的支付費(fèi)用等于其臨界估價(jià)bc.

定義6參與性(針對(duì)支付算法)：當(dāng)客戶Agent最終沒(méi)有完全得到自己投標(biāo)的加工時(shí)段時(shí)，其支付費(fèi)用為0.

文獻(xiàn)[14]已證明在投標(biāo)者為簡(jiǎn)單投標(biāo)者的情況下，如果拍賣機(jī)制滿足單調(diào)性、臨界性和參與性，則該機(jī)制是真實(shí)吐露的.

定理1本文設(shè)計(jì)的貪婪機(jī)制是真實(shí)吐露的.

證明 本文的客戶Agent均為簡(jiǎn)單投標(biāo)者.

對(duì)“單調(diào)性”，設(shè)Agent(i)的真實(shí)類型為θi=〈pi，di，bi〉，li=bi/pi，投標(biāo)θi時(shí)得到的排序表記為L(zhǎng)；對(duì)于投標(biāo)類型，投標(biāo)時(shí)排序表記為 L.假設(shè)?θi，則≥li，Agent(i)在中的位置比在L中的位置靠前.則如果i在排序表L中中標(biāo)，則i在排序表L中也中標(biāo)；如果i在排序表L中未中標(biāo)，i在L中也不可能中標(biāo).故貪婪分配算法滿足“單調(diào)性”.

顯然貪婪支付算法滿“參與性”.

對(duì)于“臨界性”，由貪婪支付算法情形2可知，中標(biāo)者的支付費(fèi)用恰好等于其可中標(biāo)時(shí)的最小投標(biāo)值.任何高于lN(i)的單位時(shí)間估價(jià)使客戶Agent(i)位于N(i)之前，如果有一個(gè)客戶Agentj(li＜ lj＜lN(i))，若j與i沖突，即當(dāng)i失標(biāo)時(shí)，j會(huì)中標(biāo)，這與N(i)是第一個(gè)這樣的投標(biāo)者相矛盾，所以i支付的最高費(fèi)用為pilN(i)；任何低于lN(i)的單位時(shí)間估價(jià)會(huì)使客戶Agent(i)失標(biāo)，因?yàn)镹(i)會(huì)中標(biāo)，故i中標(biāo)時(shí)支付的最低費(fèi)用為pilN(i).所以貪婪支付算法滿足“臨界性”.另外由于分布式環(huán)境下，各客戶Agent之間相互不知道對(duì)方的投標(biāo)信息，更不能確定自己的中標(biāo)情況，而為了保證資源Agent的收益，在不存在N(i)時(shí)按貪婪支付算法情形3支付.

3　數(shù)值實(shí)驗(yàn)

OR-Library是一個(gè)匯聚了各種運(yùn)籌學(xué)問(wèn)題的測(cè)試數(shù)據(jù)的電子數(shù)據(jù)庫(kù)，包羅了裝箱，背包，選址，網(wǎng)絡(luò)流，調(diào)度，旅行商以及車輛路徑等許多經(jīng)典運(yùn)籌學(xué)問(wèn)題的測(cè)試數(shù)據(jù).本文從OR-Library中Scheduling模塊下order acceptance and scheduling中選取一些經(jīng)典單機(jī)調(diào)度算例進(jìn)行實(shí)驗(yàn)，對(duì)線性規(guī)劃方法與貪婪機(jī)制進(jìn)行比較.所有實(shí)驗(yàn)均在MATLAB環(huán)境下編寫(xiě)貪婪機(jī)制的算法代碼，用YALMIP對(duì)優(yōu)化模型建模，調(diào)用CPLEX 12.5求解，電腦配置為Intel Core i3 3.10 GHz CPU和4GB RAM GB內(nèi)存.

3.1線性規(guī)劃方法不能保證真實(shí)吐露

本節(jié)設(shè)計(jì)實(shí)驗(yàn)，檢驗(yàn)線性規(guī)劃方法中客戶Agent的真實(shí)吐露性.實(shí)驗(yàn)測(cè)試10個(gè)算例，每個(gè)算例有10個(gè)客戶Agent，隨機(jī)選取6個(gè)Agent，謊報(bào)投標(biāo)值為收益的95%，90%，80%和75%.真實(shí)吐露情況與不同謊報(bào)投標(biāo)值情況下客戶Agent的總效用的比較見(jiàn)圖1.

圖1　客戶Agent總效用(Ec)的比較.Fig.1　Comparison of the client Agent s’utility(Ec).

從圖1可知，在投標(biāo)值等于收益時(shí)，客戶Agent的效用為0，隨著投標(biāo)值減小，客戶Agent的效用呈增加趨勢(shì).其中有幾組客戶Agent的總效用隨著投標(biāo)值減小有小幅下降，這是由于一些客戶Agent謊報(bào)程度過(guò)大而失標(biāo)，另一些謊報(bào)程度小或者無(wú)謊報(bào)的客戶Agent中標(biāo)，使客戶Agent的總效用有所下降.另外，對(duì)于每一個(gè)客戶Agent，謊報(bào)投標(biāo)值為收益的x倍時(shí)，中標(biāo)后效用為(1-x)v，客戶Agent為了增加其中標(biāo)后的效用有動(dòng)力謊報(bào)，故線性規(guī)劃方法不能保證客戶Agent真實(shí)吐露.

3.2貪婪機(jī)制能保證真實(shí)吐露

本節(jié)設(shè)計(jì)一個(gè)簡(jiǎn)單算例，驗(yàn)證貪婪機(jī)制的真實(shí)吐露性.假設(shè)有10個(gè)客戶Agent，每個(gè)客戶Agent有1個(gè)工件需要競(jìng)爭(zhēng)機(jī)器資源，機(jī)器規(guī)劃期為0～150，各客戶Agent的任務(wù)描述如表1所示.

表1　客戶Agent的任務(wù)描述Table 1　Task description for client Agents

用貪婪機(jī)制得到的中標(biāo)客戶Agent為Agent(3)，Agent(6)，Agent(8)，Agent(10)，相應(yīng)的支付費(fèi)用為18.4，47.5，37.1和30.9.以客戶Agent(3)為例分析，當(dāng)客戶Agent(3)謊報(bào)其投標(biāo)值在[18.4，19]內(nèi)時(shí)，仍中標(biāo)，但根據(jù)貪婪支付算法，其支付費(fèi)用不變，仍為18.4，這表明降低投標(biāo)值并不會(huì)增加其效用；當(dāng)客戶Agent(3)的投標(biāo)值小于18.4時(shí)，該Agent失標(biāo)，效用為0.與理論結(jié)論相符，客戶Agent謊報(bào)投標(biāo)值時(shí)其效用不會(huì)增加，卻有失標(biāo)的可能.算例分析再次證實(shí)本文設(shè)計(jì)的貪婪機(jī)制能夠激勵(lì)各Agent吐露真實(shí)信息.

3.3單位時(shí)間估價(jià)相近時(shí)，貪婪機(jī)制可保證較好的資源Agent收益

本節(jié)設(shè)計(jì)實(shí)驗(yàn)比較貪婪機(jī)制與不同謊報(bào)估價(jià)情況下線性規(guī)劃方法得到的資源Agent的收益.本實(shí)驗(yàn)測(cè)試10個(gè)工件的情況，各客戶Agent的單位時(shí)間估價(jià)由均勻分布隨機(jī)生成，根據(jù)分布區(qū)間的不同(見(jiàn)表2)，分為兩組實(shí)驗(yàn)數(shù)據(jù)，每組10個(gè)算例.隨機(jī)選取6個(gè)客戶Agent，謊報(bào)估價(jià)為收益的95%、90%、80%和75%，同一組實(shí)驗(yàn)中謊報(bào)Agent保持不變.進(jìn)行兩組實(shí)驗(yàn)，1)客戶Agent的單位時(shí)間估價(jià)在[10，15]上時(shí)，貪婪機(jī)制分別與4種謊報(bào)投標(biāo)值情形下線性規(guī)劃方法得到的資源Agent收益、客戶Agent總效用和系統(tǒng)收益進(jìn)行比較，實(shí)驗(yàn)結(jié)果見(jiàn)圖2；2)單位時(shí)間估價(jià)在[10，30]上時(shí)，貪婪機(jī)制分別與4種謊報(bào)投標(biāo)值情形下線性規(guī)劃方法得到的資源Agent收益(Πr)、客戶Agent總效用(Fc)和系統(tǒng)收益(Πs)進(jìn)行比較，實(shí)驗(yàn)結(jié)果見(jiàn)圖3.

表2　客戶Agent的單位時(shí)間估價(jià)的均勻分布區(qū)間Table 2　The uniform distribution interval for the unit time valuation of client Agents

從圖2(a)與圖2(b)可知：當(dāng)客戶Agent的單位時(shí)間估價(jià)在[10，15]上時(shí)，貪婪機(jī)制得到的資源Agent收益近似等于謊報(bào)到收益的95%左右時(shí)線性規(guī)劃方法得到的資源Agent收益，貪婪機(jī)制得到的客戶Agent效用等于謊報(bào)到估收益的90%左右時(shí)線性規(guī)劃方法得到的客戶Agent的效用；從圖3(a)與圖3(b)可知，當(dāng)客戶Agent的單位時(shí)間估價(jià)在[10，30]上時(shí)，貪婪機(jī)制得到的資源Agent收益等于謊報(bào)到收益的80%左右時(shí)線性規(guī)劃方法得到的資源Agent收益，貪婪機(jī)制得到的客戶Agent效用等于謊報(bào)到收益的80%左右時(shí)線性規(guī)劃方法得到的客戶Agent的效用.

綜合圖2(a)和圖3(a)與圖2(b)和圖3(b)可知，隨著客戶Agent投標(biāo)值的減小，線性規(guī)劃方法得到的調(diào)度方案的資源Agent的收益呈減小趨勢(shì)，客戶Agent的效用呈增加趨勢(shì).綜合圖2(c)和圖3(c)知，其系統(tǒng)收益呈遞減趨勢(shì).這是由于一些原本中標(biāo)的客戶Agent謊報(bào)程度過(guò)大而失標(biāo)，另一些單位時(shí)間估價(jià)低的客戶Agent中標(biāo)所致.

圖2　第一組實(shí)驗(yàn)結(jié)果(k為仿真算例編號(hào))Fig.2　The experimental results of first group(k is the simulation example number)

對(duì)比兩組實(shí)驗(yàn)，單位時(shí)間估價(jià)區(qū)間較小，即當(dāng)客戶Agent的單位時(shí)間估價(jià)相近時(shí)，貪婪機(jī)制得到的調(diào)度方案中，在保證客戶Agent合理的效用時(shí)，使資源Agent獲得較好的收益.因此在線性規(guī)劃方法無(wú)法保證客戶Agent真實(shí)吐露的情況下，采用貪婪機(jī)制可以得到較好的效果.當(dāng)客戶Agent的單位時(shí)間估價(jià)相差較大時(shí)，采用貪婪機(jī)制得到的調(diào)度方案中，中標(biāo)客戶Agent的支付費(fèi)用與其收益相差較大，資源Agent的收益損失變大，但是此時(shí)客戶Agent的效用(Ec)較大，這樣可以鼓勵(lì)更多的客戶Agent參與投標(biāo)，實(shí)現(xiàn)資源的優(yōu)化配置.

圖3　第二組實(shí)驗(yàn)結(jié)果(k為仿真算例編號(hào))Fig.3　The experimental results of second group(k is the simulation example number)

3.4兩種機(jī)制的求解效果

本節(jié)設(shè)計(jì)實(shí)驗(yàn)對(duì)兩種機(jī)制的系統(tǒng)收益，機(jī)器加工時(shí)段的單位時(shí)間收益和求解時(shí)間進(jìn)行比較.本實(shí)驗(yàn)分別測(cè)試需要加工的工件數(shù)為10，15，20和100個(gè)工件4種情況，每種情況10個(gè)算例.兩種機(jī)制下4種情況的10個(gè)算例的最終調(diào)度方案的平均中標(biāo)工件數(shù)、平均機(jī)器利用率、平均系統(tǒng)總收益、平均單位時(shí)間收益和平均求解時(shí)間如表3所示.

表3　貪婪機(jī)制與線性規(guī)劃方法求解結(jié)果比較Table 3　Comparison between the Greedy Mechanism and Linear Programming

從表3可以看出，貪婪機(jī)制得到的系統(tǒng)收益近似于最優(yōu)系統(tǒng)收益；貪婪機(jī)制得到的最終調(diào)度方案使得機(jī)器加工時(shí)段的單位時(shí)間收益高于線性規(guī)劃方法得到機(jī)器單位時(shí)間收益；隨著工件數(shù)增多，線性規(guī)劃方法的求解時(shí)間顯著增加，且對(duì)于15個(gè)工件的情況，由于計(jì)算量太大，只有1個(gè)算例在有效時(shí)間內(nèi)求解成功，對(duì)于20個(gè)和100個(gè)工件2種情況，全部算例在有效時(shí)間內(nèi)無(wú)法得到調(diào)度方案，而貪婪機(jī)制對(duì)4種情況均在1 s內(nèi)得到了全部算例的調(diào)度方案.

4　結(jié)束語(yǔ)

針對(duì)分布式環(huán)境下的多Agent單機(jī)調(diào)度問(wèn)題，本文從拍賣的角度出發(fā)，設(shè)計(jì)了一種貪婪機(jī)制，該機(jī)制包括貪婪分配算法和貪婪支付算法兩部分，貪婪分配算法解決競(jìng)勝標(biāo)問(wèn)題，貪婪支付算法以第二價(jià)格支付的形式確定中標(biāo)者的支付費(fèi)用，該機(jī)制能夠保證真實(shí)吐露，且機(jī)制規(guī)則簡(jiǎn)單，方便執(zhí)行.實(shí)驗(yàn)表明，本文設(shè)計(jì)的貪婪機(jī)制能夠激勵(lì)客戶Agent真實(shí)吐露；在各客戶Agent對(duì)機(jī)器加工時(shí)段的單位時(shí)間估價(jià)相近時(shí)，該機(jī)制可以保證資源Agent較好的收益；對(duì)大規(guī)模問(wèn)題，該機(jī)制能夠快速得到使系統(tǒng)總收益接近最優(yōu)的調(diào)度方案.本文的研究還可以進(jìn)一步深入，在競(jìng)勝標(biāo)問(wèn)題中考慮客戶優(yōu)先權(quán)和留住重要客戶等調(diào)度指標(biāo)，推廣到平行機(jī)調(diào)度問(wèn)題等.這些都有待于進(jìn)一步研究.

[1]YusufYY，SarhadiM，GunasekaranA.Agilemanufacturing：Thedrivers，conceptsandattributes.InternationalJournalofProduction Economics，1999，62(1/2)：33-43.

[2]王康周，江志斌，李娜，等.服務(wù)型制造綜合資源計(jì)劃體系研究.工業(yè)工程與管理，2011，16(3)：113-120. Wang K Z，Jiang Z B，Li N，et al.A framework for resource planning of service-oriented manufacturing.Industrial Engineering and Management，2011，16(3)：113-120.(in Chinese)

[3]李伯虎，張霖，王時(shí)龍，等.云制造：面向服務(wù)的網(wǎng)絡(luò)化制造新模式.計(jì)算機(jī)集成制造系統(tǒng)，2010，16(1)：1-7. Zhang B H，Zhang L，Wang S L，et al.Cloud manufacturing：A new service2oriented networked manufacturing model.Computer Integrated Manufacturing Systems，2010，16(1)：1-7.(in Chinese)

[4]Myerson R B.Optimal auction design.Mathematics of Operations Research，1981，6(1)：58-73.

[5]汪定偉.網(wǎng)上集中采購(gòu)的捆綁-組合拍賣機(jī)制設(shè)計(jì).系統(tǒng)工程學(xué)報(bào)，2011，26(6)：809-816. Wang D W.Mechanism design of hybrid bundling and combination auction for centralized E-procurement.Journal of Systems Engineering，2011，26(6)：809-816.(in Chinese)

[6]饒從軍，趙勇.可分離物品多屬性采購(gòu)拍賣的最優(yōu)機(jī)制.系統(tǒng)工程學(xué)報(bào)，2012，27(1)：88-98. Rao C J，Zhao Y.Optimal mechanism of multi-attribute procurement auction for divisible goods.Journal of Systems Engineering，2012，27(1)：88-98.(in Chinese)

[7]王剛，陳秋雙，杜玉泉等.基于組合拍賣的多主體單機(jī)調(diào)度問(wèn)題.計(jì)算機(jī)集成制造系統(tǒng)，2013，19(1)：106-113. Wang G，Chen Q S，Du Y Q，et al.Multi-Agent single machine scheduling based on combinatorial auction.Computer Integrated Manufacturing Systems，2013，19(1)：106-113.(in Chinese)

[8]王剛，陳秋雙.加工時(shí)間可控的多主體單機(jī)調(diào)度問(wèn)題研究.計(jì)算機(jī)集成制造系統(tǒng)，2013，19(9)：2187-2192. Wang G，Chen Q S.Multi-Agent scheduling with controllable processing times.Computer Integrated Manufacturing Systems，2013，19(9)：2187-2192.(in Chinese)

[9]Kutanoglu E，Wu S D.On combinatorial auction and Lagrangean relaxation for distributed resource scheduling.IIE Transaction，1999，31(9)：813-826.

[10]呂賜興，朱云龍，尹朝萬(wàn)，等.基于多Agent的敏捷生產(chǎn)調(diào)度中的協(xié)商策略.計(jì)算機(jī)集成制造系統(tǒng)，2006，12(4)：579-584. LüC X，Zhu Y L，Yi C W，et al.Negotiation policy for multi-Agent based agile production scheduling.Computers Integrated Manufacturing Systems.2006.12(4)：579-584.(in Chinese)

[11]Attanasio A，Ghiani G，Grandinetti L，et al.Auction algorithms for decentralized parallel machine scheduling.Parallel Computing，2006，32(9)：701-709.

[12]Liu Ning，Abdelrahman M A，Ramaswamy S.A complete multiagent framework for robust and adaptable dynamic job shop scheduling.IEEE Transactions on Systems，Man and Cybernetics，2007，37(5)：904-916.

[13]Parkes D C，Ungar L H.An Auction-based Method for Decentralized Train Scheduling//Proceedings of the 5th International Conference on Autonomous Agents.New York：ACM，2001：43-50.

[14]Lehmann D，O’Callaghan L I，Shoham Y.Truth revelation in approximately efficient combinatorial auctions.Journal of the ACM，2002，49(5)：577-602.

Multi-Agent single machine scheduling based on truthful greedy mechanism

Jiang Xue，Quan Xiongwen，Chen Qiushuang
(College of Computer and Control Engineering，Nankai University，Tianjin 300071，China)

This paper proposes a greedy mechanism based on combinatorial auction to solve the distributed multi-Agent scheduling problem.The greedy mechanism includes a greedy allocation algorithm and a greedy payment algorithm，where the former solves the winner determining problem with the goal of maximizing the revenues of source Agent and the latter determines the minimum fees that winners should pay in the form of second price payments.It is proved that the mechanism is truthful，and a series of numerical examples are used to illustrate the feasibility and validity of the greedy mechanism.Furthermore，a simulation experiment is done to compare the effectiveness of the greedy mechanism and the linear programming method.The result showsthatthegreedymechanismcansolvelarge-scaleschedulingproblemswithlesscomputationaltimewhile achieving near optimal revenues for the system.

multi-Agent single machine scheduling；combinatorial auction；truthful；greedy mechanism

TH166

A

1000-5781(2016)03-0423-08

10.13383/j.cnki.jse.2016.03.013

姜雪(1992-)，女，河南新鄉(xiāng)人，碩士生，研究方向：系統(tǒng)優(yōu)化與調(diào)度，Email：jiangxue s@163.com；

全雄文(1979-)，男，浙江永嘉人，博士，講師，研究方向：系統(tǒng)優(yōu)化與調(diào)度，Email：quanxw@nankai.edu.cn；

陳秋雙(1966-2015)，女，河北冀州人，教授，博士生導(dǎo)師，研究方向：系統(tǒng)優(yōu)化與調(diào)度，Email：chenqs@nankai.edu.cn.

2014-12-30；

2015-11-30.

國(guó)家自然科學(xué)基金資助項(xiàng)目(71172071；61403213)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(201200311100-36).