朱倩倩，王秀利，耿蘇杰

(南京理工大學(xué) 經(jīng)濟(jì)管理學(xué)院，江蘇 南京 210094)

0 引言

隨著工業(yè)4.0時(shí)代的到來(lái)，個(gè)性化需求、批量定制正逐漸成為潮流，云制造作為一種面向服務(wù)的網(wǎng)絡(luò)化制造新模式正越來(lái)越多地被制造企業(yè)采用，它是將現(xiàn)有網(wǎng)絡(luò)化制造和服務(wù)技術(shù)同云計(jì)算、物聯(lián)網(wǎng)等技術(shù)相融合，實(shí)現(xiàn)各類制造資源(機(jī)器設(shè)備、計(jì)算系統(tǒng)、數(shù)據(jù)等)的集中化和智能化管理，為制造全生命周期提供可隨時(shí)獲取、按需使用、安全可靠、優(yōu)質(zhì)低廉的各類制造活動(dòng)服務(wù)，其核心思想是實(shí)現(xiàn)分散資源的集中使用和集中資源的分散服務(wù)[1]。

在云制造模式的分散決策場(chǎng)景下，制造商的訂單接受與加工調(diào)度(Order Acceptance and Scheduling, OAS)問(wèn)題也受到越來(lái)越多的關(guān)注。在分散系統(tǒng)中，制造商的OAS問(wèn)題不僅受資源的約束，還受其他客戶選擇的約束，制造商和客戶作為“理性人”，往往力圖以最小經(jīng)濟(jì)代價(jià)獲得自身的最大經(jīng)濟(jì)利益，但對(duì)于制造系統(tǒng)而言，由于個(gè)體的自利性，在機(jī)制缺失的情況下，個(gè)體競(jìng)爭(zhēng)的均衡結(jié)果常常會(huì)降低系統(tǒng)資源配置的效率，從而導(dǎo)致系統(tǒng)全局目標(biāo)惡化，即分散決策代價(jià)[2-5](Price of Anarchy, POA)。POA是用來(lái)描述分散決策下的系統(tǒng)結(jié)果與系統(tǒng)全局最優(yōu)結(jié)果的關(guān)系，只有通過(guò)機(jī)制設(shè)計(jì)引導(dǎo)分散系統(tǒng)中的個(gè)體競(jìng)爭(zhēng)行為才能減小POA，優(yōu)化系統(tǒng)全局性能。Wang等[6]通過(guò)合同設(shè)計(jì)機(jī)制解決了一個(gè)制造商可內(nèi)部加工或轉(zhuǎn)包給代工企業(yè)加工訂單的OAS分散決策問(wèn)題，在假設(shè)所有訂單與加工能力信息透明的情況下，設(shè)計(jì)固定報(bào)價(jià)加轉(zhuǎn)移支付合同和數(shù)量折扣合同，實(shí)現(xiàn)分散決策下全局性能的最優(yōu)化。然而，在實(shí)際的分散決策場(chǎng)景中，制造商和客戶所掌握的訂單與加工能力信息都是不完全的，因此對(duì)不完全信息下OAS分散決策問(wèn)題的研究具有更重要的現(xiàn)實(shí)意義。

