基于改進(jìn)迭代貪婪算法的產(chǎn)品服務(wù)系統(tǒng)訂單調(diào)度優(yōu)化

張 楊，但 斌，高華麗

(1.重慶工商大學(xué) 管理學(xué)院，重慶 400067；2.重慶市人文社科重點(diǎn)研究基地 重慶工商大學(xué)企業(yè)管理研究中心，重慶 400067；3.重慶大學(xué) 經(jīng)濟(jì)與工商管理學(xué)院，重慶 400044;4.西南政法大學(xué) 商學(xué)院，重慶 401120)

0 引言

近年來，由于產(chǎn)品同質(zhì)化競(jìng)爭(zhēng)的加劇、客戶個(gè)性化需求的增加、生產(chǎn)要素成本的上升以及資源和環(huán)境問題的突顯，全球制造業(yè)正在向信息化、智能化、綠色化和服務(wù)化轉(zhuǎn)型升級(jí)。服務(wù)型制造作為創(chuàng)新發(fā)展的重要轉(zhuǎn)型方向之一，得到了許多企業(yè)和國(guó)家的重視與推廣。例如，IBM和羅爾斯·羅伊斯等公司從單純的產(chǎn)品制造商成功轉(zhuǎn)型為“產(chǎn)品+服務(wù)”解決方案提供商，全球500強(qiáng)企業(yè)中有兩成跨國(guó)制造企業(yè)的服務(wù)收入超過總收入的50%。為了推動(dòng)國(guó)家制造業(yè)的轉(zhuǎn)型，德國(guó)推出了“工業(yè)4.0”，美國(guó)提出了“國(guó)家制造創(chuàng)新網(wǎng)絡(luò)”，日本制定了“工業(yè)價(jià)值鏈”戰(zhàn)略，這些國(guó)家戰(zhàn)略均強(qiáng)調(diào)要推動(dòng)服務(wù)型制造。2015年5月，國(guó)務(wù)院印發(fā)《中國(guó)制造2025》，提出“積極發(fā)展服務(wù)型制造和生產(chǎn)性服務(wù)業(yè)”[1]。2016年7月，工信部、國(guó)家發(fā)改委和中國(guó)工程院三部委聯(lián)合印發(fā)《發(fā)展服務(wù)型制造專項(xiàng)行動(dòng)指南》，提出到2018年“基本實(shí)現(xiàn)與制造強(qiáng)國(guó)戰(zhàn)略進(jìn)程相適應(yīng)的服務(wù)型制造發(fā)展格局”[2]。在服務(wù)型制造模式下，制造企業(yè)將產(chǎn)品和服務(wù)整合為全面的解決方案，即產(chǎn)品服務(wù)系統(tǒng)(Product Service System, PSS)[3]。例如，在裝備制造業(yè)(例如電梯、風(fēng)電等行業(yè))，機(jī)械設(shè)備的生產(chǎn)與安裝是一類典型的PSS。對(duì)于該類PSS訂單，很多客戶通常希望企業(yè)盡早交付，從而能夠?qū)SS盡快投入使用以創(chuàng)造收益。例如，房地產(chǎn)開發(fā)商通常希望樓盤配套的電梯能盡早安裝完畢，以加快新盤入市和資金回流；風(fēng)電場(chǎng)業(yè)主通常希望風(fēng)機(jī)能夠盡早完成安裝，以盡快實(shí)現(xiàn)并網(wǎng)發(fā)電創(chuàng)收。對(duì)于這類時(shí)間敏感型的客戶，較短的PSS交付時(shí)間意味著更高的客戶服務(wù)水平，同時(shí)也說明了企業(yè)具有更強(qiáng)的競(jìng)爭(zhēng)力和更高的運(yùn)營(yíng)效率。這是因?yàn)樵趦r(jià)格與質(zhì)量相同或相近的情況下，客戶通常會(huì)選擇在更短時(shí)間內(nèi)交付PSS的企業(yè)；從長(zhǎng)期來看，PSS的交付時(shí)間越短，企業(yè)在單位時(shí)間內(nèi)能夠滿足的PSS訂單越多，收益就越多，同時(shí)對(duì)生產(chǎn)資源以及服務(wù)資源的利用率也就越高。因此，研究如何制定合理的PSS訂單調(diào)度策略以實(shí)現(xiàn)訂單的快速響應(yīng)與交付，對(duì)于服務(wù)型制造企業(yè)提升服務(wù)水平和實(shí)現(xiàn)降本增效具有重要意義。

