帶工期指派的產(chǎn)品服務(wù)系統(tǒng)訂單隨機調(diào)度問題研究

張 楊，但 斌，高華麗

(1.重慶大學(xué)經(jīng)濟與工商管理學(xué)院，重慶 400044；2.重慶大學(xué)現(xiàn)代物流重慶市重點實驗室，重慶 400030；3.西南政法大學(xué)管理學(xué)院，重慶 401120)

1 引言

隨著市場競爭日益激烈和產(chǎn)品利潤空間不斷壓縮，傳統(tǒng)制造業(yè)開始由生產(chǎn)型制造向服務(wù)型制造轉(zhuǎn)變。2016年7月，國家工信部、發(fā)改委、中國工程院聯(lián)合印發(fā)了《發(fā)展服務(wù)型制造專項行動指南》[1]，指出：“(制造企業(yè))從單純出售產(chǎn)品向出售‘產(chǎn)品+服務(wù)’轉(zhuǎn)變，有利于延伸和提升價值鏈，提高全要素生產(chǎn)率、產(chǎn)品附加值和市場占有率”。這種“產(chǎn)品+服務(wù)”的整體解決方案又被稱為產(chǎn)品服務(wù)系統(tǒng)(Product service system，PSS)[2]。為了按期交付產(chǎn)品與服務(wù)，服務(wù)型制造企業(yè)需要為客戶的PSS訂單制定有效的調(diào)度方案并指派合理的工期，否則就會因訂單延遲交付而受到誤工懲罰，甚至導(dǎo)致客戶流失[3]。然而，在PSS的交付過程中，生產(chǎn)時間與服務(wù)時間可能具有隨機性。例如，電梯供貨與安裝合同常常包含定制化需求，無法得到電梯生產(chǎn)與安裝過程中每一道工序的精確時間，而只能結(jié)合現(xiàn)場操作和根據(jù)以往類似產(chǎn)品的生產(chǎn)與安裝經(jīng)驗進(jìn)行估計。這種隨機性使得PSS訂單調(diào)度與工期指派問題變得更為復(fù)雜。因此，在生產(chǎn)與服務(wù)時間均具有隨機性的條件下，如何聯(lián)合制定有效的PSS訂單調(diào)度與工期指派策略是服務(wù)型制造企業(yè)亟待解決的現(xiàn)實問題。

目前，在PSS運營管理領(lǐng)域，尚缺乏針對PSS訂單調(diào)度或工期指派問題的研究文獻(xiàn)，而現(xiàn)有的PSS運營管理的定量研究主要有兩類：企業(yè)宏觀層面上的PSS運營策略制定和微觀層面上的生產(chǎn)與服務(wù)任務(wù)運作計劃。大多數(shù)文獻(xiàn)從宏觀角度探討了如何制定企業(yè)的PSS運營策略，如產(chǎn)品和服務(wù)的定價策略、契約機制設(shè)計和能力配置等等。例如，Tsay和Agrawal[4]考慮由一個制造商和兩個零售商組成的產(chǎn)品服務(wù)供應(yīng)鏈，研究了零售商競爭環(huán)境下產(chǎn)品價格和服務(wù)水平的動態(tài)決策問題；Lee等[5]通過研究傳統(tǒng)渠道與服務(wù)化渠道存在競爭時制造企業(yè)的最優(yōu)定價與質(zhì)量決策問題，發(fā)現(xiàn)當(dāng)產(chǎn)品對服務(wù)的依賴性較高或渠道競爭較激烈時，制造企業(yè)實施服務(wù)化更有利；Xie Wenming等[6]在信息不對稱條件下對比分析了產(chǎn)品服務(wù)供應(yīng)鏈的三種契約設(shè)計，結(jié)果表明契約實施的有效性很大程度上受供應(yīng)鏈權(quán)力結(jié)構(gòu)與成本信息類型的影響；劉宇熹和謝家平[7]針對租賃PSS研究了節(jié)約共享契約對協(xié)調(diào)再制造企業(yè)與客戶利益的重要作用；Xie Wenming等[8]以確保供應(yīng)鏈中制造商和服務(wù)商間的充分信息共享為目標(biāo)，探討了如何有效規(guī)劃產(chǎn)能和實現(xiàn)多渠道分銷；Li Gang等[9]分析了零售商自建與外購服務(wù)能力決策對產(chǎn)品服務(wù)供應(yīng)鏈成員績效的影響，發(fā)現(xiàn)服務(wù)外包能夠提高零售商的服務(wù)水平并降低制造商的批發(fā)價格；姚樹俊和陳菊紅[10]考慮由兩個制造商和一個零售商組成的產(chǎn)品服務(wù)供應(yīng)鏈，以制造商提供服務(wù)為視角，研究了不同權(quán)利結(jié)構(gòu)下制造商的服務(wù)能力決策問題。以上文獻(xiàn)側(cè)重于如何通過增加企業(yè)或供應(yīng)鏈的收益來提高利潤，因此未對成本控制策略作深入探討。僅有少數(shù)文獻(xiàn)從企業(yè)執(zhí)行層面對PSS運作過程的最優(yōu)控制策略進(jìn)行了研究。例如，Li Na和Jiang Zhibin[11]針對帶有額外服務(wù)能力和不耐煩顧客的生產(chǎn)服務(wù)系統(tǒng)構(gòu)建了分塊Markov最優(yōu)控制模型；Wang Kangzhou等[12]針對同時銷售產(chǎn)品和PSS的服務(wù)型制造企業(yè)提出了最優(yōu)生產(chǎn)與需求準(zhǔn)入控制策略。但此類文獻(xiàn)均假設(shè)對PSS需求按照簡單的先來先服務(wù)規(guī)則進(jìn)行調(diào)度，未對更為現(xiàn)實且有效的復(fù)雜調(diào)度策略作深入探討和分析，而這正是本文的主要研究內(nèi)容。