拍賣是一種基于參與者競(jìng)價(jià)的資源分配方式，能夠有效解決OAS分散決策中的信息不完全問(wèn)題。通過(guò)拍賣解決調(diào)度問(wèn)題，就是將資源的使用時(shí)間作為商品分配給競(jìng)標(biāo)者。近年來(lái)，拍賣在生產(chǎn)調(diào)度領(lǐng)域的應(yīng)用取得了很多研究成果。Kutanoglu等[7]采用組合拍賣機(jī)器時(shí)間的方式來(lái)解決復(fù)雜資源調(diào)度問(wèn)題，研究了基于加權(quán)拖期懲罰為目標(biāo)的加工車間作業(yè)調(diào)度問(wèn)題，發(fā)現(xiàn)了組合拍賣機(jī)制和基于拉格朗日分解之間的聯(lián)系；Dewan等[8]研究了基于拍賣的分布式環(huán)境下動(dòng)態(tài)加工車間作業(yè)調(diào)度問(wèn)題，以最小化提前和拖期懲罰為目標(biāo)，設(shè)計(jì)拍賣機(jī)制提高分散系統(tǒng)全局性能；Attanasio等[9]研究了拍賣機(jī)制在并行機(jī)調(diào)度中的應(yīng)用，以最小化完工時(shí)間為目標(biāo)，采用基于改進(jìn)拉格朗日啟發(fā)算法的拍賣機(jī)制優(yōu)化全局性能；Hall等[10]研究了多個(gè)單件訂單客戶通過(guò)競(jìng)爭(zhēng)制造商單機(jī)加工能力資源加工其訂單的問(wèn)題。文獻(xiàn)[10]從基于加工時(shí)間的調(diào)度目標(biāo)出發(fā)，設(shè)計(jì)了基于固定時(shí)段和靈活時(shí)段的升價(jià)拍賣(ascending price auction, 也稱英式拍賣)機(jī)制，分析了該拍賣機(jī)制所生成的最終決策結(jié)果能夠成為均衡解的條件。經(jīng)研究發(fā)現(xiàn)，上述文獻(xiàn)都采用傳統(tǒng)調(diào)度度量目標(biāo)(如訂單完工時(shí)間、總加權(quán)滯后時(shí)間等)，對(duì)于多主體企業(yè)追求收益目標(biāo)而言具有一定的局限性。

在不完全信息的分散決策場(chǎng)景下，本文以明確的經(jīng)濟(jì)收益為目標(biāo)，研究設(shè)計(jì)一種多輪升價(jià)拍賣機(jī)制來(lái)解決加工能力有限，但需要承諾交貨期的OAS問(wèn)題。在制造商和客戶分別以最大化自身凈收益為目標(biāo)的前提下，通過(guò)設(shè)計(jì)合適的拍賣機(jī)制優(yōu)化系統(tǒng)全局性能，使該分散系統(tǒng)決策結(jié)果盡可能接近完全信息下的系統(tǒng)全局最優(yōu)解。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

假設(shè)制造商面對(duì)n個(gè)客戶單件訂單加工需求，已知每個(gè)訂單i的加工時(shí)間為pi，交貨期為di，市場(chǎng)加工收益為ri。假設(shè)制造商加工能力描述為單機(jī)(single machine)，機(jī)器加工從0時(shí)刻開始有效，機(jī)器的加工時(shí)間被劃分為時(shí)間槽集合{1,2,…,T}，每個(gè)時(shí)間槽t表示時(shí)間段[t-1,t]，制造商在任意時(shí)間槽只能加工一件訂單，且訂單加工不允許中斷;已知每個(gè)機(jī)器時(shí)間槽t的加工成本為qt，它包括制造商為生產(chǎn)產(chǎn)品而發(fā)生的各項(xiàng)費(fèi)用，如員工工資、機(jī)器折舊費(fèi)、修理費(fèi)等，制造商只有在生產(chǎn)所得收益能夠抵補(bǔ)生產(chǎn)成本時(shí)才能確定盈利;制造商和客戶所組成的分散制造系統(tǒng)中信息是不完全的;制造商不了解市場(chǎng)加工訂單信息，包括訂單市場(chǎng)收益、加工時(shí)間需求和交貨期限承諾,同時(shí)客戶也不知道制造商的加工成本信息。

1.2 完全信息下的系統(tǒng)優(yōu)化決策問(wèn)題

將一個(gè)制造商和若干客戶組成的分散制造系統(tǒng)作為一個(gè)整體，考慮在完全信息下該制造系統(tǒng)的全局最優(yōu)解，以優(yōu)化系統(tǒng)凈收益為目標(biāo)，構(gòu)建該問(wèn)題的整數(shù)線性規(guī)劃模型。假設(shè)市場(chǎng)客戶訂單集合N={1,2,…,n}需要加工，制造商擁有連續(xù)機(jī)器時(shí)間槽集合Α={1,2,…,T};所有訂單i的加工時(shí)間pi和交貨期di為正整數(shù)。定義決策變量xit∈{0，1}，如果訂單i在機(jī)器上加工且在時(shí)刻t完工，則xit=1，否則xit=0，其中i=1,2,…,n，t=1,2,…,T。該問(wèn)題的整數(shù)線性規(guī)劃(Integer Linear Programming, ILP)模型如下:

