云制造環境下的動態調度①

李曉輝,王雪茹,趙 毅,李沛帆,冉保健

(長安大學 電子與控制工程學院,西安 710064)

我國雖然是當今世界上擁有制造資源最豐富的國家,但是資源的有效使用效率低造成了資源的極大浪費,不利于我國制造業的發展.隨著云計算、物聯網、虛擬化等技術的出現,云制造的概念被一些學者提出.云制造是一種基于網絡的,面向服務的智慧化制造新模式手段,它融合發展了現有信息化制造技術與云計算、物聯網、服務計算、智能科學等新興信息技術,將各類制造資源和制造能力虛擬化、服務化,構成制造資源和制造能力的云服務池,進行統一的、集中的優化管理和經營,使得用戶只要通過云端就可以隨時隨地按需獲取制造資源和服務能力,進而智慧的完成其制造全生命周期的各類活動.由于對制造資源和制造能力進行了統一的管理分配,使得資源的利用率大大提高,并且不同資源調度方案對不同資源的使用情況也不同,因此對資源的合理調度成為研究的熱點.由于云平臺任務數量眾多,精確解的獲取非常困難,因此云平臺需要將某一時刻到達的任務集中在一起,通過合適的調度算法確定其優先順序獲得近似解,以此解決云制造調度問題.由于具體的任務執行過程的不確定性,如:緊急任務的到達、由于機器故障等因素導致服務暫停、任務的取消,這些因素會引起云制造系統的重調度,本文旨在解決任務動態調度過程中緊急任務的到達和服務暫停問題.

目前,求解傳統車間調度的方法有精確算法和近似算法.毛志慧等[1]提出一種文化基因非支配排序粒子群算法,旨在優化產品的合格率、縮短生產周期、減少機器的空轉時間.杜兆龍等[2]以粒子群算法為基礎,引入變鄰域搜索方式,提出基于解空間距離聚類和變鄰域搜索的粒子群算法.Ding 等[3]提出了一種改進的粒子群算法來解決柔性作業車間調度問題,并通過改進編解碼方案、粒子之間的通信機制和候選操作機器的交替規則來獲得有益的解決方案,并對編譯碼方案進行了創新,提出了一種新穎的鏈式編碼方案和相應的有效譯碼方案.Chen 等[4]設計一種基于強化學習對關鍵參數進行智能調整的自學習遺傳算法.

與傳統車間調度方法類似,對云系統任務的調度可以采用遺傳算法、粒子群算法等元啟發式算法來獲取最優解.李云龍等[5]針對云制造環境下柔性作業車間調度產生的離散型加工設備的空閑時間利用及其沖突問題,提出了一種基于混合遺傳算法的云制造環境下柔性作業車間調度方案,以最小懲罰總成本為目標,采用了遺傳變鄰域混合算法求解云任務工件最優調度順序.王時龍等[6]考慮服務需求者間存在的利益沖突及重要的服務評價指標,以每個任務的執行制造路徑為博弈策略,將有限資源的多任務調度問題轉變為多個靜態非合作博弈問題.鄭楚紅等[7]針對云制造環境下的多目標任務調度問題,改進非支配排序生物地理優化算法,通過基于權重均勻分配策略定義的用戶偏好度來評估制造任務調度方案的質量,并設計梯形遷移率計算模型擴大其搜索鄰域,避免陷入局部最優解.Xiao 等[8]為解決云制造的多任務調度問題,提出了一種基于博弈理論的云制造多任務調度模型,并利用一種嵌入三種改進的基于生物地理學的擴展優化算法來求解相應模型.Zhou 等[9]針對不同任務的調度問題,根據子任務有向圖生成候選服務集,利用一種改進的遺傳算法來尋找任務調度的最優解.Zhang 等[10]針對任務隨機到達的動態云制造環境中的任務調度問題,提出了一種事件觸發的動態任務調度方法,事件觸發策略的設計考慮了新任務的到來和子任務序列中第一或中間子任務的完成,結合候選服務的服務時間、物流時間和最早可用的時間,為被觸發的子任務選擇最優服務.

由上述文獻可知,在云環境下的任務調度系統中,很少涉及動態任務調度問題,為了更好地解決云環境下的調度問題,并考慮到云環境下任務的規模很大,遺傳算法因其可以在較為合理的計算時間內迅速求得較為理想的滿意解,適合用于求解較大規模的調度問題,因此本文以任務的最大完成時間為優化目標,提出了一種改進的遺傳算法來解決由于緊急任務到達、服務故障導致的重調度問題.

1 問題描述