另一個與本文相關(guān)的研究領(lǐng)域是調(diào)度管理。早期，學(xué)者們主要針對生產(chǎn)調(diào)度[13-15]或服務(wù)調(diào)度[16-17]問題開展研究；后來，為了進(jìn)一步提升MTO(make to order)型制造企業(yè)的運營效率和降低其運營成本，一些學(xué)者開始研究產(chǎn)品生產(chǎn)與配送服務(wù)的聯(lián)合調(diào)度問題。例如，Garcia和Lozano[18]考慮帶有時間窗的生產(chǎn)與配送調(diào)度問題，以最大化訂單利潤為目標(biāo)構(gòu)建了整數(shù)規(guī)劃模型，并提出求解問題的禁忌搜索算法；Li等[19]針對消費類電子產(chǎn)品供應(yīng)鏈研究了裝配生產(chǎn)與空運的協(xié)同調(diào)度問題；Low等[20]以最小化最大完工時間為目標(biāo)構(gòu)建了時間窗約束下的生產(chǎn)與配送調(diào)度模型，并基于遺傳算法設(shè)計了求解問題的啟發(fā)式算法；馬士華和呂飛[21]在隨機需求條件下構(gòu)建了基于Supply Hub的供應(yīng)鏈生產(chǎn)與配送協(xié)同決策模型。上述研究中，產(chǎn)品和配送服務(wù)之間不具有嚴(yán)格的匹配與集成關(guān)系：同一客戶訂單的產(chǎn)品在數(shù)量較多時可由不同運輸工具分批或分時段配送，同一運輸工具也可以同時為多個客戶提供配送服務(wù)，并且配送所需時間與選擇的運輸工具或運輸路線相關(guān)，而非與產(chǎn)品本身相關(guān)。而PSS訂單中的產(chǎn)品與服務(wù)具有高度集成性和匹配性：產(chǎn)品與服務(wù)往往是一一對應(yīng)的關(guān)系，不同類型的產(chǎn)品對應(yīng)的服務(wù)在服務(wù)方式和服務(wù)時間等方面不一致，且服務(wù)時間通常與產(chǎn)品的復(fù)雜性或客戶需求相關(guān)。例如，不同型號電梯的生產(chǎn)與安裝時間一般不同，且安裝時間與客戶的戶型和層高等要求有關(guān)；而在電梯安裝過程中，同一電梯安裝隊在同一時間只能為一臺電梯提供安裝服務(wù)。因此，以往針對生產(chǎn)與配送服務(wù)的調(diào)度方案不能適用于PSS訂單調(diào)度問題，需要基于PSS的運作特點研究新的生產(chǎn)與服務(wù)集成調(diào)度策略。