近年來，PSS得到了企業(yè)界和學(xué)術(shù)界的廣泛關(guān)注與研究。許多學(xué)者采用定性方法對(duì)PSS的概念、設(shè)計(jì)和案例分析等內(nèi)容進(jìn)行了研究[4]，然而僅有少量學(xué)者對(duì)PSS進(jìn)行了定量研究，這些定量研究主要集中在市場(chǎng)博弈、合作契約分析和系統(tǒng)運(yùn)作優(yōu)化等方面。例如，Xie等[5]針對(duì)制造商和零售商合作提供PSS的供應(yīng)鏈，在信息不對(duì)稱條件下研究了3種協(xié)調(diào)契約對(duì)供應(yīng)鏈決策的影響；Lee等[6]考慮單純提供產(chǎn)品的傳統(tǒng)渠道和提供PSS的服務(wù)化渠道間存在價(jià)格與質(zhì)量競(jìng)爭(zhēng)，基于博弈理論分析了服務(wù)依賴性和渠道可替代性對(duì)服務(wù)化競(jìng)爭(zhēng)力的影響；劉宇熹等[7]針對(duì)租賃PSS設(shè)計(jì)了一種節(jié)約共享契約來協(xié)調(diào)再制造企業(yè)與客戶間的收益。在運(yùn)營(yíng)管理領(lǐng)域，Li等[8]針對(duì)帶有額外服務(wù)能力和面對(duì)不耐煩客戶的PSS，構(gòu)建了一種塊結(jié)構(gòu)的馬爾可夫鏈優(yōu)化模型；為了評(píng)估公共倉庫的服務(wù)能力和優(yōu)化資源配置，Cao等[9]采用目標(biāo)分流法建立了一種倉庫PSS服務(wù)能力成熟度模型；Wang等[10]針對(duì)同時(shí)提供產(chǎn)品與PSS的服務(wù)型制造系統(tǒng)，研究了最優(yōu)生產(chǎn)和準(zhǔn)入控制問題；王康周等[11]針對(duì)由生產(chǎn)設(shè)施和服務(wù)中心組成的柔性生產(chǎn)服務(wù)系統(tǒng)，研究了生產(chǎn)和服務(wù)能力的協(xié)同分配問題；Zhang等[12]基于物理互聯(lián)網(wǎng)和PSS為云物流構(gòu)建了智能箱型PSS，并結(jié)合云計(jì)算技術(shù)提出一種物流任務(wù)動(dòng)態(tài)優(yōu)化方法。上述文獻(xiàn)為PSS的營(yíng)銷運(yùn)營(yíng)管理提供了經(jīng)驗(yàn)和參考，然而這些文獻(xiàn)均未探討如何對(duì)幾乎同時(shí)到達(dá)的批量PSS訂單進(jìn)行優(yōu)化調(diào)度，該問題的本質(zhì)是對(duì)PSS訂單的生產(chǎn)任務(wù)和服務(wù)任務(wù)進(jìn)行協(xié)同調(diào)度，因此目前亟待對(duì)PSS訂單的調(diào)度問題進(jìn)行深入探討。本文的研究能豐富和拓展生產(chǎn)運(yùn)營(yíng)管理領(lǐng)域中調(diào)度管理和服務(wù)質(zhì)量管理的相關(guān)理論與應(yīng)用。

另一個(gè)與本文密切相關(guān)的研究方向是訂單調(diào)度問題，該問題已成為生產(chǎn)與運(yùn)營(yíng)管理領(lǐng)域的研究熱點(diǎn)。Wang等[13]考慮每個(gè)客戶訂單包含多個(gè)需要在不同專用設(shè)施上處理的作業(yè)，以最小化加權(quán)訂單完成時(shí)間總和為目標(biāo)研究了相應(yīng)的訂單調(diào)度問題；周水銀等[14]針對(duì)流水車間環(huán)境，在服務(wù)水平約束下研究了成套訂單的調(diào)度問題；梁旭等[15]針對(duì)加工和裝配混合生產(chǎn)形態(tài)下的多訂單調(diào)度問題，提出一種新的遺傳算法；Xu等[16]提出一種基于位置學(xué)習(xí)效應(yīng)的多訂單調(diào)度問題，其優(yōu)化目標(biāo)設(shè)定為最小化總延誤；為了解決具有準(zhǔn)備時(shí)間的雙代理多設(shè)施訂單調(diào)度問題，Lin等[17]基于粒子群算法設(shè)計(jì)了3種元啟發(fā)式算法；劉儼后等[18]針對(duì)混流裝配線上的緊急插單情形提出一種動(dòng)態(tài)調(diào)度策略，從而實(shí)現(xiàn)了緊急訂單的最大程度交付和生產(chǎn)目標(biāo)的最優(yōu)化；Framinan等[19]針對(duì)最小化總延誤的訂單調(diào)度問題，提出了多種構(gòu)造型啟發(fā)式方法；Wu等[20]在客戶訂單調(diào)度問題中考慮基于加工時(shí)間的學(xué)習(xí)效應(yīng)，并以訂單總延誤最小化為目標(biāo)建立了相應(yīng)問題的優(yōu)化模型。上述研究?jī)H考慮了單一生產(chǎn)類型或單一服務(wù)類型訂單，而本文討論的PSS訂單調(diào)度問題同時(shí)包含了生產(chǎn)和服務(wù)的協(xié)同調(diào)度，情形更為復(fù)雜且難以求解。因此，以往針對(duì)單一類型訂單調(diào)度問題的解決方案不適用于PSS訂單調(diào)度問題，需要基于PSS的運(yùn)作特點(diǎn)制定新的調(diào)度策略。

鑒于此，本文以擁有多條生產(chǎn)線和多支安裝團(tuán)隊(duì)的服務(wù)型制造企業(yè)為對(duì)象，考慮客戶在訂單中規(guī)定了最早允許服務(wù)時(shí)間，對(duì)相應(yīng)PSS訂單調(diào)度問題進(jìn)行研究。首先以最小化訂單交付時(shí)間總和為目標(biāo)構(gòu)建問題的數(shù)學(xué)模型，然后根據(jù)問題特點(diǎn)設(shè)計(jì)改進(jìn)的迭代貪婪(Interative Greedy, IG)算法進(jìn)行求解，最后通過仿真實(shí)驗(yàn)分析算法的有效性。

1 問題描述