在云制造系統中,各種制造資源被封裝到制造服務中,資源服務以不同的形式提供各種制造能力.由于在大部分情況下,任務請求復雜且眾多,為了調度執行這些任務,將其分解成一組具有優先關系的子任務,且子任務之間有相互約束關系.

N個任務由P×S個服務執行,其中P和S分別代表云平臺上供應商的數量和每個供應商提供的服務數.每個任務由不同的子任務組成,并且每個子任務對應的任務類型不同.根據任務類型的不同,選擇不同的服務來執行任務,每個供應商所提供的服務可以執行一個或多個不同類型的子任務.本文所考慮的調度問題包括任務的排序、在不違反優先約束的情況下從每個任務分解出的子任務的排序以及選擇合適的服務來最小化最大完工時間Cmax.帶有緊急任務和服務暫停的云制造調度分為3 部分:無特殊情況的正常調度、緊急任務到達引起的重調度、服務暫停引起的重調度.每一部分都需要確定每個子任務的執行順序和每個子任務所選擇的服務,使得最大完成時間最優.

云制造系統調度問題需要考慮如下約束條件:

(1)一個服務在同一時間只可執行一個任務;

(2)一個子任務只可由一個服務執行處理;

(3)同一任務的子任務存在優先關系,需要按順序執行;

(4)任務不可被搶占,任務在執行過程中不能被中斷;

(5)材料資源充足,每個任務所需的資源不會短缺;

針對帶有緊急任務和服務暫停的云制造調度,目標是找到一個最優的子任務序列和服務序列,使得最大完成時間最小化.

2 重調度

云環境下的任務在執行過程中會遇到許多特殊情況,這些特殊情況會中斷正在執行的任務,當特殊情況到達時,需要統計任務的完成情況:已經完成的任務、正在加工的任務、還未執行的任務,再根據具體的情況對這些任務進行重新調度.本文對云制造環境下的動態調度研究考慮了兩種常見的中斷類型:“緊急任務到達”和“服務暫停”,并給出了一種與鄰域搜索相結合的改進遺傳算法,對緊急任務的到達和服務暫停問題得到了很好的解決.

2.1 緊急任務到達

云環境下的任務來自于不同的客戶的不同需求,云平臺根據相應規則將客戶分為高優先級客戶和普通優先級客戶,高優先級客戶具有優先執行任務的權力.在實際的任務執行過程中訂單的優先級都是相同的,當優先級高的客戶在云平臺上發布任務需求時,該任務就會作為緊急訂單加入到系統中,云制造調度系統在這時會產生一個中斷,并統計系統中任務的完成情況,將還未完成的任務與緊急任務作為新的需要重新調度的任務輸入到云制造調度系統中,通過改進的遺傳算法調度產生最優解.在調度過程中優先考慮完成緊急任務,即當緊急任務與普通任務選擇同一個服務執行時,緊急任務優先使用該服務.

若在某時刻云平臺的一個超級會員客戶產生了一個緊急任務,此時需要統計在該時刻還未完成的任務,并將緊急任務作為優先執行任務進行重調度,各個供應商根據調度產生的最優任務序列完成相應任務.

2.2 服務暫停

在傳統的柔性作業車間調度系統中,工件在機器上加工,機器會因為零件老化,部件磨損等情況導致機器故障,因此在該機器上加工的工件需要選擇其他機器進行加工.類似于傳統柔性作業車間調度問題,在實際的云環境生產制造過程中,機器故障、資源緊缺等因素會導致某個服務暫停使用,需要使用該服務的任務需要選擇其他服務來執行,從而影響任務的完成時間.當服務無法使用時,服務只能在恢復之后才能重新執行任務,因此需要在該時刻重新統計還未完成的任務,并對這些任務重新選擇供應商和服務操作.云制造系統根據改進遺傳算法對這些任務進行迭代尋優,產生最優調度任務序列,獲取最小的最大完成時間.

3 改進遺傳算法

遺傳算法(Genetic Algorithm,GA)因其優越的性能和較強的通用性,被認為是求解實際組合優化問題最典型的基于種群的優化算法.本文提出一種改進的遺傳算法用于解決帶有緊急任務和服務暫停的云制造調度問題.改進遺傳算法在傳統遺傳算法的基礎上結合了鄰域搜索和模擬退火算法,多樣的鄰域結構保證在進行全局搜索的過程中陷入局部最優.

傳統的遺傳算法包含初始化、適應度計算、選擇交叉、變異操作,本文在以遺傳算法為基本框架,提出了一種改進的遺傳算法,該算法包含云制造任務編碼、輪盤賭選擇、啟發式規則交叉、多操作鄰域搜索、兩點變異,具體的實現方式如下所示:

3.1 編碼方式

種群中每一個解包含兩個部分,任務次序部分和服務選擇部分.例如:[2 2 3 1 3 1 1 2]和{[6 4 5 2 1 3 2 6],[1 2 1 3 1 2 2 4]}其中第一個向量的第一個“2”表示第2個訂單的第1個子任務,第二“2”表示第2個訂單的第2個子任務,第二個向量表示每個子任務所對應的供應商及其服務,比如表示第2個訂單的第1個子任務是由供應商6的第一個服務來完成的.

3.2 遺傳因子

選擇、交叉、變異是遺傳算法不可缺少的操作,對獲取近似解起到至關重要的作用.

選擇:以輪盤賭的方式選擇,步驟如下:

(1)計算種群中每個個體的適應度值.

(2)計算每個個體遺傳到下一代群體的概率.

(3)計算個體的累計概率.

(4)隨機生成0–1 之間的小數,并根據該數選擇相應的個體.

啟發式規則交叉:為了增加種群的多樣性,本文對遺傳算法進行改進,并提出一種啟發式規則的交叉方法,該交叉方法是在一定的數據引導下對兩個個體進行交叉操作,實驗結果表明,該交叉方法優于傳統的單點交叉、多點交叉、PMX交叉如圖1所示,具體操作方法如下.

圖1 交叉操作

(1)生成一個以任務數為大小的向量R,R中的數是0–1 之間的隨機數,并隨機生成一個0–1 之間的數pt.

(2)根據R中小于pt的數對應選擇父代1中的任務,并將其復制到子代中.

(3)選擇父代2中大于pt的數對應的任務復制到子代中,當對應的位置有值時,不予改變.

(4)選擇父代1中大于pt的數對應的任務復制到子代中,當對應的位置有值時,不予改變,并且確保解的可行性.

(5)統計剩余的子任務,并隨機選擇子代中的空余位置,對子代進行補全.

以圖1為例,根據隨機產生的矩陣R=[0.40,0.66,0.37,0.82],pt=0.55首先選擇P1中的任務1和3 保留到子代中,再選擇P2的任務2和4 補全子代上的空余位置,再選擇P1中的任務4 補全子代上的空余位置,最后統計還未放入子代的任務,若任務數大于2,隨機選擇位置放入,圖1只剩任務4,故直接補全子代即可.

變異:本文采用交換子任務的位置實現變異操作,使遺傳算法具有局部的隨機搜索能力.

3.3 鄰域搜索

遺傳算法雖然能夠快速的找到近似解,但是容易陷入局部最優,這會使得所搜索到的解的結果不好,本文提出的改進的遺傳算法引入了鄰域搜索,旨在打破傳統遺傳算法陷入局部最優的缺點.本文所提出的改進遺傳算法將鄰域操作與模擬退火算法相結合,在鄰域搜索的過程中,以一定的概率接受差解,使得遺傳算法不會過早的收斂于一個局部值.具體的鄰域操作如下所示:

(1)交換:隨機選擇個體的兩個位置,并將相應位置上的任務進行交換.

(2)插入:隨機選擇個體中一個位置,并將該位置上的任務隨機插入其他位置上.

(3)交換兩次:進行兩次操作(1).

(4)插入兩次:進行兩次操作(2).

(5)翻轉:選擇個體中的一段基因,進行翻轉.

在圖2中,鄰域搜索步驟如下:

(1)對參數進行初始化:其中α為溫度衰減因子,T0為初始溫度,Rmax為迭代次數;

(2)獲取種群的最優解及其適應度值;

(3)從種群中隨機選擇一個個體S進行鄰域搜索:根據上述鄰域操作產生鄰域解S′,計算增量?s(S′和S的適應度值之差),若?s小于0,則以一定的概率接受差解,若?s大于0,則用新產生的鄰域解代替原來的解,再更新種群最優值,若適應度值優于種群最優,則代替,并對其進行鄰域搜索;

(4)判斷是否完成相應次數的鄰域搜索,若未達到,返回第(3)步,若達到執行第(5)步;

(5)更新溫度,增加迭代次數,判斷是否達到迭代最大值,若達到則退出,反之則返回第(2)步.

3.4 改進遺傳算法

本文所提出的改進遺傳算法用于解決云環境下的緊急任務到達和服務故障問題,具體實現如下:

(1)統計中斷點的待加工任務;

(2)根據待加工任務進行編碼,產生初始種群;

(3)執行選擇、交叉、變異操作,更新種群;