鑒于此，本文考慮生產(chǎn)時間與服務(wù)時間的隨機性影響，以最小化訂單提前、誤工和工期指派費用的期望總和為目標(biāo)研究服務(wù)型制造企業(yè)的PSS訂單調(diào)度與工期指派聯(lián)合決策問題，并探討問題的解決方案，以期為服務(wù)型制造企業(yè)的PSS訂單調(diào)度管理提供有價值的啟示。

2 問題描述與基本模型

2.1 問題描述與假設(shè)

考慮由一個制造工廠和n個區(qū)域服務(wù)中心組成的服務(wù)型制造企業(yè)，如圖1所示。企業(yè)通過區(qū)域服務(wù)中心收集該地區(qū)客戶的PSS訂單需求，各訂單所需產(chǎn)品由制造工廠集中進(jìn)行生產(chǎn)，產(chǎn)品完工后運送到客戶處并由相應(yīng)的區(qū)域服務(wù)中心提供所需服務(wù)，從而最終完成PSS的交付。上述服務(wù)型制造企業(yè)在現(xiàn)實中很常見，如許多品牌電梯廠商在中國建立了電梯制造基地并在各省區(qū)設(shè)立分公司(負(fù)責(zé)該省區(qū)的電梯銷售、安裝和維保等業(yè)務(wù))。在計劃期的初始時刻，區(qū)域服務(wù)中心i(i=1,2,…,n)收到一個PSS訂單(記為訂單oi)，其中訂單oi由一單位產(chǎn)品與相應(yīng)服務(wù)組成(如一臺電梯的生產(chǎn)與安裝合同)。各區(qū)域服務(wù)中心的訂單構(gòu)成了企業(yè)需要處理的一組確定訂單集合O={o1,o2,…,on}。企業(yè)需要為每個訂單指派工期并制定訂單調(diào)度計劃。其中訂單oi的工期由兩部分組成：產(chǎn)品工期dpi(同時也是服務(wù)交付期的開始時間)和服務(wù)交付期長度lsi(即服務(wù)交付期的截止時間dsi與產(chǎn)品工期dpi的差值，lsi=dsi-dpi)。例如，電梯設(shè)備生產(chǎn)安裝合同通常會在條款中分別對電梯的交貨期與安裝工期進(jìn)行規(guī)定。為了制定最優(yōu)的訂單調(diào)度與工期計劃，企業(yè)需考慮在訂單交付過程中可能產(chǎn)生的各項生產(chǎn)與服務(wù)費用。如果訂單oi的生產(chǎn)在服務(wù)交付期的開始時間之前完工，產(chǎn)品將在庫存中等待，每單位時間產(chǎn)生的庫存費用為hi；如果訂單oi的生產(chǎn)誤工或服務(wù)延遲交付，則企業(yè)每超期一單位時間需支付給客戶的誤工費用為bi；此外，由于較長的工期可能會使企業(yè)喪失訂單，進(jìn)而損害企業(yè)的競爭力[22]，故參照以往有關(guān)產(chǎn)品訂單工期指派問題的研究[13]，本文考慮訂單oi每單位時間的工期時長會產(chǎn)生潛在的懲罰費用ai。由于各訂單的收益在最初與客戶談判時就已確定，不會隨訂單調(diào)度計劃而改變，因此為了實現(xiàn)利潤最大化的目標(biāo)，管理者需要聯(lián)合決策訂單序列和工期以使所有訂單的期望費用總和最小。

圖1 服務(wù)型制造企業(yè)運作示意圖