考慮擁有m條生產(chǎn)線M={1,2,…,m}和l支安裝團(tuán)隊(duì)L={1,2,…,l}的服務(wù)型制造企業(yè)，面向市場(chǎng)滿足客戶的PSS訂單需求，其交付流程如圖1所示。在計(jì)劃期的初始時(shí)刻即零時(shí)刻，企業(yè)接收了包含n個(gè)PSS訂單的訂單集合N={1,2,…,n}。其中，每個(gè)訂單包含一單位的產(chǎn)品及相應(yīng)安裝服務(wù)，并規(guī)定了客戶要求的最早允許服務(wù)時(shí)間，早于該時(shí)間客戶會(huì)由于各種原因(如不具備安裝條件)而不能接受服務(wù)。各PSS訂單的交付需要依次經(jīng)過生產(chǎn)階段和服務(wù)階段這兩個(gè)階段H={1,2}，在生產(chǎn)階段，企業(yè)需要決策各訂單的生產(chǎn)任務(wù)分配給哪條生產(chǎn)線及各生產(chǎn)線上執(zhí)行生產(chǎn)任務(wù)的順序；在服務(wù)階段，企業(yè)需要決策各訂單的服務(wù)任務(wù)分配給哪支安裝團(tuán)隊(duì)及各安裝團(tuán)隊(duì)執(zhí)行服務(wù)任務(wù)的順序。企業(yè)的優(yōu)化目標(biāo)是通過制定最優(yōu)的PSS訂單調(diào)度策略，使得所有訂單的交付時(shí)間總和最小化(等價(jià)于訂單的平均交付時(shí)間最小化)。根據(jù)以上描述，在表1中給出了PSS訂單調(diào)度問題的目標(biāo)函數(shù)、輸入條件、約束條件和輸出條件，作為建立優(yōu)化模型的基礎(chǔ)。

表1 PSS訂單調(diào)度問題構(gòu)成要素

本文研究的PSS訂單調(diào)度問題的主要特點(diǎn)是：生產(chǎn)調(diào)度與服務(wù)調(diào)度的整合與協(xié)同。由于實(shí)物產(chǎn)品與服務(wù)具有不同的性質(zhì)：產(chǎn)品是有形的、可儲(chǔ)存的，而服務(wù)是無形的、不可儲(chǔ)存的，因此在生產(chǎn)調(diào)度過程中，產(chǎn)品可以被提前生產(chǎn)并儲(chǔ)存起來，并在后續(xù)時(shí)間成為提供服務(wù)的載體。這說明生產(chǎn)調(diào)度過程可以利用庫存作為一種緩沖，從而能夠在一定程度上保證產(chǎn)品供應(yīng)的及時(shí)性。然而，服務(wù)的生產(chǎn)和消費(fèi)是同時(shí)進(jìn)行的，且服務(wù)的提供必須以產(chǎn)品為基礎(chǔ)，因此服務(wù)調(diào)度過程不存在緩沖，而且會(huì)受到產(chǎn)品生產(chǎn)完工時(shí)間和最早允許服務(wù)時(shí)間的雙重制約。由此可見，PSS訂單調(diào)度中的生產(chǎn)調(diào)度和服務(wù)調(diào)度相互影響、相互作用，如何有效協(xié)同兩種調(diào)度過程是企業(yè)面臨的一個(gè)難題。此外，最小化訂單交付時(shí)間總和的PSS訂單調(diào)度問題屬于NP-hard問題。如果不考慮最早允許服務(wù)時(shí)間的約束，將訂單看作“工件”，同時(shí)將生產(chǎn)線和安裝團(tuán)隊(duì)看作“機(jī)器”，則服務(wù)型制造系統(tǒng)可以看作是柔性流水車間(flexible flowshop)。而已知最小化加權(quán)完工時(shí)間的柔性流水車間調(diào)度是NP-hard問題[21]，因此根據(jù)等價(jià)傳遞規(guī)則，本文研究的問題也是NP-hard問題。但在PSS訂單調(diào)度問題中，由于服務(wù)具有不可儲(chǔ)存性，生產(chǎn)完工后不能早于最早允許服務(wù)時(shí)間提供服務(wù)，這與多階段生產(chǎn)系統(tǒng)可利用庫存緩沖下一階段的生產(chǎn)作業(yè)是不同的。PSS訂單調(diào)度問題的上述特點(diǎn)和NP-hard特性使得該問題的求解非常困難，必須尋找協(xié)同和集中決策下的調(diào)度策略。

2 模型建立

2.1 模型假設(shè)

為了便于對(duì)PSS訂單調(diào)度問題進(jìn)行研究，本文假設(shè)：

(1)每個(gè)訂單的生產(chǎn)時(shí)間和服務(wù)時(shí)間均是確定且已知的；

(2)同一訂單在每條生產(chǎn)線上的生產(chǎn)時(shí)間均相同，在每支安裝團(tuán)隊(duì)處的服務(wù)時(shí)間也相同；

(3)生產(chǎn)任務(wù)和服務(wù)任務(wù)一旦開始，不允許中斷；

(4)同一時(shí)刻，每條生產(chǎn)線只能執(zhí)行一項(xiàng)生產(chǎn)任務(wù)，每支安裝團(tuán)隊(duì)只能執(zhí)行一項(xiàng)服務(wù)任務(wù)。

2.2 符號(hào)定義

為了方便建立PSS訂單調(diào)度問題的數(shù)學(xué)模型，定義如下符號(hào)：

(1)下標(biāo)

i,j為訂單序號(hào)；

k為生產(chǎn)線(安裝團(tuán)隊(duì))編號(hào)；

h為階段類型，h=1表示生產(chǎn)階段，h=2表示服務(wù)階段。

(2)參數(shù)

