基于拍賣的訂單接受與加工調(diào)度分散決策問題

朱倩倩，王秀利，耿蘇杰

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

0 引言

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

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

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

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

1 問題描述與建模

1.1 問題描述

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

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

將一個制造商和若干客戶組成的分散制造系統(tǒng)作為一個整體，考慮在完全信息下該制造系統(tǒng)的全局最優(yōu)解，以優(yōu)化系統(tǒng)凈收益為目標，構(gòu)建該問題的整數(shù)線性規(guī)劃模型。假設(shè)市場客戶訂單集合N={1,2,…,n}需要加工，制造商擁有連續(xù)機器時間槽集合Α={1,2,…,T};所有訂單i的加工時間pi和交貨期di為正整數(shù)。定義決策變量xit∈{0，1}，如果訂單i在機器上加工且在時刻t完工，則xit=1，否則xit=0，其中i=1,2,…,n，t=1,2,…,T。該問題的整數(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)為機器約束，表示任意兩個訂單在機器上的加工時間不能重疊；約束(3)為訂單交貨期約束，表示被接受加工的訂單必須按期完工交貨。

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

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

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

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

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

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

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

t+pk+pj≤dk

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

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

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

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

遞歸方程為

s.t.

pi≤t≤di

否則

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

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

2 拍賣機制設(shè)計

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

2.1 拍賣流程

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

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

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

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

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

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

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

2.3 投標規(guī)則

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

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

客戶i的投標價格bi是在要價的基礎(chǔ)上，根據(jù)自身的提價空間給出一定的加價，這個加價又稱作競價階梯，記作λi。競價階梯可以由拍賣者決定，也可以由競拍者決定，可以是固定的，也可以是不固定的。在現(xiàn)實中，每個物品的效用對不同的消費者來說是不同的，為了能夠?qū)⒖蛻舻恼鎸嵠眯畔⒎答伣o制造商，以協(xié)調(diào)客戶需求與制造商的生產(chǎn)能力，本文的競價階梯由客戶(競拍者)根據(jù)自身競爭能力決定，令λi=ρ(ri-α(pi,ui))，ρ∈(0，1)。

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

2.4 競勝標確定問題

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

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

遞歸方程為

s.t.

ui=t

否則

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

3 計算實驗及分析

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

3.1 算例

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

(1)第1輪 首先，已知制造商機器時間槽成本qt，計算機器時間槽報價α(p,u)，如表3所示；然后，根據(jù)計算機器時間槽報價α(p,u)，客戶進行投標，如表4所示；最后，制造商根據(jù)上一步的投標計算競勝標，得出投標B3(4,7,53)中標，制造商收益為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é)定價策略重新計算α(p,u)，如表5所示；緊接著，客戶根據(jù)α(p,u)再次進行投標，如表6所示；根據(jù)第2輪投標計算競勝標，得出投標B1(2,3,24)和B5(10,13,116.8)中標，制造商收益為57.8，系統(tǒng)收益為164。令β(2,3)=24，β(10,13)=116.8，μ=0.5。

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

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

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

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

表1 訂單加工信息

表2 制造商機器時間槽成本

表3 第1輪機器時間槽報價α(p,u)

表4 第1輪客戶投標Bi

表5 第2輪機器時間槽報價α(p,u)

表6 第2輪客戶投標Bi

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

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

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

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

3.3 拍賣的價值

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

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

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

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

3.4 拍賣的性能

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

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

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

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

4 結(jié)束語

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

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