為了方便研究，本文假設(shè)：制造工廠在同一時刻只能生產(chǎn)一個PSS訂單的產(chǎn)品；各服務(wù)中心在產(chǎn)品到貨后能夠立即開始提供服務(wù)；生產(chǎn)時間和服務(wù)時間均是隨機的和相互獨立的，且服從已知正態(tài)分布；準(zhǔn)備時間和運輸時間包含在生產(chǎn)時間中；生產(chǎn)任務(wù)和服務(wù)任務(wù)一旦開始不允許中斷。

2.2 基本模型

企業(yè)在決策前已知的信息包含：訂單規(guī)模，各訂單所需的生產(chǎn)時間與服務(wù)時間以及單位時間的提前、誤工與工期指派費用等。據(jù)此，定義參量如下：

n：訂單規(guī)模；

h[i]：訂單[i]的單位時間提前費用；

b[i]：訂單[i]的單位時間誤工費用；

a[i]：訂單[i]的單位時間工期指派費用；

企業(yè)直接決策的是訂單序列以及產(chǎn)品與服務(wù)的工期，間接決策的是訂單中產(chǎn)品與服務(wù)的完工時間。據(jù)此，定義決策變量如下：

seq：PSS訂單序列；

dp[i]：訂單[i]的產(chǎn)品工期，也是服務(wù)交付期的開始時間；

ds[i]：訂單[i]的服務(wù)交付期的截止時間；

ls[i]：訂單[i]的服務(wù)交付期長度，ls[i]=ds[i]-dp[i]；

ctp[i]：訂單[i]的產(chǎn)品完工時間；

cts[i]：訂單[i]的服務(wù)完工時間；

其中，[i](i=1,2,…,n)表示訂單序列seq中第i個位置的訂單編號。此外，全文中令φ(·)和Φ(·)分別表示標(biāo)準(zhǔn)正態(tài)分布的概率密度函數(shù)和分布函數(shù)，并定義函數(shù)Ψ(x)=φ(x)-x[1-Φ(x)]。

根據(jù)問題描述和假設(shè)，給定任意PSS訂單序列seq，如果該序列的第一個訂單不在零時刻開始生產(chǎn)，或者在兩個相鄰的訂單之間插入空閑時間，或者在同一訂單的生產(chǎn)階段和服務(wù)階段之間插入空閑時間，都會推遲PSS的交付時間并產(chǎn)生更多工期指派費用，同時不會減少其它費用。因此問題的最優(yōu)調(diào)度一定是非延遲調(diào)度，且第一個訂單一定在零時刻開始生產(chǎn)?；谝陨戏治觯宰钚』谕傎M用為目標(biāo)，建立優(yōu)化模型如下：

minC(seq,dp,ls)=

(1)

(2)

cts[i]=max{ctp[i],dp[i]}+st[i],i=1,2,…,n

(3)

其中，dp=(dp[1],dp[2],…,dp[n])表示產(chǎn)品工期向量，ls=(ls[1],ls[2],…,ls[n])表示服務(wù)交付期長度向量。式表示目標(biāo)為最小化產(chǎn)品的期望提前費用、產(chǎn)品與服務(wù)的期望誤工費用以及工期指派費用之和；式和分別定義了訂單[i]的產(chǎn)品和服務(wù)的完工時間。

3 問題求解

在現(xiàn)實中，服務(wù)型制造企業(yè)通常先通過調(diào)度訂單確定訂單序列，再根據(jù)訂單序列以及訂單的生產(chǎn)時間和服務(wù)時間等信息對訂單的完工時間進(jìn)行估計，最后向客戶承諾一個合理的工期。如果先指派工期后確定序列，由于缺少訂單的排序信息，容易造成承諾的工期過短或過長。當(dāng)工期過短時，由于生產(chǎn)時間和服務(wù)時間具有隨機性，容易發(fā)生誤工并產(chǎn)生誤工成本；而工期過長可能不被客戶接受甚至導(dǎo)致客戶流失，這時企業(yè)會被迫提供價格折扣來爭取訂單，由此產(chǎn)生工期指派成本。因此，為了更好地制定工期計劃和優(yōu)化運營成本，企業(yè)需要先確定訂單序列再指派工期。但在學(xué)術(shù)研究中，通常采用逆序求解的方法，即先假設(shè)給定任意訂單序列，求得該序列下的最優(yōu)工期，然后再返回決策最優(yōu)訂單序列。這也是求解帶工期指派的調(diào)度問題常用的方法。