(4)鄰域搜索,避免陷入局部最優,獲取最優解;

(5)迭代尋優,產生最優加工序列.

本文對遺傳算法的交叉操作因子做了具體改進,啟發式規則下的交叉操作使得種群的解更加豐富多樣,同時降低對種群有效模式的破壞概率.除此之外,引入鄰域搜索,擴大了解的搜索范圍,彌補了遺傳算法容易陷入局部最優的缺點,提高了解的質量,很好的解決了云環境下的動態調度問題.

4 實驗結果

4.1 實驗數據

表1給出了不同供應商之間的運輸時間,當同一個任務的不同子任務使用不同供應商的服務時,在求最大完成時間時需要考慮子任務之間的運輸時間,其中0代表起始點,起始點與不同供應商之間也存在運輸時間,如:起始點為存儲倉庫,客戶所需要的任務最終需要運輸到此地保存.

表1 供應商之間的運輸時間

在云制造調度的文獻中很少考慮由于緊急訂單的到達、服務暫停所導致的重調度問題,所以文獻中沒有包含所有特征的基準實例進行直接比較,因此實驗數據是參照文獻[11]中的數據生成方法隨機生成的.本文數據根據任務和服務數量的不同分為不同的規模,表2給出了任務類型為6 種,3×3 規模的供應商和服務情況下3個任務的數據信息.該數據包含了每個子任務對應的任務類型和選擇的供應商、服務、加工時間,一種類型的任務可選擇不同服務.供應商、服務和加工時間一一對應.

表2 任務數據信息

該數據是還未發生重調度時的數據,在由緊急任務到達、服務故障引起中斷時,此時需要統計還未完成的任務,若在中斷點之后還未執行的任務為“13”、“23”、“24”、“34”則在重調度時只需將這些任務重新調度.

4.2 實驗結果

在本文中,不同規模的問題調度產生的最大完成時間如表3所示,該表包含了正常調度結果和緊急任務以及服務暫停所導致的重調度結果.O、J、T、P、S、H分別代表任務序號、任務數、總子任務數、供應商數、服務數、子任務類型數.Cmax,Cmax1,Cmax2分別是在正常調度、遇到緊急任務和服務暫停情況時的最大完成時間.T1、T2是遇到緊急任務和服務暫停情況的時間,J1是到達的緊急任務數量,p/s是不能使用的服務.

表3 實驗結果

在實例6中,有29個子任務由9個服務執行,這些子任務一共有6 種類型,調度的最大完成時間是28,在執行時間為15 時,到達一個緊急任務,重調度之后的最大完成時間是33.若沒有緊急任務到達,且在執行時間為18 時發生,第一個供應商的第二個服務無法使用,重調度之后的最大完成時間是29.

實例6的實驗結果甘特圖如圖3所示,該圖包含3個子圖:無特殊情況的調度結果圖3(a)、在時間為15時由于緊急任務9的插入引起的重調度結果圖3(b)、在時間為18 時由于第一個供應商的第二個服務暫停引起的重調度結果圖3(c).橫軸為時間軸,縱軸為相應的服務,如:“11”代表第一個供應商的第一個服務.紅線代表中斷時間點,在圖3(b)中,任務9為緊急任務,需要優先執行,如:任務“54”與任務“93”都需要服務“12”執行,首先執行任務“93”.在圖3(c)中,使用故障服務的任務需要重新選擇服務,如:任務“54”由于服務“12”無法使用,故重新選擇服務“22”.

圖3 實驗結果

本文提出的改進遺傳算法與所研究問題的領域沒有關系,它具有隨機搜索的能力并可以快速的獲取最優解.相比于其他算法,本文的算法編碼過程簡單,可擴展性很強,具有良好的全局搜索能力,該算法以遺傳算法為基本框架,與模擬退火算法相結合,擴展了解的搜索范圍,可以快速地將解空間中的最優解搜索出,而不會陷入局部最優解的快速下降陷阱,除此之外,本算法利用它的內在并行性可以方便地進行分布式計算,加快求解速度.

5 結論與展望

針對云制造環境下的動態調度問題,提出了一種與鄰域搜索相結合的改進遺傳算法,用來解決動態調度過程中由于緊急任務的到達和服務暫停導致的重調度問題,來獲取任務的最大完成時間的最優值.實驗結果表明,該算法能夠有效的得到任務的最佳執行序列解,很好的解決動態調度問題.接下來將會對物流運輸進行進一步的研究,使用機器人或車輛對其進行搬運,通過合理的調度得到最優調度解,除此之外,將會嘗試優化算法,最小化最大完成時間.