s.t.

(1)

?t∈A;

(2)

txit≤di,?i∈N,?t∈A;

(3)

xit∈{0,1},?i∈N,?t∈A。

(4)

其中：約束(1)為訂單約束，表示制造商接受訂單，并且訂單只能被加工一次，或者制造商不接受訂單；約束(2)為機(jī)器約束，表示任意兩個(gè)訂單在機(jī)器上的加工時(shí)間不能重疊；約束(3)為訂單交貨期約束，表示被接受加工的訂單必須按期完工交貨。

假設(shè)每個(gè)機(jī)器時(shí)間槽的加工成本相同，即q1=q2=…=qT，就系統(tǒng)優(yōu)化決策問(wèn)題可以得到下列優(yōu)化性質(zhì)：

引理1存在一個(gè)最優(yōu)決策方案，訂單加工中間沒(méi)有空閑時(shí)間直至所有被加工的訂單完工。

引理1的結(jié)論是明顯的，證明省略。

引理2存在一個(gè)最優(yōu)決策方案，訂單按交貨期非減(Earliest Due Date First, EDD)規(guī)則排序。

證明假設(shè)存在最優(yōu)調(diào)度π，其中交貨期早的訂單后加工。在該調(diào)度里，必須至少有兩項(xiàng)相鄰的訂單j和k,訂單j在訂單k之前加工，使得dj>dk。假設(shè)訂單j在時(shí)間t開始加工，對(duì)訂單j和訂單k執(zhí)行所謂的鄰對(duì)交換得到新的調(diào)度π′。在調(diào)度規(guī)則π下，訂單j和k的完工時(shí)間分別為

t+pj≤dj,t+pj+pk≤dk。

在π′下，訂單j和k的完工時(shí)間分別為

t+pk+pj≤dk

此時(shí)，調(diào)度π′仍然滿足交貨期要求，并且在制造商機(jī)器時(shí)間槽成本相同的情況下，調(diào)度π′也是最優(yōu)調(diào)度。由此可見，存在一個(gè)最優(yōu)調(diào)度，其中交貨期早的訂單先加工。證畢。

利用引理1和引理2，可以將qt(t=1,2,…,T)相同時(shí)的ILP模型用動(dòng)態(tài)規(guī)劃(dynamic programming)方法求解。

不失一般性，假設(shè)集合N={1,2,…,n}中的訂單按交貨期從小到大編號(hào)。令f(i,t)為制造商僅使用1,…,t時(shí)間槽的加工能力來(lái)選擇性地加工訂單1,…,i時(shí)的最大系統(tǒng)凈收益。

邊界條件為f(0,t)=0,t≥0。

遞歸方程為

s.t.

pi≤t≤di

否則

最優(yōu)解為f(n,T)。

需要說(shuō)明的是，在訂單加工順序可以確定的情況下(可能不是EDD)，該動(dòng)態(tài)規(guī)劃算法仍然適用。例如，在下述拍賣機(jī)制中，由客戶投標(biāo)決定訂單加工順序時(shí)，制造商的競(jìng)勝標(biāo)問(wèn)題仍然可以采用該動(dòng)態(tài)規(guī)劃算法求解。

2 拍賣機(jī)制設(shè)計(jì)

制造商和客戶組成的兩階段分散決策場(chǎng)景中，客戶在已知制造商機(jī)器時(shí)間定價(jià)的情況下，通過(guò)投標(biāo)競(jìng)爭(zhēng)制造商機(jī)器加工時(shí)間來(lái)優(yōu)化自身凈收益；制造商在考慮客戶投標(biāo)的情況下，充分利用加工能力來(lái)優(yōu)化自身凈收益，為了實(shí)現(xiàn)制造商和客戶的雙贏，設(shè)計(jì)如下多輪升價(jià)拍賣機(jī)制。

2.1 拍賣流程