3.1 工期指派方法

C(seq,dp,ls)

(4)

式(4)仍然比較復(fù)雜，難以直接用于問題的分析和求解。為克服這一困難，本文提出一種可以得到近似最優(yōu)解的方法，該方法的主要步驟如下：

步驟1：確定原目標(biāo)函數(shù)的上界和下界，并用上下界的凸組合來近似原目標(biāo)函數(shù)；

步驟 2：在給定任意訂單調(diào)度序列的條件下，計算近似目標(biāo)函數(shù)的最優(yōu)工期和最優(yōu)值；

步驟3：基于近似目標(biāo)函數(shù)的最優(yōu)工期和最優(yōu)值，設(shè)計啟發(fā)式算法尋找近似最優(yōu)調(diào)度解。

按照上述方法，首先推導(dǎo)式(4)的近似值。記V[i]Φ(θ)[Φ(κ[i](θ))-1]dθ。由積分中值定理可知，存在ξ[i]∈(y[i],z[i])使得

V[i]=Φ(ξ[i])[Φ(κ[i](ξ[i]))-1](z[i]-y[i])

又由于0<Φ(ξ[i]),Φ(κ[i](ξ[i]))<1并且z[i]>y[i]，因此有

-(z[i]-y[i])

由上式和式(4)，C(seq,dp,ls)的近似值可表示為

(5)

其中τ[i]〗∈(0,1)。

定理1記

(6)

(7)

聯(lián)立式(6)和式(7)可得

(8)

以及

(9)

定理2記

以及

δ[i]

(10)

(11)

(12)

證明 對任意的i,j=1,2,…,n且i≠j，由式(6)和(7)得

λ1,[i]

λ2,[i]

以及

(13)

其中，

φ[i]

3.2 啟發(fā)式算法設(shè)計

由上式和式(12)可得

其中η[k]a[k]+δ[k]/3。下面的定理給出了能夠最小化的近似最優(yōu)排序規(guī)則。

定理3根據(jù)加權(quán)最短平均生產(chǎn)時間(weighted shortest average production time，WSAPT)排序規(guī)則：

可以得到問題

的近似最優(yōu)調(diào)度解。

證明 令seq表示任意一個非WSAPT規(guī)則序列，則必存在兩個相鄰的訂單of和og(假設(shè)分別占據(jù)seq中[]和[+1]的位置)滿足

令seq′表示交換這兩個訂單位置得到新序列，有

以及

進(jìn)而得到

上式表明交換訂單of和og的位置可以得到更優(yōu)的序列。證畢。

根據(jù)定理3，利用WSAPT規(guī)則對原目標(biāo)函數(shù)進(jìn)行優(yōu)化，可得到啟發(fā)式算法步驟如下：

算法WSAPT

步驟1：根據(jù)WSAPT排序規(guī)則輸出調(diào)度解seq*=([1],[2],…,[n])；

步驟2：根據(jù)式(13)，求解約束優(yōu)化問題

其中τ(ζ)=(τ[1](ζ),τ[2](ζ),…,τ[n](ζ))；

上述算法中，步驟1可利用快速排序?qū)崿F(xiàn)，故計算復(fù)雜度為O(nlogn)；步驟2和3的目的是為求解最優(yōu)序列下原目標(biāo)函數(shù)的最優(yōu)工期和最優(yōu)值，其中問題(14)的尋優(yōu)速度由具體的優(yōu)化算法所決定，一般可采用已有的且比較成熟的約束優(yōu)化方法，如有效集(Active-set)算法和SQP(Sequential quadratic programming)算法等等。需要說明的是，要得到序列seq*下原目標(biāo)函數(shù)的最優(yōu)值，步驟2實際應(yīng)當(dāng)執(zhí)行的操作是：根據(jù)式(4)，求解如下的約束優(yōu)化問題：

