制造信息物理系統資源配置優化分析

武善玉 李云鶴

引言

制造業對于社會、經濟、環境都有著重大的影響。隨著技術的更新，具有高計算能力、通信能力和控制能力的智能化制造設備將成為制造系統新的設備資源。信息物理系統（Cyber-Physical Systems——CPS）[1～5]正是為了解決新型智能物理設備互聯問題而提出的，它實現計算資源和物理資源的緊密結合與協同[6]。何積豐院士認為“下一代工業是建立在CPS之上，將來CPS技術的發展和普及，將使得用計算機和網絡實現功能擴展的物理設備無處不在” [7]。M-CPS匯聚不同工廠、地域的制造資源，使用多任務加工與運輸協同調度思想解決多任務請求下的全局資源統籌分配問題[8]，理論上可以獲得全局最優的資源配置方案。本文研究在相近地域范圍內，可忽略運輸時間的多任務調度問題，但可用服務數量可能少于任務數量，即資源受限條件下面向多任務的資源配置優化問題（Resource-constrainded Multi-task Scheduling Problem， RCMTSP）。

一、RCMTSP問題描述

1.1問題及假設條件

N個同類型任務 同時請求服務，將該類任務分解后，任務Ti由n個子任務組成，其中括號{}表示串行結構模式，[]表示并行結構模式。

集合T中每個任務的第j個子任務屬于同類型子任務，組成一個集合。系統根據服務提供者的地理位置信息，為集合T* j選出同一地域范圍內可用的服務組成可用服務集，其中Sj，k是可用服務集中的第k個服務，mj是可用服務集中服務的個數。T* j中的每個子任務將在SVRj中選取合適的服務完成加工操作。任意兩個服務間的運輸環節可忽略。

問題的相關假設如下：

1）所有任務類型相同，具有相同的加工過程;

2） 可用服務是相近地域內的提供者提供的;

3） 同一個任務的鄰接子任務間是嚴格有序的;

4） 一個服務同一時刻只能為一個子任務提供服務;

5） 子任務開始處理后，直到處理結束才釋放占用的服務;

6） 為每個子任務集合T * j構建的可用服務集SVRj中的服務數量可能少于子任務數量。

1.2優化目標

優化目標包括：

F1： 所有任務的最大完成時間;F2： 所有任務的平均完成時間;F3： 各關鍵服務的總負載;F4： 所有服務集的平均負載之和。

任務Ti的完成時間ti由其所有子任務的加工時間和子任務等待處理時的等待時間構成。對任意滿足強時序約束的子任務Ti（j-1）和Tij，其完成時間可根據公式（2）計算，而對于任意一個并行子任務集，完成時間為其中所有子任務完成時間的最大值，即：。

二、 MOHSA-DPSO算法框架

RCMTSP問題與柔性車間作業調度問題 （FJSP） [9～13]具有某些相似之處，即二者都包含兩個子問題——路徑子問題和排序子問題，不同之處在于：FJSP問題解決的是一組工件和對應的一組機器間的資源分配問題，而RCMTSP包含多組（多階段）子任務，且每組子任務對應一組數量較多的可用服務。

針對問題離散、大規模等特征，提出多目標混合模擬退火-離散粒子群（MOHSA-DPSO）算法，將模擬退火算法與離散粒子群算法混合，并對粒子編碼、解碼、種群初始化、種群更新、鄰域搜索、非劣解集維護等環節進行了詳細設計。

2.1粒子編碼

RCMTSP問題的一個解決方案需要表達出兩個方面的信息：①服務分配;②同一服務上的子任務排序。分別采用服務分配矩陣Xh和子任務序列矩陣Oh表示上述兩種信息。服務分配矩陣Xh是n行N列的矩陣，行號表示子任務階段，列號表示任務序號，矩陣元素xhji∈[1，mj]表示子任務Tij分配到的服務編號。其中h表示種群中第h個粒子。子任務序列矩陣Oh同樣為n行N列，ohji∈[1，N]表示子任務排序，即在同階段子任務中的優先順序，對于分配到同一個服務上的兩個子任務來說，在該服務上的處理順序按照優先級由高到低進行。

2.2解碼

對于多目標問題的解碼方法，本文算法按行解析粒子Ph的子任務序列矩陣Oh和服務分配矩陣Xh，按照同一行中子任務的優先級順序依次選取元素ohji，其值記為b=ohji，及其在Xh中對應的服務編號xhjb;重復確定子任務Tbj的開始時間t s bj和完成時間t? e bj? ，以及服務Sj，k的負載時間tw j，k（任意一個服務的負載初始值為0）。對粒子h解析完畢后，計算出粒子對應的各目標值。

2.3算法基本步驟

MOHSA-DPSO算法基本步驟如下：

第1步，種群初始化：產生初始的粒子;

第2步，設初始種群為當前種群;

