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

任春慧

（上海工程技術大學 管理學院，上海 201620）

0 引言

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

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

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

1 問題描述

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

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

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

2 生產服務模型

2.1 模型假設

（1）訂單的生產和服務時間確定且已知。

（2）不同生產線上生產同一訂單的時間相等，且不同安裝隊伍的服務時間也相同。

（3）每個生產線和安裝隊伍不能同時生產和服務不同任務。

（4）生產和服務任務都能完成。

2.2 數學模型

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

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

PSS訂單調度問題的數學模型如下：

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

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

（3）在生產過程中，同一條生產線有且只有一項生產任務在執行：

（4）生產的開始時間不能早于結束時間：

（5）同一訂單的服務開始時間不能早于其最早授權服務時間：

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

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

（8）每條生產線的生產任務執行次序，以及每支安裝團隊的服務任務執行次序：

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

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

3 算法改進

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

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

3.1 初始化

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

3.2 鄰域搜索

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

3.3 破壞與重建

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

3.4 閾值接受準則

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

對優選表中的解進行歸一化處理：

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

3.5 終止條件

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

3.6 算法流程

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

4 仿真實驗

4.1 算例構造與性能評價指標

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

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

4.2 實驗參數設置

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

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

表1 MIG算法參數設置實驗的ANOVA結果Tab.1 ANOVA results of MIG algorithm parameters setting experiment

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

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

4.3 有效性與魯棒性分析

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

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

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

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

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

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

圖5 MIG關于l的變化趨勢Fig.5 Variation trend of MIG on l

圖6 MIG關于m的變化趨勢Fig.6 Variation trend of MIG on m

圖7 MIG關于θ的變化趨勢Fig.7 Variation trend of MIG on θ

5 結束語

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