pti為訂單i的生產(chǎn)時(shí)間；

sti為訂單i的服務(wù)時(shí)間；

ei為訂單i的最早允許服務(wù)時(shí)間；

Q為足夠大的正數(shù)。

(3)決策變量

STPi為訂單i的生產(chǎn)開工時(shí)間；

CTPi為訂單i的生產(chǎn)完工時(shí)間；

STSi為訂單i的服務(wù)開始時(shí)間；

CTSi為訂單i的服務(wù)完成時(shí)間；

yikh為如果訂單i的生產(chǎn)(服務(wù))任務(wù)被分配給生產(chǎn)線(安裝團(tuán)隊(duì))k，則yikh=1，否則yikh=0；

xijkh為如果訂單i和j的生產(chǎn)(服務(wù))任務(wù)被分配給生產(chǎn)線(安裝團(tuán)隊(duì))k，且訂單i先于訂單j，則xijkh=1，否則xijkh=0。

如果訂單i∈N是生產(chǎn)線k∈M上第一個(gè)生產(chǎn)的訂單，易知其最早生產(chǎn)完工時(shí)間等于生產(chǎn)時(shí)間pti。為使最早允許服務(wù)時(shí)間起到約束作用，需要求最早允許服務(wù)時(shí)間不早于其最早生產(chǎn)完工時(shí)間，即滿足ei≥pti。

2.3 數(shù)學(xué)模型

基于上文描述和假設(shè)，構(gòu)建PSS訂單調(diào)度問題的數(shù)學(xué)模型如下：

(1)

s.t.

CTPi=STPi+pti,?i∈N；

(2)

STPj≥CTPi+Q(xijk1-1),

?i,j∈N,i≠j,k∈M；

(3)

STSi≥CTPi,?i∈N；

(4)

STSi≥ei,?i∈N；

(5)

CTSi=STSi+sti,?i∈N；

(6)

STSj≥CTSi+Q(xijk2-1),

?i,j∈N,i≠j,k∈L；

(7)

xijkh+xjikh≤yikh,

(8)

xijkh+xjikh≥yikh+yjkh-1,

(9)

(10)

STPi≥0,CTPi≥0,STSi≥0,CTSi≥0,

?i∈N；

(11)

xijkh,yikh∈{0,1},?i,j∈N,

(12)

其中：式(1)表示目標(biāo)為最小化訂單交付時(shí)間總和；式(2)表示產(chǎn)品在生產(chǎn)過程中不允許中斷；式(3)表示同一時(shí)刻每條生產(chǎn)線只能執(zhí)行一項(xiàng)生產(chǎn)任務(wù)；式(4)表示同一訂單的服務(wù)開始時(shí)間不能早于其生產(chǎn)完工時(shí)間；式(5)表示同一訂單的服務(wù)開始時(shí)間不能早于其最早允許服務(wù)時(shí)間；式(6)表示服務(wù)在提供過程中不許中斷；式(7)表示同一時(shí)刻每支安裝團(tuán)隊(duì)只能執(zhí)行一項(xiàng)服務(wù)任務(wù)；式(8)和式(9)表示每條生產(chǎn)線的生產(chǎn)任務(wù)執(zhí)行順序，以及每支安裝團(tuán)隊(duì)的服務(wù)任務(wù)執(zhí)行順序；式(10)表示每個(gè)訂單的生產(chǎn)任務(wù)必須被分配給一條生產(chǎn)線，服務(wù)任務(wù)必須被分配給一支安裝團(tuán)隊(duì)；式(11)和式(12)定義了各決策變量的取值范圍。

3 問題求解

最小化訂單交付時(shí)間總和的PSS訂單調(diào)度屬于NP-hard問題，當(dāng)規(guī)模較大時(shí)難以在多項(xiàng)式時(shí)間內(nèi)獲得精確解，因此通常采用啟發(fā)式算法尋找問題的近似最優(yōu)解。IG算法由是Ruiz等[22]提出的一種新型智能優(yōu)化算法，該算法主要由鄰域搜索、擾動(dòng)算子和接受準(zhǔn)則3個(gè)基本部分組成。IG算法提出后，以其參數(shù)少、易實(shí)現(xiàn)和效率高等特點(diǎn)引起了眾多國(guó)內(nèi)外學(xué)者的關(guān)注和研究，并在阻塞流水車間調(diào)度[23]和二次多重背包問題[24]等領(lǐng)域得到了理論研究和實(shí)踐應(yīng)用。

本文提出一種改進(jìn)的IG算法來求解PSS訂單調(diào)度問題，其基本思想為：首先基于訂單的最早允許服務(wù)時(shí)間排序，設(shè)計(jì)一種構(gòu)造型啟發(fā)式算法來產(chǎn)生初始調(diào)度；然后采用局部搜索策略，在當(dāng)前解的鄰域內(nèi)進(jìn)行搜索和優(yōu)化；局部搜索后，利用擾動(dòng)算子跳出局部最優(yōu)以防止算法過早收斂；最后，根據(jù)接受準(zhǔn)則更新當(dāng)前解和最好解，直到迭代滿足終止準(zhǔn)則。本文對(duì)IG算法的改進(jìn)主要包括：①根據(jù)PSS訂單調(diào)度問題的特點(diǎn)，提出了基于訂單排列的整數(shù)編碼與解碼方法；②基于訂單的最早允許服務(wù)時(shí)間排序，設(shè)計(jì)了一種用于產(chǎn)生初始解的構(gòu)造型啟發(fā)式算法；③基于變鄰域搜索的思想，提出一種結(jié)合了插入和交換操作的高效鄰域搜索策略；④在破壞和重建過程中，通過嵌入針對(duì)部分解的局部搜索優(yōu)化提出了一種改進(jìn)的擾動(dòng)算子；⑤基于輪盤賭選擇，設(shè)計(jì)了一種新的接受準(zhǔn)則來更新當(dāng)前解。下面對(duì)改進(jìn)IG算法的主要部分進(jìn)行說明。