將拍賣應(yīng)用于調(diào)度問(wèn)題，即通過(guò)拍賣來(lái)分配制造商的生產(chǎn)能力，制造商即可描述成“拍賣者”，制造商的機(jī)器時(shí)間是“拍賣物品”，客戶是拍賣中的“競(jìng)標(biāo)者”。拍賣機(jī)制由制造商定價(jià)機(jī)制、客戶投標(biāo)機(jī)制和制造商競(jìng)勝標(biāo)機(jī)制組成。當(dāng)機(jī)器處于空閑時(shí)，制造商發(fā)出拍賣請(qǐng)求，客戶通過(guò)投標(biāo)來(lái)競(jìng)爭(zhēng)機(jī)器時(shí)間，制造商則根據(jù)投標(biāo)情況確定競(jìng)勝標(biāo)，形成臨時(shí)調(diào)度方案，制造商再根據(jù)臨時(shí)調(diào)度方案和投標(biāo)情況更新機(jī)器時(shí)間的價(jià)格，客戶根據(jù)更新的價(jià)格決定新一輪的投標(biāo)，如此反復(fù)，直至拍賣結(jié)束。拍賣的作用在于通過(guò)不斷更新物品價(jià)格來(lái)引導(dǎo)客戶需求，協(xié)調(diào)訂單在機(jī)器上的加工，以減少資源競(jìng)爭(zhēng)的沖突，提高系統(tǒng)資源配置的效率。拍賣的具體流程如下：

(1)給定訂單i(i=1,…,n)的加工時(shí)間pi、加工收益ri、交貨期di；給定制造商的機(jī)器時(shí)間槽t(t=1,…,T)的加工成本qt。

(2)制造商向客戶發(fā)出拍賣請(qǐng)求，并根據(jù)機(jī)器時(shí)間的加工成本、客戶投標(biāo)情況和臨時(shí)調(diào)度方案構(gòu)建拍賣時(shí)間段[u-p+1,u]的要價(jià)(Asking price)α(p,u)。

(3)客戶i(i=1,…,n)根據(jù)要價(jià)α(p,u)確定投標(biāo)Bi(pi,ui),bi，其中(pi,ui)表示客戶所競(jìng)標(biāo)的時(shí)間段[ui-pi+1,ui]，bi表示投標(biāo)價(jià)格，且投標(biāo)價(jià)格不得低于時(shí)間段[ui-pi+1,ui]的要價(jià)α(pi,ui)。

(4)制造商收集所有客戶的投標(biāo)求解競(jìng)勝標(biāo)問(wèn)題，形成臨時(shí)調(diào)度方案，并將中標(biāo)客戶的投標(biāo)價(jià)格bi直接賦給中標(biāo)價(jià)格β(pi,ui)，如果在步驟(2)中沒(méi)有一個(gè)客戶競(jìng)標(biāo)，則該臨時(shí)調(diào)度方案即為最終的調(diào)度方案，拍賣結(jié)束；否則返回步驟(1)。

2.2 自適應(yīng)定價(jià)策略

本文研究的單件訂單接受與加工調(diào)度分散決策問(wèn)題中的訂單加工是不允許中斷的，要求拍賣物品必須是連續(xù)機(jī)器時(shí)段的組合，這不同于常見的單一物品拍賣[11-12]，也不同于拍賣物品可以任意搭配的組合拍賣[13-15]。因此，設(shè)計(jì)基于連續(xù)時(shí)段的自適應(yīng)定價(jià)策略，不僅可以大大緩解資源供求沖突問(wèn)題，還可以指導(dǎo)拍賣的動(dòng)態(tài)調(diào)整，提高拍賣的效率。具體規(guī)則如下：

2.3 投標(biāo)規(guī)則

本文采用占優(yōu)投標(biāo)策略，即無(wú)論其他競(jìng)爭(zhēng)對(duì)手采用何種策略，該策略對(duì)投標(biāo)者都是最優(yōu)的。投標(biāo)分為兩部分，客戶不僅要決策出競(jìng)標(biāo)的時(shí)間段，還要給出投標(biāo)價(jià)格，投標(biāo)以Bi(pi,ui),bi的形式給出，其中i=1,…,n。在2.1節(jié)的拍賣步驟(3)中，如果客戶中標(biāo)，則仍以同樣的標(biāo)參與下一輪競(jìng)爭(zhēng);如果客戶未中標(biāo)，則根據(jù)已更新的要價(jià)和投標(biāo)規(guī)則給出新的投標(biāo)，具體投標(biāo)規(guī)則如下：

