武善玉 李云鶴

引言

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

一、RCMTSP問題描述

1.1問題及假設條件

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

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

問題的相關假設如下：

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

2） 可用服務是相近地域內(nèi)的提供者提供的;

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

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

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

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

1.2優(yōu)化目標

優(yōu)化目標包括：

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

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

二、 MOHSA-DPSO算法框架

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

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

2.1粒子編碼

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

2.2解碼

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

2.3算法基本步驟

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

第1步，種群初始化：產(chǎn)生初始的粒子;

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

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

第4步，為每個粒子選取全局最優(yōu)位置;

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

三、多目標混合粒子群優(yōu)化算法MOHSA-DPSO

3.1種群初始化

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

（1）采用三類經(jīng)驗法則產(chǎn)生初始粒子。最短子任務加工時間法則;最長子任務加工時間法則;最短交貨期優(yōu)先法則。

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

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

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

3.2種群更新策略

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

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

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

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

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

（3）變異操作。

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

（4）鄰域搜索。

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

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

3.3選取非劣解

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

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

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

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

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

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

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

3.4更新粒子個體最優(yōu)位置

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

3.5選擇粒子全局最優(yōu)位置

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

3.6混合算法流程

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

（1）參數(shù)初始化：初始化種群規(guī)模SwarmSize、初始溫度T0、終止溫度Tend、溫度調(diào)整參數(shù)B及其他相關參數(shù);

（2）產(chǎn)生初始種群：

1、根據(jù)3.1的方法產(chǎn)生初始種群Swarm（0）;

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

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

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

5、為每個粒子選取全局最優(yōu)位置;

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

1、根據(jù)粒子自身位置、個體最優(yōu)位置、全局最優(yōu)位置更新粒子;

2、在滿足KL

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

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

5、為粒子選取全局最優(yōu)位置;

（4）輸出優(yōu)化結果。

四、小結

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

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

參? 考? 文? 獻

[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] 李建中， 高宏， 于博. 信息物理融合系統(tǒng)（CPS）研究進展[C]. 2009中國計算機科學技術發(fā)展報告， 北京： 機械工業(yè)出版社， 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