3.1 編碼與解碼

本文采用基于PSS訂單排序的編碼方式對(duì)個(gè)體進(jìn)行編碼，個(gè)體的解可表達(dá)為π={π(1),π(2),…,π(n)}，其中π(j)表示序列中排在第j個(gè)位置的訂單。在對(duì)個(gè)體進(jìn)行解碼時(shí)，需要規(guī)定在PSS訂單的交付過程中，不允許出現(xiàn)任何非強(qiáng)迫的空閑，即當(dāng)生產(chǎn)線或安裝團(tuán)隊(duì)處于空閑狀態(tài)時(shí)，不存在可被立即執(zhí)行的訂單任務(wù)；此外，本文定義一個(gè)訂單的“服務(wù)就緒時(shí)間”為該訂單可以開始提供服務(wù)的最早時(shí)間，該時(shí)間一定不早于訂單的生產(chǎn)完工時(shí)間和最早允許服務(wù)時(shí)間。個(gè)體的解碼步驟如下：

步驟1在生產(chǎn)階段，按照給定訂單排序每次取出一個(gè)訂單，將其生產(chǎn)任務(wù)分配給最先空閑的生產(chǎn)線，直到所有訂單分配完畢；如果有多條生產(chǎn)線同時(shí)處于空閑，則將訂單的生產(chǎn)任務(wù)分配給編號(hào)最小的生產(chǎn)線。

步驟2按照各訂單的服務(wù)就緒時(shí)間對(duì)訂單進(jìn)行升序排列，從而得到一個(gè)新的序列；如果有多個(gè)訂單的服務(wù)就緒時(shí)間相同，則將編號(hào)較小的訂單排在前面。

步驟3在服務(wù)階段，按照新的訂單排列每次取出一個(gè)訂單，將其服務(wù)任務(wù)分配給最先空閑的安裝團(tuán)隊(duì)，直到所有訂單分配完畢；如果有多支安裝團(tuán)隊(duì)同時(shí)處于空閑狀態(tài)，則將訂單的服務(wù)任務(wù)分配給編號(hào)最小的安裝團(tuán)隊(duì)。

步驟4各生產(chǎn)線和安裝團(tuán)隊(duì)執(zhí)行各自分配的任務(wù)，所有任務(wù)完成后，計(jì)算每個(gè)訂單的服務(wù)交付時(shí)間。

表2 示例的訂單參數(shù)

3.2 初始化

本文基于PSS訂單的最早允許服務(wù)時(shí)間排序?qū)EH(Nawaz-Enscore-Ham)算法[25]進(jìn)行改編，提出一種NEHEAST(NEH with earliest allowable service time)算法作為IG算法的初始化方法。該算法的基本思想如下：首先根據(jù)最早允許服務(wù)時(shí)間對(duì)訂單進(jìn)行升序排列，得到一個(gè)初始序列；然后對(duì)該初始序列前兩個(gè)訂單進(jìn)行排序，選擇具有較小訂單交付時(shí)間總和的調(diào)度作為部分序列；接下來將初始序列中的剩余訂單逐一插入到部分序列中的所有可能位置，并選擇具有最小訂單交付時(shí)間總和的調(diào)度作為新的部分序列；當(dāng)所有訂單插入完畢，最后重新得到一個(gè)完整序列。NEHEAST算法的偽代碼如圖3所示。

3.3 鄰域搜索

鄰域搜索方法對(duì)IG算法的求解效果影響很大。經(jīng)典IG算法采用的鄰域搜索方法是一種基于插入操作且首次改進(jìn)即更新的高性能局部搜索算法，該算法能夠找到基于插入鄰域的局部最優(yōu)，但是忽略了交換鄰域這種常用的鄰域結(jié)構(gòu)，而關(guān)于插入鄰域的局部最優(yōu)解不一定是關(guān)于交換鄰域的局部最優(yōu)解。因此，受Solis等[26]提出的隨機(jī)搜索(random search)以及Hansen等[27]提出的簡(jiǎn)化變鄰域搜索(reduced variable neighborhood search)思想的啟發(fā)，本文將插入鄰域搜索和交換鄰域搜索相結(jié)合，提出一種隨機(jī)鄰域搜索(Random Neighborhood Search，RNS)算法，以擴(kuò)大搜索空間和提高尋優(yōu)效率。其基本思想是：每次從當(dāng)前解中隨機(jī)地選擇一個(gè)訂單，隨機(jī)地選擇插入鄰域或者交換鄰域進(jìn)行搜索，前者將其從原位置移除并插入到所有可能位置中的最優(yōu)位置，后者將其與所有可能位置中最優(yōu)位置的訂單進(jìn)行交換；如果通過鄰域搜索找到的新解優(yōu)于當(dāng)前解，則替換當(dāng)前解并且繼續(xù)搜索，否則結(jié)束搜索。隨機(jī)鄰域搜索的偽代碼如圖4所示。

3.4 擾動(dòng)算子

