基于混合策略改進的貪心算法PSS訂單調(diào)度研究

任春慧

（上海工程技術(shù)大學 管理學院，上海 201620）

0 引言

隨著現(xiàn)代化經(jīng)濟的發(fā)展，市場同類型產(chǎn)品的競爭不斷加劇，如何在更好地滿足客戶的個性化需求的條件下，降低生產(chǎn)成本，提高資源的利用率和減少環(huán)境污染，將制造業(yè)向綠色智能、服務(wù)信息化轉(zhuǎn)型升級，是許多企業(yè)現(xiàn)在及未來的發(fā)展方向。

在當今社會服務(wù)化生產(chǎn)的模式下，制造生產(chǎn)型企業(yè)把產(chǎn)品和服務(wù)相結(jié)合提出產(chǎn)品服務(wù)系統(tǒng)（Product Service System，PSS）。對于PSS的研究，Bu等人創(chuàng)建VR平臺將收集并處理用戶生成的數(shù)據(jù)和VR系統(tǒng)生成的數(shù)據(jù)，實現(xiàn)VR輔助的用戶體驗和實時數(shù)據(jù)反饋的增值服務(wù)。Mariusz等人改變PSS原有的基于銷售和產(chǎn)品所有權(quán)從制造商轉(zhuǎn)移到用戶的商業(yè)模式，允許銷售產(chǎn)品提供的可訪問性和功能，為印刷行業(yè)提供更大發(fā)展空間。Kang等人在物流行業(yè)采用PSS的基礎(chǔ)上定義和闡述了LPSS，提出了多單位維克拍賣和單面Vickrey-Clarke-Groves（O-VCG）組合拍賣并研究了對應(yīng)的相關(guān)屬性，包括激勵相容性、分配效率、預(yù)算平衡和個人理性。Zhang等人提出了一個基于設(shè)計中心復(fù)雜性（DCC）理論的可持續(xù)PSS開發(fā)框架，采用DCC理論確定系統(tǒng)的復(fù)雜性類型，結(jié)合TRIZ子域模型對問題進行轉(zhuǎn)換和求解并建立泛函周期性，降低系統(tǒng)復(fù)雜度，保持系統(tǒng)的長期運行穩(wěn)定性。Haber等人通過Kano模型增強了PSS質(zhì)量功能部署方法以篩選客戶需求并將有吸引力的需求轉(zhuǎn)化為接收器狀態(tài)參數(shù)，將模糊層次分析法集成到該過程中評估這些參數(shù)及其固有的不確定性。Li等人針對存在個性化需求的客戶，設(shè)計了塊結(jié)構(gòu)的馬爾可夫鏈優(yōu)化模型，較好地解決PSS問題。上述文獻均對生產(chǎn)服務(wù)調(diào)度的運營及其管理模式進行了探討并具有可參考價值，但并未提及到同時間大量PSS訂單的調(diào)度問題，究其根源性問題是如何協(xié)調(diào)PSS訂單的制造生產(chǎn)和滿足客戶的服務(wù)需求，達到服務(wù)效率和效果最優(yōu)化。

為此，本文將研究產(chǎn)品服務(wù)系統(tǒng)訂單調(diào)度問題，以一家有多條生產(chǎn)線和多支安裝團隊的服務(wù)型制造企業(yè)為研究對象，在滿足客戶個性化需求的同時，尋求訂單交付時間的最小化，構(gòu)建數(shù)學模型，基于貪心算法求解問題，最后仿真實驗驗證。

1 問題描述

假設(shè)面向市場服務(wù)型制造企業(yè)｛1，2，…，｝，擁有條生產(chǎn)線和支安裝團隊，需要滿足客戶的PSS訂單需求，如圖1所示。從規(guī)劃期開始即在零點，企業(yè)接到一組訂單，其中包括來自個PSS訂單的訂單集｛1，2，…，｝。 在這種情況下，每個訂單包含一個產(chǎn)品單元和相應(yīng)的安裝服務(wù)，并指定客戶要求的第一個授權(quán)服務(wù)時間，在此之前，客戶由于各種原因（如缺乏安裝條件）無法獲得服務(wù)。