客戶i以最大化自身凈收益為目標(biāo)，在盡可能保證中標(biāo)的前提下，選出有最大競(jìng)爭(zhēng)優(yōu)勢(shì)的競(jìng)標(biāo)時(shí)間段(pi,ui)，即(pi,ui)=argmax{ri-α(pi,pi),ri-α(pi,pi+1),…,ri-α(pi,di)}。

客戶i的投標(biāo)價(jià)格bi是在要價(jià)的基礎(chǔ)上，根據(jù)自身的提價(jià)空間給出一定的加價(jià)，這個(gè)加價(jià)又稱作競(jìng)價(jià)階梯，記作λi。競(jìng)價(jià)階梯可以由拍賣者決定，也可以由競(jìng)拍者決定，可以是固定的，也可以是不固定的。在現(xiàn)實(shí)中，每個(gè)物品的效用對(duì)不同的消費(fèi)者來(lái)說(shuō)是不同的，為了能夠?qū)⒖蛻舻恼鎸?shí)偏好信息反饋給制造商，以協(xié)調(diào)客戶需求與制造商的生產(chǎn)能力，本文的競(jìng)價(jià)階梯由客戶(競(jìng)拍者)根據(jù)自身競(jìng)爭(zhēng)能力決定，令λi=ρ(ri-α(pi,ui))，ρ∈(0，1)。

該占優(yōu)投標(biāo)策略可以確保客戶中標(biāo)的機(jī)器加工時(shí)間給其帶來(lái)正的收益，并且是最大的凈收益，這樣的拍賣機(jī)制更易于得到客戶的青睞。

2.4 競(jìng)勝標(biāo)確定問(wèn)題

制造商競(jìng)勝標(biāo)問(wèn)題是在客戶的投標(biāo)約束下，以最大化制造商凈收益為目標(biāo)，進(jìn)行訂單接受與加工調(diào)度決策。初始化收到的投標(biāo)Bi(pi,ui),bi(i=1,…,n)，不失一般性，假設(shè)投標(biāo)Bi按ui升序編號(hào)。令f(i,t)為制造商僅使用1,…,t時(shí)間槽的加工能力選擇性地加工投標(biāo)B1,…,Bi所能獲得的最大凈收益。競(jìng)勝標(biāo)問(wèn)題的動(dòng)態(tài)規(guī)劃模型如下：

邊界條件為f(0,t)=0,t≥0。

遞歸方程為

s.t.

ui=t

否則

最優(yōu)解為f(n,T)。

3 計(jì)算實(shí)驗(yàn)及分析

本文通過(guò)IBM ILOG CPLEX 12.3和Visual C++編程實(shí)現(xiàn)上述模型和算法，通過(guò)廣泛的問(wèn)題實(shí)例分析討論理論結(jié)果的管理啟示。具體的，計(jì)算實(shí)驗(yàn)主要分析討論拍賣機(jī)制的價(jià)值和性能，包括該拍賣機(jī)制對(duì)分散系統(tǒng)提高收益的價(jià)值，分散決策相對(duì)于系統(tǒng)全局集中的代價(jià)，以及各種參數(shù)的變化對(duì)拍賣性能的影響。

3.1 算例

已知該算例包括5個(gè)客戶單件訂單加工需求，具體的訂單信息如表1所示，制造商的加工能力和加工成本信息如表2所示。拍賣由制造商定價(jià)、客戶投標(biāo)和制造商競(jìng)勝標(biāo)組成，具體拍賣步驟如下：

(1)第1輪 首先，已知制造商機(jī)器時(shí)間槽成本qt，計(jì)算機(jī)器時(shí)間槽報(bào)價(jià)α(p,u)，如表3所示；然后，根據(jù)計(jì)算機(jī)器時(shí)間槽報(bào)價(jià)α(p,u)，客戶進(jìn)行投標(biāo)，如表4所示；最后，制造商根據(jù)上一步的投標(biāo)計(jì)算競(jìng)勝標(biāo)，得出投標(biāo)B3(4,7,53)中標(biāo)，制造商收益為29，系統(tǒng)收益為145。令β(4,7)=53，μ=1。