為了避免IG算法在求解PSS訂單調(diào)度問題時(shí)陷入局部最優(yōu)，必須設(shè)計(jì)一種有效的跳出機(jī)制，該機(jī)制也稱為擾動(dòng)算子。經(jīng)典IG算法采用破壞(destruction)和重建(construction)過程作為擾動(dòng)算子，其主要思想是：在破壞階段，從當(dāng)前解中隨機(jī)選擇若干訂單并移除，得到兩個(gè)部分序列：由剩余訂單組成的部分解、由移除訂單按照移除順序組成的部分序列；在重建階段，將部分序列中的訂單逐一插入到部分解中所有可能位置的最優(yōu)位置，從而最終得到一個(gè)擾動(dòng)解。然而，該擾動(dòng)算子在擾動(dòng)后，可能丟失局部最優(yōu)解的優(yōu)良特性，從而導(dǎo)致后續(xù)局部搜索可能陷入比之前局部最優(yōu)解更差的局部最優(yōu)點(diǎn)。Framinan等[28]以及Rad等[29]的研究表明，在構(gòu)造完整解的過程中對(duì)部分解進(jìn)行鄰域搜索優(yōu)化能夠改善最終解。受上述研究的啟發(fā)，本文提出一種破壞—優(yōu)化—重建(Destruction-Optimization-Construction, DOC)作為改進(jìn)IG算法的擾動(dòng)算子，其主要?jiǎng)?chuàng)新在于：對(duì)執(zhí)行破壞操作后的部分解實(shí)施若干次插入鄰域搜索，再對(duì)優(yōu)化后的部分解執(zhí)行重建操作，以期改善擾動(dòng)解的質(zhì)量。DOC擾動(dòng)算子的偽代碼如圖5所示。

3.5 接受準(zhǔn)則

接受準(zhǔn)則的作用是更新IG算法的當(dāng)前解和最好解。然而，由于擾動(dòng)算子的擾動(dòng)有時(shí)可能不是足夠大，導(dǎo)致算法在后續(xù)局部搜索過程中又陷入到相同局部最優(yōu)點(diǎn)。為了幫助IG算法更有效地跳出局部最優(yōu)，本文基于遺傳算法中常用的輪盤賭選擇(Roulette Wheel Selection，RWS)策略，提出一種新的接受準(zhǔn)則。在該接受準(zhǔn)則中，需要構(gòu)建一個(gè)精英表(elite list)，該精英表儲(chǔ)存了通過局部搜索找到的新解。

RWS接受準(zhǔn)則：通過局部搜索找到新解后，如果新解優(yōu)于最好解，則更新最好解，且清空精英表；如果新解不在精英表中，則將新解添加到精英表的尾部；如果精英表的長(zhǎng)度超過ω，則從表中刪除最壞解；按照RWS策略從精英表中選擇一個(gè)解為當(dāng)前解。令精英表的長(zhǎng)度為τ(τ≤ω)，RWS策略的實(shí)現(xiàn)步驟如下：

步驟1對(duì)精英表中每個(gè)解的目標(biāo)值進(jìn)行min-max歸一化處理，計(jì)算公式為：

步驟3由[0,1]區(qū)間的均勻分布產(chǎn)生一個(gè)隨機(jī)數(shù)Rand。如果Rand

RWS接受準(zhǔn)則的偽代碼如圖6所示，其中π和π*分別表示當(dāng)前解和最好解，EliteList表示精英表。

Procedure RWS(π,π*,EliteList,ω)

if Z(π)

π*:=π;

EliteList:=?;

end if

if π?EliteList then

add π to the end of EliteList;

end if

if |EliteList|>ω then

remove the worst solution among EliteList;

end if

π:=a permutation selected from EliteList according to the RWS strategy;

return{π,π*,EliteList}

end procedure

圖6 RWS接受準(zhǔn)則的偽代碼

3.6 終止條件

由于具有較大訂單規(guī)模的PSS訂單調(diào)度問題可能需要運(yùn)行更長(zhǎng)時(shí)間來搜索最優(yōu)解，本文設(shè)置改進(jìn)IG算法的終止條件為最大CPU時(shí)間100nms，該終止條件能夠隨著訂單規(guī)模n動(dòng)態(tài)地調(diào)整。

3.7 求解PSS訂單調(diào)度問題的改進(jìn)IG算法流程

結(jié)合PSS訂單調(diào)度問題的特點(diǎn)，上文對(duì)改進(jìn)IG算法的主要組成部分進(jìn)行了描述，如圖7所示為整個(gè)算法的求解流程。

Procedure MIG

set the parameters λ and ω;

π0:=NEHEAST;

π:=RNS(π0);

π*:=π;

EliteList:={π};

while CPU time≤100n do

π′:=DOC(π,λ)

π″:=RNS(π′)

{π,π*,EliteList}:=RWS(π″,π*,EliteList,ω);

end while

return π*

end procedure

圖7 改進(jìn)IG算法的求解流程

4 仿真實(shí)驗(yàn)

本章通過仿真實(shí)驗(yàn)來評(píng)價(jià)改進(jìn)的IG算法的優(yōu)化性能。所有算法均采用MATLAB(R2018b)編制程序，并在一臺(tái)配備2.50 GHz Intel(R)Core(TM)i5-7300HQ CPU和8 G RAM的PC機(jī)上進(jìn)行實(shí)驗(yàn)。

4.1 算例構(gòu)造與性能評(píng)價(jià)指標(biāo)