圖1 PSS訂單交付流程Fig.1 PSS order delivery process

PSS訂單調(diào)度問題的研究重點是協(xié)調(diào)生產(chǎn)與服務(wù)之間的平衡，尋求最優(yōu)的調(diào)度方案。對于服務(wù)型制造產(chǎn)業(yè)，因為產(chǎn)品和服務(wù)之間存在時間上的差異，服務(wù)需要以產(chǎn)品為媒介得到體現(xiàn)，且兩者之間存在相互約束，所以如何協(xié)同規(guī)劃生產(chǎn)調(diào)度已然成為亟需解決的研究課題。

2 生產(chǎn)服務(wù)模型

2.1 模型假設(shè)

（1）訂單的生產(chǎn)和服務(wù)時間確定且已知。

（2）不同生產(chǎn)線上生產(chǎn)同一訂單的時間相等，且不同安裝隊伍的服務(wù)時間也相同。

（3）每個生產(chǎn)線和安裝隊伍不能同時生產(chǎn)和服務(wù)不同任務(wù)。

（4）生產(chǎn)和服務(wù)任務(wù)都能完成。

2.2 數(shù)學模型

首先，定義以下符號和變量：

，為訂單編號；為生產(chǎn)線（安裝團隊）編號；為生產(chǎn)階段；為服務(wù)階段；pt表示訂單的生產(chǎn)時間；st表示訂單的服務(wù)時間；e為訂單的最早授權(quán)服務(wù)時間；表示足夠大的正數(shù)；STP為訂單的生產(chǎn)開始時間，CTP為訂單的生產(chǎn)結(jié)束時間；STS為訂單的服務(wù)開始時間；CTS為訂單的服務(wù)結(jié)束時間；y表示訂單的任務(wù)分配給生產(chǎn)線（安裝團隊），則y＝1，否則，y＝0；x表示訂單的任務(wù)分配給生產(chǎn)線（安裝團隊），且訂單早于訂單，則x＝1；否則，x＝0；

PSS訂單調(diào)度問題的數(shù)學模型如下：

（1）為得到訂單最小交付時間的總和，目標函數(shù)為：

（2）在生產(chǎn)產(chǎn)品時，過程不能被打斷、即不間歇生產(chǎn)：

（3）在生產(chǎn)過程中，同一條生產(chǎn)線有且只有一項生產(chǎn)任務(wù)在執(zhí)行：

（4）生產(chǎn)的開始時間不能早于結(jié)束時間：

（5）同一訂單的服務(wù)開始時間不能早于其最早授權(quán)服務(wù)時間：

（6）服務(wù)在提供過程中必須是連續(xù)不間斷：

CTS＝STS＋st?∈（6） （7）同一時刻每支安裝隊伍不能同時服務(wù)不同任務(wù)：

（8）每條生產(chǎn)線的生產(chǎn)任務(wù)執(zhí)行次序，以及每支安裝團隊的服務(wù)任務(wù)執(zhí)行次序：

（9）每個訂單的生產(chǎn)任務(wù)必須被分配給一條生產(chǎn)線，服務(wù)任務(wù)必須被分配給一支安裝團隊：

（10）各決策變量的取值范圍：

3 算法改進

在屬于較大規(guī)模NP-hard問題的情況下，需要借助有效的智能算法求解模型。迭代貪心算法（Iterated Greedy，IG）是Ruiz等人提出的一種新型智能優(yōu)化算法，該算法主要由鄰域搜索、擾動算子和接受準則三個基本部分組成。IG算法被提出后，因其便于實現(xiàn)、效率高而受到國內(nèi)外學者的關(guān)注和研究，并已廣泛應(yīng)用于約束車間流水調(diào)度、傳感器網(wǎng)絡(luò)覆蓋增強問題研究等領(lǐng)域。