(dp*,ls*)=argminC((dp,ls|seq*)

s.t.dp[i],ls[i]>0,i=1,2,…,n

(15)

然而，該問題中含有2n個決策變量，當(dāng)訂單規(guī)模稍大時(如n≥7)，問題(15)會非常耗費時間。因此，考慮在算法WSAPT中以犧牲一定的求解精度為代價，將2n維優(yōu)化問題降為一維優(yōu)化問題以換取時間效率。

由于WSAPT規(guī)則是基于近似目標(biāo)函數(shù)上界得到的調(diào)度規(guī)則，通過WSAPT算法得到的調(diào)度解可能會與原目標(biāo)函數(shù)的最優(yōu)調(diào)度解存在較大偏離，因此需要引入優(yōu)化機制進(jìn)一步提高解的質(zhì)量。本文的改進(jìn)方法為：首先利用WSAPT規(guī)則產(chǎn)生初始解，然后對該初始解執(zhí)行插入鄰域局部搜索，最后選取目標(biāo)值最小的解作為新的初始解。據(jù)此，提出改進(jìn)的啟發(fā)式算法如下：

算法IA1(inserting algorithm 1)

步驟1：根據(jù)WSAPT排序規(guī)則生成初始調(diào)度解seq0=([1],[2],…,[n])；

步驟2：令j=1并構(gòu)建部分序列seqp=([j])，其中[j]是seq0中第j個位置的訂單；

步驟3：將訂單[j+1]插入到seqp的第k個位置，同時將該位置及后面的訂單順序后移一位，從而形成新序列seqk，其中k=1,2,…,j+1。根據(jù)式(13)，計算

(16)

步驟4：令j=j+1。如果j=n，輸出seq*并轉(zhuǎn)步驟5；否則令seqp=seq*，轉(zhuǎn)步驟3；

步驟5：根據(jù)式(13)，求解約束優(yōu)化問題；

算法IA1的計算復(fù)雜度為O(n3)。考慮到當(dāng)訂單規(guī)模較大時，算法IA1中步驟3會非常耗費時間。為了解決這一問題，可以在該步驟中對k設(shè)置一個自適應(yīng)下界，使其無需試探seqp中所有可能的插入位置，就能達(dá)到與遍歷所有位置相同或相近的優(yōu)化效果，同時能夠節(jié)省大量的運行時間。記j(n)max(1,j-「n/10?)，其中「x?表示不小于x的最小整數(shù)?；谒惴↖A1，提出改進(jìn)算法如下：

算法IA2(inserting algorithm 2)

步驟0-2，4-6與算法IA1相同，步驟3變?yōu)椋?/p>

步驟3：將訂單[j+1]插入到seqp的第k個位置，將該位置及后面的訂單順序后移一位，從而構(gòu)成新序列seqk，其中k=j(n),j(n)+1,…,j+1。根據(jù)式(13)，計算式(16)。

4 數(shù)值實驗

首先，考察三種算法的優(yōu)化效果對初始化參數(shù)τi(ζ0)的敏感性。通過大量實驗發(fā)現(xiàn)，訂單規(guī)模不會對本實驗的結(jié)論產(chǎn)生實質(zhì)性的影響，因此本文僅展示四種訂單規(guī)模n={10,20,30,40}的測試結(jié)果，每種訂單規(guī)模包含20個隨機算例。由于ζ0∈(0,1)，故考慮測試ζ0={0.1,0.3,0.5,0.7,0.9}。對于每種訂單規(guī)模，統(tǒng)計各算法在不同ζ0取值下求解20個算例的平均目標(biāo)值，結(jié)果如圖2所示。在圖2中，算法IA1和IA2的曲線接近于重合，這是由于兩種算法的優(yōu)化效果十分相近。

由圖2可見，各算法關(guān)于參數(shù)ζ0的單調(diào)性均是不確定的，但是各算法所得目標(biāo)值的波動幅度均小于5‰，因此ζ0對三種算法優(yōu)化效果的影響都很小，說明這些算法對τi初始值的擾動均具有較強的魯棒性。正是由于這種魯棒性，使得各算法在對ζ進(jìn)行重新尋優(yōu)后，無需再基于最優(yōu)值ζ*調(diào)整已得到的最優(yōu)訂單序列。對于WSAPT算法，圖2(A)表明當(dāng)n=10時，ζ0的不同取值并未對算法性能產(chǎn)生影響；由圖2(B)和2(C)可見，當(dāng)n=20或n=30時，ζ0取值大于0.5會使算法性能下降；圖2(D)則表明當(dāng)n=40時，ζ0取值為0.3要優(yōu)于其它取值。綜合來看，對于WSAPT算法，ζ0的一個合適取值是0.3。對IA1和IA2算法的結(jié)果進(jìn)行類似分析，可將兩種算法中ζ0的值選定為0.7。