根據(jù)PSS訂單調(diào)度問題的特點(diǎn)，考慮隨機(jī)產(chǎn)生測(cè)試算例。令生產(chǎn)時(shí)間pti和服務(wù)時(shí)間sti均由區(qū)間[1,100]的均勻分布隨機(jī)產(chǎn)生，最早允許服務(wù)時(shí)間ei由區(qū)間[pti,(1+θ)pti]的均勻分布隨機(jī)產(chǎn)生。算例的實(shí)驗(yàn)參數(shù)取值為n={50,100,150,200}、m={2,5,10}、l={2,3,5}和θ={1,2,3}，故共有4×3×3×3=108種參數(shù)組合。對(duì)于每種參數(shù)組合，隨機(jī)產(chǎn)生2個(gè)算例，這樣可得到一個(gè)包含108×2=216算例的基準(zhǔn)測(cè)試算例集。

評(píng)價(jià)算法性能的指標(biāo)為相對(duì)偏差指數(shù)(RDI)，

其中對(duì)于每個(gè)算例，Zalg表示給定算法得到的訂單交付時(shí)間總和，Zbest和Zworst分別表示所有算法得到的訂單交付時(shí)間總和的最小值和最大值。如果Zbest與Zworst相等，表示所有算法得到的訂單交付時(shí)間總和均相同，此時(shí)令RDI的值為零。RDI的值越小，說明給定算法的性能越好。

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

算法的參數(shù)設(shè)置對(duì)求解效果有重要影響，因此本節(jié)采用實(shí)驗(yàn)設(shè)計(jì)(design of experiments)[30]方法對(duì)改進(jìn)IG算法的參數(shù)進(jìn)行調(diào)整。Pan等[31]指出，將參數(shù)校準(zhǔn)的基準(zhǔn)算例與最終測(cè)試的基準(zhǔn)算例分離是至關(guān)重要的，因?yàn)椴捎米罱K測(cè)試的基準(zhǔn)算例進(jìn)行參數(shù)校準(zhǔn)會(huì)造成過度校準(zhǔn)和產(chǎn)生過于樂觀的結(jié)果，算例一旦改變將導(dǎo)致算法無法再獲得好的計(jì)算結(jié)果。據(jù)此，本文用于參數(shù)設(shè)置的算例集合包含50個(gè)算例，每個(gè)算例通過隨機(jī)選取n′={20,50,80,100,120,150,180,200}以及上述m、l和θ的參數(shù)取值集合中的一個(gè)值來產(chǎn)生。

在實(shí)驗(yàn)設(shè)計(jì)方法的因子設(shè)計(jì)中，考慮將算法參數(shù)看作因子，并對(duì)因子的不同水平進(jìn)行測(cè)試。改進(jìn)IG算法包含兩個(gè)參數(shù)：λ和ω，測(cè)試水平分別為：λ={1,2,3,4}和ω={5,6,7,8}，這樣共有4×4=16種參數(shù)組合。對(duì)于每種參數(shù)組合，改進(jìn)IG算法分別對(duì)每個(gè)算例運(yùn)算5次，并對(duì)計(jì)算結(jié)果取平均值。

參數(shù)設(shè)置的實(shí)驗(yàn)結(jié)果采用雙因素方差分析(ANalysis of VAriance，ANOVA)技術(shù)進(jìn)行分析。采用ANOVA進(jìn)行統(tǒng)計(jì)分析需要滿足3個(gè)基本假設(shè)：正態(tài)性(normality)、方差齊性(homogeneity of variance)以及獨(dú)立性(independence)，實(shí)驗(yàn)數(shù)據(jù)的殘差分析表明這些假設(shè)均是有效的。改進(jìn)IG算法的ANOVA結(jié)果如表3所示。根據(jù)統(tǒng)計(jì)學(xué)理論，F(xiàn)值越大，則對(duì)應(yīng)因子的影響就越顯著，P值給出了對(duì)應(yīng)因子的最小顯著性水平，P值小于0.05表明對(duì)應(yīng)因子的影響是顯著的。由表3可見，參數(shù)λ對(duì)改進(jìn)IG算法性能的影響在統(tǒng)計(jì)學(xué)意義上是顯著的，但是參數(shù)ω對(duì)算法性能的影響并不顯著。此外，參數(shù)λ和ω之間的交互作用對(duì)改進(jìn)IG算法性能的影響也不顯著。

表3 改進(jìn)IG算法參數(shù)設(shè)置實(shí)驗(yàn)的ANOVA結(jié)果

為了更好地分析參數(shù)λ和ω對(duì)改進(jìn)IG算法性能的影響，圖8給出了各參數(shù)取不同值時(shí)對(duì)應(yīng)RDI均值和95%LSD(least significant difference)置信區(qū)間。根據(jù)統(tǒng)計(jì)學(xué)理論，如果其他因子在不同水平下的置信區(qū)間不重疊，則可認(rèn)為該因子在不同水平下的效果有顯著區(qū)別。由圖8a可見，隨著參數(shù)λ取值的增大，改進(jìn)IG算法的性能顯著下降，參數(shù)λ取值為1要顯著優(yōu)于取值為2、3和4。圖8b表明參數(shù)ω取不同值時(shí)并未產(chǎn)生統(tǒng)計(jì)意義上的顯著差異，但改進(jìn)IG算法的平均性能在參數(shù)ω取值為6時(shí)要略優(yōu)于其取值。因此，根據(jù)改進(jìn)IG算法參數(shù)設(shè)置實(shí)驗(yàn)的ANOVA結(jié)果，改進(jìn)IG算法的參數(shù)可以設(shè)置為λ=1和ω=6。

4.3 改進(jìn)IG算法的有效性與魯棒性分析