第3步，計算各粒子對應的目標函數向量，對每個粒子進行評價，根據評價結果決定是否更新粒子的個體最優位置;選取非劣解更新全局非劣解集檔案;

第4步，為每個粒子選取全局最優位置;

第5步，判斷終止條件，若滿足則算法終止;否則更新粒子的位置，并返回到第3步。

三、多目標混合粒子群優化算法MOHSA-DPSO

3.1種群初始化

初始種群對算法性能有著極大的影響。同時考慮接近最優解和粒子多樣性兩個問題，本文算法采用以下幾種規則產生初始種群。

（1）采用三類經驗法則產生初始粒子。最短子任務加工時間法則;最長子任務加工時間法則;最短交貨期優先法則。

（2）采用完全隨機方法：每個階段子任務隨機排序，并將此排序作為優先級排序，將子任務按優先順序分配到當前加工時間最短的服務上。

（3）先到先服務方法：將第一階段子任務進行排序和服務分配，第二階段按照第一段子任務完成時間從小到大排列，并將此排序作為優先級排序，并分配到當前加工時間最短的服務上。其他階段依此類推。

以上幾種方法同時使用，分別承擔種群中一部分粒子的生成，比如三大類方法分別用于40%、20%、40%粒子的生成，其中第一類方法中的三種法則分別用于產生20%、10%、10%的粒子;采用“先到先服務方法”的粒子中第一階段子任務分配規則采用不同法則的比例分別為10%。

3.2種群更新策略

本文MOHSA-DPSO中，粒子的更新分成“交叉”和“變異”兩類操作。其中“交叉”操作依賴粒子的歷史最優位置和全局最優位置，粒子的速度依賴于粒子與兩個最優位置的相似度，表示粒子向二者前進的可能性。變異操作則是為了避免早熟收斂而針對RCMTSP特定問題特點提出的對傾向停滯的粒子采用的干擾機制。

（1）更新子任務序列矩陣。

MOHSA-DPSO算法中，每個粒子的更新包含兩個方面：更新子任務序列和更新服務分配。子任務序列的更新：對于第α代種群中的粒子Pα h的子任務序列矩陣Oα h的更新是按行從上到下進行的。

（2）更新服務分配矩陣。

對于粒子的服務分配矩陣的更新按行從上到下進行的，并且同樣依賴于相似度概念，但對于歷史最優位置和全局最優位置的繼承將分別取決于粒子與兩者各自的相似度。

（3）變異操作。

為了避免早熟收斂，本文算法使用干擾機制對傾向停滯的粒子進行變異操作。停滯狀態的識別基于粒子局部最優位置沒有被刷新的連續最大代數gmax，變異概率設為（gh/gmax），其中gh表示到目前為止粒子局部最優位置沒有刷新的進化代數。

（4）鄰域搜索。

本文算法采用模擬退火算法對新種群進行鄰域搜索。模擬退火算法是一種模擬固體物質退火過程的啟發式隨機搜索算法，廣泛應用于求解組合優化問題。算法從一較高溫度開始，隨著逐漸冷卻，在解空間中隨機尋找全局最優解，并以按某種規律變化的概率接受較差的新狀態而避免算法陷入局部最優。

本文使用模擬退火算法對當前解作鄰域搜索，即對當前解做小的局部調整產生一個新的解，為了使算法能夠跳出局部最優，以隨溫度Tc變化的概率接受較差的新解。算法基本思想為：對于粒子，產生其鄰域內的新解，判斷二者之間的優劣關系，如果新解支配初始解則接受新解，否則以與當前溫度Tc相關的概率exp（-Δ/Tc）接受新解。

3.3選取非劣解

本文提出的MOHSA-DPSO算法使用一個Pareto非劣解集檔案保存搜索到的非劣解。每次粒子更新后，都要判斷是否非劣解，根據判斷結果對檔案進行更新。更新的步驟如下：

（1）將新解與當前Pareto非劣解集檔案中的解進行比較，判斷新解是否非劣解;

（2）根據判斷結果對檔案進行更新：

①新解與檔案中的某個解相同：放棄新解，更新結束;

②新解被檔案中的一或多個解支配：放棄新解，更新結束;

③新解支配檔案中的解：將新解加入檔案，同時刪除檔案中被新解支配的所有解，更新結束;

④新解與檔案中的任何解互不支配：將新解加入檔案，更新結束。

3.4更新粒子個體最優位置

當前種群中任一個粒子更新后產生一個新的解，這個解與其個體最優位置Pbh之間的關系決定了Pbh的更新。根據支配概念的定義，粒子每次更新后如果支配Pbh，則用更新Pbh，否則Pbh不變。

3.5選擇粒子全局最優位置

