制造信息物理系統(tǒng)資源配置優(yōu)化分析

武善玉 李云鶴

引言

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

一、RCMTSP問題描述

1.1問題及假設(shè)條件

N個(gè)同類型任務(wù) 同時(shí)請(qǐng)求服務(wù)，將該類任務(wù)分解后，任務(wù)Ti由n個(gè)子任務(wù)組成，其中括號(hào){}表示串行結(jié)構(gòu)模式，[]表示并行結(jié)構(gòu)模式。

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

問題的相關(guān)假設(shè)如下：

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

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

3） 同一個(gè)任務(wù)的鄰接子任務(wù)間是嚴(yán)格有序的;

4） 一個(gè)服務(wù)同一時(shí)刻只能為一個(gè)子任務(wù)提供服務(wù);

5） 子任務(wù)開始處理后，直到處理結(jié)束才釋放占用的服務(wù);

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

1.2優(yōu)化目標(biāo)

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

F1： 所有任務(wù)的最大完成時(shí)間;F2： 所有任務(wù)的平均完成時(shí)間;F3： 各關(guān)鍵服務(wù)的總負(fù)載;F4： 所有服務(wù)集的平均負(fù)載之和。

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

二、 MOHSA-DPSO算法框架

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

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

2.1粒子編碼

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

2.2解碼

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

2.3算法基本步驟

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

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

第2步，設(shè)初始種群為當(dāng)前種群;

第3步，計(jì)算各粒子對(duì)應(yīng)的目標(biāo)函數(shù)向量，對(duì)每個(gè)粒子進(jìn)行評(píng)價(jià)，根據(jù)評(píng)價(jià)結(jié)果決定是否更新粒子的個(gè)體最優(yōu)位置;選取非劣解更新全局非劣解集檔案;

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

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

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

3.1種群初始化

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

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

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

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

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

3.2種群更新策略

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

（1）更新子任務(wù)序列矩陣。

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

（2）更新服務(wù)分配矩陣。

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

（3）變異操作。

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

（4）鄰域搜索。

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

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

3.3選取非劣解

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

（1）將新解與當(dāng)前Pareto非劣解集檔案中的解進(jìn)行比較，判斷新解是否非劣解;

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

①新解與檔案中的某個(gè)解相同：放棄新解，更新結(jié)束;

②新解被檔案中的一或多個(gè)解支配：放棄新解，更新結(jié)束;

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

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

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

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

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

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

3.6混合算法流程

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

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

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

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

2、對(duì)每個(gè)粒子進(jìn)行解碼并計(jì)算各粒子對(duì)應(yīng)的目標(biāo)函數(shù)向量，用模擬退火算法對(duì)每個(gè)粒子進(jìn)行鄰域搜索;

3、對(duì)每個(gè)粒子進(jìn)行評(píng)價(jià)，根據(jù)評(píng)價(jià)結(jié)果決定是否更新粒子的個(gè)體最優(yōu)位置;

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

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

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

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

2、在滿足KL

3、對(duì)粒子進(jìn)行評(píng)價(jià)，根據(jù)評(píng)價(jià)結(jié)果決定是否更新粒子的個(gè)體最優(yōu)位置;

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

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

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

四、小結(jié)

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

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

參? 考? 文? 獻(xiàn)

[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）研究進(jìn)展[C]. 2009中國(guó)計(jì)算機(jī)科學(xué)技術(shù)發(fā)展報(bào)告， 北京： 機(jī)械工業(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]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊， 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