為了檢驗(yàn)改進(jìn)IG算法的有效性，將其與經(jīng)典IG算法(記為IG_RSLS)[22]進(jìn)行對(duì)比分析。首先對(duì)經(jīng)典IG算法進(jìn)行改編，以適應(yīng)求解PSS訂單調(diào)度問題的需要，包括編碼和解碼方法、初始解產(chǎn)生方法和終止條件均采用本文提供的方法，以保證對(duì)比的公平性；但是經(jīng)典IG算法中的局部搜索方法、擾動(dòng)算子和接受準(zhǔn)則這3個(gè)主要組成部分均保留不變?；诮?jīng)典IG算法，分別采用本文所提改進(jìn)策略對(duì)上述3個(gè)主要組成部分進(jìn)行改進(jìn)，從而得到3種部分改進(jìn)的IG算法，分別記為IG_RSRNS、IG_RSDOC和IG_RSRWS。將經(jīng)典IG算法、3種部分改進(jìn)的IG算法和完整改進(jìn)的IG算法作為參與比較的算法，以分別檢驗(yàn)每種改進(jìn)策略的有效性。分別采用上述5種IG算法求解基準(zhǔn)測(cè)試算例集，每個(gè)算例運(yùn)算5次。

基于實(shí)驗(yàn)數(shù)據(jù)，繪制各個(gè)IG算法的RDI均值和95%LSD置信區(qū)間，如圖9所示。由圖9可見，IG_RSRNS、IG_RSDOC和IG_RSRWS算法的RDI均值分別領(lǐng)先IG_RSLS算法約38%、60%和6%，表明DOC擾動(dòng)算子對(duì)經(jīng)典IG算法性能提升的改進(jìn)效果最好，其次是RNS局部搜索算法，最后是RWS接受準(zhǔn)則；此外，這些改進(jìn)IG算法的優(yōu)化性能均優(yōu)于經(jīng)典IG算法，表明本文所提出的RNS局部搜索算法、DOC擾動(dòng)算子和RWS接受準(zhǔn)則3種改進(jìn)策略都是非常有效的。特別地，MIG算法的RDI均值相比IG_RSLS算法領(lǐng)先了約94%，表明MIG算法的改進(jìn)是非常成功的；而且，MIG算法的求解效果相比IG_RSRNS、IG_RSDOC和IG_RSRWS算法都要好，說明本文所提出的各種改進(jìn)策略之間具有較好的兼容性和協(xié)同性。

為了考察MIG算法對(duì)算例的關(guān)鍵參數(shù)n、m、l和θ的敏感性，圖10～圖13分別描述了MIG算法關(guān)于這些參數(shù)的變化趨勢(shì)。由圖10可見，隨著訂單規(guī)模的增大，MIG算法的RDI均值逐漸下降，而IG_RSLS算法的RDI均值卻逐漸上升，表明在求解較大規(guī)模的PSS訂單調(diào)度問題時(shí)，改進(jìn)IG算法相比經(jīng)典IG算法更有優(yōu)勢(shì)。由圖11和圖12可見，生產(chǎn)線數(shù)量和安裝隊(duì)數(shù)量的變動(dòng)對(duì)MIG算法性能的影響較小，表明MIG算法對(duì)這兩個(gè)算例參數(shù)具有較好的魯棒性。在圖13中，參數(shù)θ的值越大，意味著各訂單的最早允許服務(wù)時(shí)間越分散。圖13同樣表明，MIG算法的性能對(duì)于最早允許服務(wù)時(shí)間的波動(dòng)同樣具有較好的魯棒性。

上述實(shí)驗(yàn)結(jié)果表明相比經(jīng)典IG算法，MIG算法在求解各種規(guī)模(尤其是較大規(guī)模)和不同特征的PSS訂單調(diào)度問題時(shí)具有更好的性能和較好的魯棒性，因此可以作為決策者解決此類問題的有效求解工具。

5 結(jié)束語

本文針對(duì)擁有多條生產(chǎn)線和多支安裝團(tuán)隊(duì)的服務(wù)型制造企業(yè)，考慮客戶規(guī)定訂單交付的最早允許服務(wù)時(shí)間，以最小化所有訂單交付時(shí)間總和為目標(biāo)構(gòu)建了PSS訂單調(diào)度問題的數(shù)學(xué)模型，并根據(jù)問題特點(diǎn)設(shè)計(jì)了求解問題的改進(jìn)IG算法。該算法的主要?jiǎng)?chuàng)新在于：開發(fā)了一種高效的隨機(jī)鄰域搜索算法作為局部搜索方法，提出了一種破壞、優(yōu)化與重建過程作為擾動(dòng)算子，并基于輪盤賭的選擇策略設(shè)計(jì)了一種新的接受準(zhǔn)則。通過仿真測(cè)試驗(yàn)證了IG算法改進(jìn)策略的有效性，并分析了關(guān)鍵參數(shù)對(duì)算法性能的影響，發(fā)現(xiàn)改進(jìn)IG算法不但性能優(yōu)異而且具有較好的魯棒性。本文的研究可以為服務(wù)型制造企業(yè)的PSS訂單調(diào)度決策者提供高效的優(yōu)化建模與求解工具，從而有助于企業(yè)提高客戶服務(wù)水平和實(shí)現(xiàn)降本增效。未來可進(jìn)一步研究具有多個(gè)優(yōu)化目標(biāo)的PSS訂單調(diào)度問題，以及如何設(shè)計(jì)更加有效的元啟發(fā)式算法對(duì)相關(guān)問題進(jìn)行求解。