ZHANG Heng, WU Lin-lin, LI Shi-jie, KUANG Ye, MA Xing-hong

(2)第2輪 根據(jù)2.2節(jié)定價(jià)策略重新計(jì)算α(p,u)，如表5所示；緊接著，客戶根據(jù)α(p,u)再次進(jìn)行投標(biāo)，如表6所示；根據(jù)第2輪投標(biāo)計(jì)算競(jìng)勝標(biāo)，得出投標(biāo)B1(2,3,24)和B5(10,13,116.8)中標(biāo)，制造商收益為57.8，系統(tǒng)收益為164。令β(2,3)=24，β(10,13)=116.8，μ=0.5。

(3)第3輪 投標(biāo)B1(2,3,24)和B3(4,7,128)中標(biāo)，制造商收益為111，系統(tǒng)收益為180。計(jì)算方法和第2輪相同，此處省略。

(4)第4輪 投標(biāo)B1(2,3,24)、B3(4,7,128)和B4(5,12,46)中標(biāo)，制造商收益為119，系統(tǒng)收益為220。計(jì)算方法和第2輪相同，此處省略。

(5)第5輪 投標(biāo)B1(2,3,24)和B5(10,13,181.4)中標(biāo)，制造商收益為122.4，系統(tǒng)收益為164。計(jì)算方法和第2輪相同，此處省略。

此時(shí)，沒(méi)有新的投標(biāo)出現(xiàn)，拍賣結(jié)束,最終調(diào)度結(jié)果為從時(shí)間2開始加工訂單1，從時(shí)間4開始加工訂單5。

表1 訂單加工信息

表2 制造商機(jī)器時(shí)間槽成本

表3 第1輪機(jī)器時(shí)間槽報(bào)價(jià)α(p,u)

表4 第1輪客戶投標(biāo)Bi

表5 第2輪機(jī)器時(shí)間槽報(bào)價(jià)α(p,u)

表6 第2輪客戶投標(biāo)Bi

3.2 數(shù)據(jù)生成

本文分別對(duì)訂單個(gè)數(shù)n=10，20，40,80的4種情況隨機(jī)生成問(wèn)題實(shí)例，生成的問(wèn)題實(shí)例規(guī)則如下：

(2)制造商的要價(jià)根據(jù)3.2節(jié)的自適應(yīng)定價(jià)規(guī)則確定，價(jià)格增量系數(shù)μ∈{0.1,0.5,1.0}，競(jìng)價(jià)階梯系數(shù)取ρ=0.2。

(3)客戶投標(biāo)價(jià)格按照3.3節(jié)的投標(biāo)規(guī)則確定。根據(jù)以上參數(shù)設(shè)計(jì)可以形成108個(gè)組合，對(duì)于每種組合分別生成10個(gè)問(wèn)題實(shí)例。

3.3 拍賣的價(jià)值

本文設(shè)計(jì)的拍賣機(jī)制能夠有效地解決分散決策場(chǎng)景下的OAS問(wèn)題，在信息不完全的情況下，通過(guò)自適應(yīng)定價(jià)規(guī)則引導(dǎo)拍賣的動(dòng)向，實(shí)現(xiàn)系統(tǒng)資源的有效配置，提高系統(tǒng)全局收益。實(shí)驗(yàn)將拍賣機(jī)制與先來(lái)先服務(wù)(First Come First Served，F(xiàn)CFS)訂單加工策略進(jìn)行對(duì)比，以分析拍賣機(jī)制對(duì)制造商和客戶收益的影響。

假設(shè)在信息不完全的分散決策場(chǎng)景下，制造商按照訂單到達(dá)順序，依次選擇并接受可以按期不虧本加工的訂單，并以高于加工成本的價(jià)格向客戶收取一定的訂單加工費(fèi)用，最常見的制造商定價(jià)方式是線性定價(jià)(Linear Pricing, LP)，制造商獲得的加工收益為所接受訂單的總收入減去總加工成本?；谥圃焐叹€性定價(jià)的先來(lái)先服務(wù)(LP-FCFS)機(jī)制既能保證公平性又簡(jiǎn)單易行，因此被工業(yè)界廣泛使用。但是，由于制造商和客戶之間信息的不完全，制造商和客戶都無(wú)法做出有利于各人和整體利益的決策。