本文提出了一種混合策略改進的IG算法，可以用來求解PSS訂單調(diào)度問題。首先，對訂單進行排序，然后初始化訂單序列，運用改進的鄰域搜索，迭代尋找最優(yōu)解并不斷替換，再對擾動算子重新進行破壞和重建，防止過早收斂。最后，根據(jù)輪盤賭設(shè)計出一套新的接受準則更新最優(yōu)解，直到算法運行結(jié)束。

3.1 初始化

本文利用Nawaz-Enscore-Ham（NEH）算法對IG初始化加以改進，通過NEH算法對所研究的訂單最早授權(quán)服務(wù)時間重新進行排序，獲得一個數(shù)列。首先選擇數(shù)列中時間之和較短的前2個訂單調(diào)度為基本序列，然后其他訂單分別調(diào)入基本序列，選擇最短時間和的序列為新的基本序列，接著重復(fù)以上步驟并不斷調(diào)整基本序列，最后會獲得一個新的數(shù)列。

3.2 鄰域搜索

本文為增強IG算法的尋優(yōu)能力，根據(jù)隨機搜索和交換鄰域的思想，提出一種隨機鄰域搜索（Random Neighborhood Search，RNS）算法，其思路主要如下：每次在當前解之中隨機選取一個個體，而后再隨機插入其任何可能最優(yōu)預(yù)測的區(qū)域，或者將個體與最優(yōu)位置的個體進行位置互換，一旦新解優(yōu)于原解，則保留新解并重復(fù)上述過程、直至不再生成較高解。這個方式能夠大幅增加搜尋的范圍并提高尋優(yōu)效果。

3.3 破壞與重建

為了避免IG算法在求解過程中陷入局部最優(yōu)，需要對其運行過程進行破壞與重建、跳出原有機制，又稱為擾動算子。原始IG算法的擾動算子在發(fā)生作用之后，可能會發(fā)生丟失局部最優(yōu)解的情況，為此本文 提 出 一 種 結(jié) 合 破 壞（Destruction）、優(yōu) 化（Optimization）和重建（Construction）過程（DOC）作為改進IG算法的擾動算子，其操作過程如下：在實施破壞過程后，將得到的解重新進行多次鄰域搜索得到優(yōu)化解，此后再對其進行重建，提升了擾動解的優(yōu)良性。

3.4 閾值接受準則

為實現(xiàn)IG算法更快找出最好解這一目的，本文提出一種基于輪盤賭選擇（Roulette Wheel Selection，RWS）策略的接受準則。根據(jù)求解問題的特點，設(shè)計一個優(yōu)選表，在優(yōu)選表中依次添加局部搜索產(chǎn)生的較優(yōu)解，當達到表的最大長度時刪除表中原有最差解，最后利用RWS選擇表中解。設(shè)置優(yōu)選表長（≤），對RWS選擇策略步驟可給出闡釋分述如下。

對優(yōu)選表中的解進行歸一化處理：

步驟3 在［0，1］中選擇隨機數(shù)。 如果，則選擇優(yōu)選表中第一個解；否則，選擇表中第個解，使得q≤Rand＜q成立。

3.5 終止條件

考慮到問題規(guī)模，保證算法充分收斂，本文設(shè)置改進IG算法的終止條件為10*ms。

3.6 算法流程

研發(fā)后得到的整個算法的求解流程具體如下。

4 仿真實驗

4.1 算例構(gòu)造與性能評價指標

本文從測試集合中隨機選擇測試算例。設(shè)置pt和st由區(qū)間1，100[ ]的均勻分布隨機產(chǎn)生，e由區(qū)間［pt，（1）pt］均勻分布隨機產(chǎn)生。實驗中關(guān)鍵參數(shù)的取值從108種參數(shù)集合中選取，｛50，100，150，200｝、｛2，5，10｝、｛2，3，5｝和｛1，2，3｝。 每個參數(shù)序列隨機產(chǎn)生2個算例，最后可形成216個基準測試集合。

使用相對偏差指數(shù)（relative deviation index，）評價IG的能力：

4.2 實驗參數(shù)設(shè)置

設(shè)置50個算例，每個算例通過選擇｛20，50，80，100，120，150，180，200｝以及、和集合中隨機值。MIG算法主要測試和，設(shè)置：｛1，2，3，4｝和｛5，6，7，8｝。測試結(jié)果分別取運行5次后的平均值。