每次迭代后，需要從非劣解集檔案中為當前粒子選擇一個全局最優位置。OHSA-DPSO算法中，為當前粒子選擇全局最優位置是依據粒子之間的擁擠度來進行的。擁擠度基于兩個粒子之間的距離，用于衡量粒子的擁擠程度。粒子Ph與Ph之間的擁擠度與兩個因素相關：粒子間的歐氏距離和漢明距離。其中粒子Ph與Ph間的歐氏距離，兩者間的漢明距離為兩個粒子位置矩陣對應元素不相同的個數，而擁擠度是上述兩個距離規一化之后的平均值。計算當前粒子與非劣解集檔案中任意粒子之間的擁擠度，選擇擁擠度最大的粒子作為當前粒子的全局最優位置。

3.6混合算法流程

模擬退火算法與粒子群算法混合在一起，粒子群算法迭代次數由模擬退火算法的溫度控制，而種群更新產生的粒子則由模擬退火算法作進一步優化。算法總體流程如下：

（1）參數初始化：初始化種群規模SwarmSize、初始溫度T0、終止溫度Tend、溫度調整參數B及其他相關參數;

（2）產生初始種群：

1、根據3.1的方法產生初始種群Swarm（0）;

2、對每個粒子進行解碼并計算各粒子對應的目標函數向量，用模擬退火算法對每個粒子進行鄰域搜索;

3、對每個粒子進行評價，根據評價結果決定是否更新粒子的個體最優位置;

4、選取非劣解更新全局非劣解集檔案;

5、為每個粒子選取全局最優位置;

（3）種群更新：在滿足T0

1、根據粒子自身位置、個體最優位置、全局最優位置更新粒子;

2、在滿足KL

3、對粒子進行評價，根據評價結果決定是否更新粒子的個體最優位置;

4、選取非劣解更新全局非劣解集檔案;

5、為粒子選取全局最優位置;

（4）輸出優化結果。

四、小結

本文研究了在同一地域范圍內、可忽略運輸時間、但可用服務數量可能少于任務數量的多任務調度問題，即資源受限條件下面向多任務的資源配置優化問題（RCMTSP），提出了面向RCMTSP問題的多目標混合模擬退火-離散粒子群算法 MOHSA-DPSO。

針對問題的離散特性，同時為了提高算法的搜索能力，本文將SA嵌入到離散PSO算法框架中;由于RCMTSP問題規模較大，不易求解，因此對種群初始化方法進行了深入研究，使用多種經驗法則產生盡可能接近最優解的初始種群。 與經典的求解FJSP問題的類似群智能算法相比，在兩個較為典型的不同規模的實例中，本文提出的算法具有較好的搜索能力。

參? 考? 文? 獻

[1] LEE E A. Cyber Physical Systems： design challenges[C]. Proceeding of the 11th IEEE international symposium on object oriented real-time distributed computing. Los Alamitos， CA： IEEE Computer Society， 2008：363-369

[2] KLESH A T， CUTLER J W， ATKINS E M. Cyber-physical challenges for space systems [A]. 2012 IEEE/ACM third international conference on cyber-physical systems [C]. Beijing， China： IEEE/ACM， 2012：45-54

[3] Tan Y， Goddard S， Prez L C. A prototype architecture for cyber-physical systems[J]. ACM SIGBED Review， 2008， 5（1）： Article No. 26

[4] 李建中， 高宏， 于博. 信息物理融合系統（CPS）研究進展[C]. 2009中國計算機科學技術發展報告， 北京： 機械工業出版社， 2010： 1-20

[5] Huang Ben-xiong. Cyber physical systems： A Survey[R]. Stavanger： Smart Home Workshop， 2008.

[6] NSF Directorate for computer & information science & engineering. NSF Directorate for engineering. Cyber-Physical Systems （CPS） [EB/OL]. available： http：//www.nsf.gov/pubs/2011/nsf11516/nsf11516.htm. 2011.

[7] 何積豐.Cyber-physical systems [J]. 中國計算機學會通訊， 2010， 6（1）： 25-29

[8] WU Shan-yu， ZHANG Ping， LI Fang， GU Feng， PAN Yi. A hybrid discrete particle swarm optimization-genetic algorithm for task scheduling problem in service oriented manufacturing systems[J]. Journal of Central South University， 2016，23（2）： 421-429

[9] PEZZELLA F，MORGANTI G，CIASCHETTI G. A genetic algorithm for the flexible job-shop scheduling problem[J]. Computers & Operations Research， 2008， 35 （10）：3202–3212

[10] Driss I， Mouss KN， Laggoun A. A new genetic algorithm for flexible job-shop scheduling problems[J]. Journal of Mechanical Science and Technology， 2015， 29（3）： 1273-1281

[11] Yuan Y， Xu H. An integrated search heuristic for large-scale flexible job shop scheduling problems[J]. Computers & Operations Research， 2013， 40（12）： 2864-2877

[12] Brandimarte P. Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research， 1993， 41（3）：157–183

[13] Gao K Z，? Suganthan P N，? Pan Q K， et al. Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling[J]. Information Sciences， 289（24）： 76-90