表7 拍賣機(jī)制與LP-FCFS(δ=1.5)機(jī)制的制造商收益和系統(tǒng)收益

表8 拍賣機(jī)制與LP-FCFS(δ=3)機(jī)制的制造商收益和系統(tǒng)收益

3.4 拍賣的性能

為了揭示拍賣的性能，將拍賣機(jī)制與2.2節(jié)完全信息下的集中系統(tǒng)優(yōu)化策略進(jìn)行對(duì)比，計(jì)算分散決策代價(jià)(POA)，即拍賣機(jī)制下的系統(tǒng)收益與集中優(yōu)化的系統(tǒng)收益的比值，結(jié)果如表9所示。該拍賣機(jī)制總體表現(xiàn)良好，平均比值達(dá)到92.7%。另外，各個(gè)參數(shù)的變化對(duì)拍賣性能的具體影響如下：代表訂單個(gè)數(shù)、制造商加工能力、訂單交貨期和拍賣自適應(yīng)定價(jià)幅度的4個(gè)參數(shù)對(duì)拍賣性能均有明顯影響，其中，隨著訂單個(gè)數(shù)n、訂單加工能力T和訂單交貨期τ的增加，拍賣性能均明顯提升；隨著拍賣自適應(yīng)定價(jià)參數(shù)μ的增加，拍賣性能明顯下降;自適應(yīng)定價(jià)系數(shù)μ對(duì)資源的需求感知越敏感，拍賣性能越好。

從表9還可以看出,該拍賣機(jī)制的計(jì)算性能良好，平均經(jīng)過(guò)12.7輪，拍賣結(jié)束。其中，訂單個(gè)數(shù)和自適應(yīng)定價(jià)系數(shù)對(duì)拍賣輪數(shù)影響較明顯，隨著訂單個(gè)數(shù)的增加和自適應(yīng)定價(jià)系數(shù)的減少，拍賣輪數(shù)明顯增加；制造商加工能力和訂單交貨期對(duì)拍賣輪數(shù)的影響不是很明顯。

綜上所述，拍賣機(jī)制總體性能良好，而且資源越緊缺，拍賣機(jī)制的優(yōu)越性越明顯，拍賣機(jī)制能通過(guò)動(dòng)態(tài)價(jià)格引導(dǎo)更明顯地分散資源需求，在有限時(shí)間內(nèi)均衡配置稀缺資源。

表9 分散決策代價(jià)(POA)和拍賣輪數(shù)

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

本文根據(jù)分散決策下OAS問(wèn)題的特點(diǎn)，設(shè)計(jì)多輪升價(jià)拍賣機(jī)制。制造商可以在不了解資源對(duì)客戶的價(jià)值和具體使用細(xì)節(jié)的情況下將資源有效地分配出去，解決了分散決策場(chǎng)景下的信息不完全問(wèn)題；該拍賣機(jī)制可以匿名操作，分散系統(tǒng)中的客戶只需要根據(jù)自己的目標(biāo)和約束進(jìn)行占優(yōu)投標(biāo)決策，保證了客戶估價(jià)的真實(shí)性，也易于被客戶接受；該拍賣機(jī)制可以根據(jù)供求關(guān)系動(dòng)態(tài)調(diào)整定價(jià)以達(dá)到競(jìng)爭(zhēng)均衡；最后通過(guò)數(shù)據(jù)實(shí)驗(yàn)表明，該拍賣機(jī)制對(duì)解決OAS分散決策問(wèn)題具有良好的效果。

本文設(shè)計(jì)拍賣機(jī)制解決單機(jī)環(huán)境下的OAS問(wèn)題，后續(xù)研究可以擴(kuò)展到現(xiàn)實(shí)中常見的并行機(jī)OAS問(wèn)題，并針對(duì)具有NP難屬性的并行機(jī)OAS問(wèn)題設(shè)計(jì)基于啟發(fā)式規(guī)則的競(jìng)勝標(biāo)確定算法以提高拍賣機(jī)制的計(jì)算效率和實(shí)際應(yīng)用性。