下面考察各算法的優(yōu)化結(jié)果對單位時間提前費用、誤工費用和工期指派費用的敏感性。通過大量實驗發(fā)現(xiàn)，敏感性分析的實驗結(jié)論適用于任意規(guī)模的算例。因此，這里僅展示一個隨機產(chǎn)生的小規(guī)模(n=5)測試問題的相關(guān)結(jié)果，該問題的參數(shù)由表1給出。

圖2 參數(shù)ζ0對各算法所得目標(biāo)值的影響

針對該測試問題，分別應(yīng)用各算法對單位時間的提前費用hi、誤工費用bi和工期指派費用ai進(jìn)行敏感性分析，得到各算法的優(yōu)化結(jié)果如表2-4所示。其中，Δhi、Δbi和Δai分別表示hi、bi和ai的變動百分比；C*表示目標(biāo)值；ΔC*表示目標(biāo)值的變動百分比；Dev是衡量算法求解質(zhì)量的指標(biāo)，表示與已知最好解的相對偏離率，其計算公式可表示為

其中，Algor表示當(dāng)前算法名稱，C*(Algor)表示當(dāng)前算法得到的目標(biāo)值，Cbest表示所有參與比較的算法所獲得的最好目標(biāo)值；CPU表示計算時間；Enum表示基于枚舉方法的精確求解算法，通過該算法一般可以得到問題的最優(yōu)解。

表1 訂單規(guī)模n=5的測試問題參數(shù)

表2 hi的敏感性分析及算法比較結(jié)果

續(xù)表2 hi的敏感性分析及算法比較結(jié)果

由表2可見，當(dāng)提前費用hi在-50%～50%變化時，對于Enum算法，總費用C*的變動范圍僅為-2.80%～2.07%；而對于本文所提的三種算法，總費用C*的變動范圍也僅為-2.25%～1.69%。這說明了通過三種算法獲得的PSS訂單調(diào)度優(yōu)化策略較少受到庫存費用偏差的影響。在企業(yè)的實際運營中，通常很難精確估計庫存費用，然而在此算例下提前費用偏差對總費用的影響很小，因此決策者即便難以準(zhǔn)確估計庫存費用也能采用本文算法制定出比較有效的PSS訂單調(diào)度策略。

由表3可見，當(dāng)誤工費用bi在-50%～50%變化時，對于Enum算法，總費用C*的變動范圍為-7.74%～4.24%；對于本文所提的三種算法，總費用C*的變動范圍為-9.14%～9.29%。只有當(dāng)總費用的構(gòu)成中有比較少的延遲相關(guān)費用時，總費用才不會因誤工費用的變化而產(chǎn)生較大波動。因此，本文提出的PSS訂單調(diào)度策略能夠比較有效地減少訂單誤工的發(fā)生。

由表4可見，工期指派費用ai在-50%～50%變化時，對于Enum算法，總費用C*的變動范圍為-43.16%～41.62%；對于本文所提的三種算法，總費用C*的變動范圍為-39.01%～39.49%。因此，工期指派費用偏差對于PSS訂單調(diào)度費用的影響很大，決策者在估計工期指派費用時需要格外謹(jǐn)慎。

表3 bi的敏感性分析及算法比較結(jié)果

續(xù)表3 bi的敏感性分析及算法比較結(jié)果

表4 ai的敏感性分析及算法比較結(jié)果

此外，表2～4還對各算法求解問題的有效性進(jìn)行了初步對比，可以看出：

(1)WSAPT、IA1和IA2的求解速度比精確算法Enum快4個數(shù)量級，因此時間效率優(yōu)勢十分明顯；

