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

2019-03-07 06:37:24高華麗

中國(guó)管理科學(xué) 2019年2期

張楊，但斌，高華麗

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

1 引言

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

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

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

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

2 問(wèn)題描述與基本模型

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

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

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

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

2.2 基本模型

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

n：訂單規(guī)模；

h[i]：訂單[i]的單位時(shí)間提前費(fèi)用；

b[i]：訂單[i]的單位時(shí)間誤工費(fèi)用；

a[i]：訂單[i]的單位時(shí)間工期指派費(fèi)用；

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

seq：PSS訂單序列；

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

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

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

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

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

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

根據(jù)問(wèn)題描述和假設(shè)，給定任意PSS訂單序列seq，如果該序列的第一個(gè)訂單不在零時(shí)刻開(kāi)始生產(chǎn)，或者在兩個(gè)相鄰的訂單之間插入空閑時(shí)間，或者在同一訂單的生產(chǎn)階段和服務(wù)階段之間插入空閑時(shí)間，都會(huì)推遲PSS的交付時(shí)間并產(chǎn)生更多工期指派費(fèi)用，同時(shí)不會(huì)減少其它費(fèi)用。因此問(wèn)題的最優(yōu)調(diào)度一定是非延遲調(diào)度，且第一個(gè)訂單一定在零時(shí)刻開(kāi)始生產(chǎn)。基于以上分析，以最小化期望總費(fèi)用為目標(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ù)交付期長(zhǎng)度向量。式表示目標(biāo)為最小化產(chǎn)品的期望提前費(fèi)用、產(chǎn)品與服務(wù)的期望誤工費(fèi)用以及工期指派費(fèi)用之和；式和分別定義了訂單[i]的產(chǎn)品和服務(wù)的完工時(shí)間。

3 問(wèn)題求解

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

3.1 工期指派方法

C(seq,dp,ls)

(4)

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

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

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

步驟3：基于近似目標(biāo)函數(shù)的最優(yōu)工期和最優(yōu)值，設(shè)計(jì)啟發(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)

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

λ1,[i]

λ2,[i]

以及

(13)

其中，

φ[i]

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

由上式和式(12)可得

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

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

可以得到問(wèn)題

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

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

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

以及

進(jìn)而得到

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

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

算法WSAPT

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

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

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

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

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

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

(15)

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

由于WSAPT規(guī)則是基于近似目標(biāo)函數(shù)上界得到的調(diào)度規(guī)則，通過(guò)WSAPT算法得到的調(diào)度解可能會(huì)與原目標(biāo)函數(shù)的最優(yōu)調(diào)度解存在較大偏離，因此需要引入優(yōu)化機(jī)制進(jìn)一步提高解的質(zhì)量。本文的改進(jìn)方法為：首先利用WSAPT規(guī)則產(chǎn)生初始解，然后對(duì)該初始解執(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個(gè)位置的訂單；

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

(16)

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

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

算法IA1的計(jì)算復(fù)雜度為O(n3)?？紤]到當(dāng)訂單規(guī)模較大時(shí)，算法IA1中步驟3會(huì)非常耗費(fèi)時(shí)間。為了解決這一問(wèn)題，可以在該步驟中對(duì)k設(shè)置一個(gè)自適應(yīng)下界，使其無(wú)需試探seqp中所有可能的插入位置，就能達(dá)到與遍歷所有位置相同或相近的優(yōu)化效果，同時(shí)能夠節(jié)省大量的運(yùn)行時(shí)間。記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è)位置，將該位置及后面的訂單順序后移一位，從而構(gòu)成新序列seqk，其中k=j(n),j(n)+1,…,j+1。根據(jù)式(13)，計(jì)算式(16)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pgb(Algor)=

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

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

表5 不同問(wèn)題規(guī)模下的實(shí)驗(yàn)結(jié)果

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

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

(4)綜合來(lái)看，當(dāng)問(wèn)題規(guī)模較小時(shí)，為了保證求解質(zhì)量應(yīng)當(dāng)采用IA1算法，而當(dāng)問(wèn)題規(guī)模較大時(shí)適宜采用IA2算法，因?yàn)樗軌蚣婢咻^高的求解質(zhì)量與時(shí)間效率。

5 結(jié)語(yǔ)

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

附錄A

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