運用雙因素方差分析所得結(jié)果，見表1。當值比0.05小的時候，代表著對應(yīng)因子的影響顯著。由表1可見，對MIG影響顯著，而對MIG則表現(xiàn)出較為明顯的影響性。并且在和同時產(chǎn)生作用的情況下，對MIG的性能影響也不明顯。

表1 MIG算法參數(shù)設(shè)置實驗的ANOVA結(jié)果Tab.1 ANOVA results of MIG algorithm parameters setting experiment

為進一步研究和對MIG算法的影響，對參數(shù)選取不同值得到均值和95%LSD置信區(qū)間，如圖2所示。由圖2可以看出，MIG的性能隨著的增大而下降，而對MIG的影響并不顯著。取1，6。

圖2 λ和ω分別取不同值時改進IG算法置信區(qū)間Fig.2 Improved confidence interval of IG algorithm when λ and ω take different values respectively

4.3 有效性與魯棒性分析

將混合策略改進的貪心算法分別與經(jīng)典IG算法、隨機鄰域改進的貪心算法（IGRNS）、擾動算子改進的貪心算法（IGDOC）、輪盤賭改進接受策略的貪心算法（IGRWS）進行對比實驗，分別測試不同改進策略效果。

IG算法改進的RDI均值和95% LSD置信區(qū)間圖如圖3所示。由圖3可以看出本文提出的改進策略對于提升貪心算法的性能均是有效的，MIG效果最為明顯，值優(yōu)于IG約為84%。同時，IGRNS的值優(yōu)于IG算法約35%，IGDOC的值優(yōu)于IG算法約58%，IGRW算法的值優(yōu)于IG算法約5%，明顯地，破壞重建過程中的擾動算子對算法性能的影響最為顯著。

圖3 IG算法改進的RDI值Fig.3 Improved RDI value of IG algorithm

MIG算法對求解算例中的具有關(guān)鍵性作用的參數(shù)敏感性變化趨勢如圖4～圖7所示。

由圖4可以看出，隨著的增加，MIG的均值呈現(xiàn)明顯的減小，而IG的均值持續(xù)上漲，這反映了MIG算法對于求解更加龐大、及復(fù)雜調(diào)度類型問題的效果會更為準確。由圖5和圖6可見，MIG的值幾乎不隨著和的增加而波動，這反映了生產(chǎn)產(chǎn)品的流水線數(shù)量和安裝團隊數(shù)量的增加幾乎不會降低MIG算法性能，反映了MIG對和的魯棒性能較優(yōu)。在圖7中，隨著的增大，各訂單的最早授權(quán)服務(wù)時間就越分散，并同樣反映出MIG較優(yōu)的魯棒性。

圖4 MIG關(guān)于n的變化趨勢Fig.4 Variation trend of MIG on n

圖5 MIG關(guān)于l的變化趨勢Fig.5 Variation trend of MIG on l

圖6 MIG關(guān)于m的變化趨勢Fig.6 Variation trend of MIG on m

圖7 MIG關(guān)于θ的變化趨勢Fig.7 Variation trend of MIG on θ

5 結(jié)束語

本文面向具有數(shù)條產(chǎn)品生產(chǎn)流水線和安裝隊伍的生產(chǎn)服務(wù)型企業(yè)，可以為客戶推薦較為合適的訂單交貨前的最早授權(quán)服務(wù)日期，減少不必要的等待時間，尋求最短交貨時間，建立了標準數(shù)學模型，并針對PSS訂單調(diào)度問題特點設(shè)計了求解問題的混合策略改進IG算法。通過仿真測試，證明了IG算法改進策略的有效性和魯棒性。本文提出的PSS訂單調(diào)度模型及IG算法混合改進策略求解方法可以為企業(yè)決策提供有效的決策建議，為消費者提高服務(wù)水平降低成本。在未來的研究中可以將本文方法推廣到汽車制造，交通調(diào)度等行業(yè)中。