(2)隨著誤工費用的增加或工期指派費用的減少，本文算法的求解質(zhì)量出現(xiàn)了較為明顯的下降，這主要是因為當(dāng)誤工費用與工期指派費用間的差值變大時，近似費用函數(shù)與原費用函數(shù)的偏差會逐漸加大，從而使算法的優(yōu)化效果變差；其次，本文算法采用降維尋優(yōu)策略也會使求解質(zhì)量有所下降。

最后用一組隨機產(chǎn)生的算例來測試本文算法的有效性。選取訂單規(guī)模n={20,40,60,80,100}，對于每種訂單規(guī)模隨機產(chǎn)生50個算例，從而可以得到5×50=250個算例所組成測試算例集。

對于該組問題，衡量各算法求解質(zhì)量的指標(biāo)為與已知最好解的相對偏離率Dev(Algor)和獲得最好解的概率Pgb(Algor)，后者的計算公式為:

Pgb(Algor)=

由表5可得如下結(jié)論：

(1)算法IA1和IA2的相對偏離率和獲得相對最好解的概率均明顯優(yōu)于WSAPT，因此基于WSAPT規(guī)則生成初始序列，再進(jìn)一步利用插入鄰域局部搜索進(jìn)行優(yōu)化的思路是正確且有效的；

表5 不同問題規(guī)模下的實驗結(jié)果

(2)IA2的求解質(zhì)量非常接近IA1，同時IA2的運行時間更短，并且問題規(guī)模越大其時間效率優(yōu)勢越明顯，故IA2的改進(jìn)策略是有效的；

(3)隨著訂單規(guī)模逐漸增大，IA1的兩個求解質(zhì)量指標(biāo)并未顯著變化，而IA2獲得最好解的概率在逐漸下降，因此IA1的求解質(zhì)量更穩(wěn)定；

(4)綜合來看，當(dāng)問題規(guī)模較小時，為了保證求解質(zhì)量應(yīng)當(dāng)采用IA1算法，而當(dāng)問題規(guī)模較大時適宜采用IA2算法，因為它能夠兼具較高的求解質(zhì)量與時間效率。

5 結(jié)語

訂單調(diào)度一直是企業(yè)運營管理的研究熱點和難點之一，而目前對PSS訂單調(diào)度問題的研究尚處于起步階段。本文針對由一個制造工廠和多個區(qū)域服務(wù)中心組成的服務(wù)型制造企業(yè)，考慮生產(chǎn)與服務(wù)時間均具有隨機性，構(gòu)建了PSS訂單調(diào)度與工期指派聯(lián)合決策問題的數(shù)學(xué)模型，并設(shè)計了啟發(fā)式算法對問題進(jìn)行求解。通過數(shù)值仿真的分析結(jié)果可以看出，本文的模型與算法可以在較短的時間內(nèi)得到較高質(zhì)量的解，同時對決策過程中相關(guān)調(diào)度參數(shù)的不確定性具有一定的魯棒性，因此能夠幫助服務(wù)型制造企業(yè)的調(diào)度人員做出合理、高效的PSS訂單調(diào)度安排，同時對于服務(wù)型制造企業(yè)降低運營成本和提高服務(wù)質(zhì)量也具有一定的參考價值。未來的研究方向可考慮如何設(shè)計高效的智能仿生算法來求解本文提出的問題。

附錄A

由公式推出公式的詳細(xì)過程:

E[max{dp[i]-ctp[i],0}]=

(A1)

其中

(A2)

同理，訂單[i]的產(chǎn)品的期望延誤可化簡為:

(A3)

令r[i](t)=ds[i]-max{t,dp[i]}以及g[i](s,t)=fst[i](s)fctp[i](t)，其中

(A4)

(A5)

類似式(A2)和(A3)的推導(dǎo)過程，通過積分運算易得:

(A6)

(A7)

以及

(A8)

下面對式(A7)進(jìn)行變換。根據(jù)鏈?zhǔn)椒▌t，有

(A9)

應(yīng)用分步積分法，由式(A9)可得:

(A10)

將式(A6)-(A8)和(A10)代入式(A5)，得:

(A11)