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

(長(zhǎng)安大學(xué) 電子與控制工程學(xué)院,西安 710064)

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

目前,求解傳統(tǒng)車間調(diào)度的方法有精確算法和近似算法.毛志慧等[1]提出一種文化基因非支配排序粒子群算法,旨在優(yōu)化產(chǎn)品的合格率、縮短生產(chǎn)周期、減少機(jī)器的空轉(zhuǎn)時(shí)間.杜兆龍等[2]以粒子群算法為基礎(chǔ),引入變鄰域搜索方式,提出基于解空間距離聚類和變鄰域搜索的粒子群算法.Ding 等[3]提出了一種改進(jìn)的粒子群算法來(lái)解決柔性作業(yè)車間調(diào)度問(wèn)題,并通過(guò)改進(jìn)編解碼方案、粒子之間的通信機(jī)制和候選操作機(jī)器的交替規(guī)則來(lái)獲得有益的解決方案,并對(duì)編譯碼方案進(jìn)行了創(chuàng)新,提出了一種新穎的鏈?zhǔn)骄幋a方案和相應(yīng)的有效譯碼方案.Chen 等[4]設(shè)計(jì)一種基于強(qiáng)化學(xué)習(xí)對(duì)關(guān)鍵參數(shù)進(jìn)行智能調(diào)整的自學(xué)習(xí)遺傳算法.

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

由上述文獻(xiàn)可知,在云環(huán)境下的任務(wù)調(diào)度系統(tǒng)中,很少涉及動(dòng)態(tài)任務(wù)調(diào)度問(wèn)題,為了更好地解決云環(huán)境下的調(diào)度問(wèn)題,并考慮到云環(huán)境下任務(wù)的規(guī)模很大,遺傳算法因其可以在較為合理的計(jì)算時(shí)間內(nèi)迅速求得較為理想的滿意解,適合用于求解較大規(guī)模的調(diào)度問(wèn)題,因此本文以任務(wù)的最大完成時(shí)間為優(yōu)化目標(biāo),提出了一種改進(jìn)的遺傳算法來(lái)解決由于緊急任務(wù)到達(dá)、服務(wù)故障導(dǎo)致的重調(diào)度問(wèn)題.

1 問(wèn)題描述

在云制造系統(tǒng)中,各種制造資源被封裝到制造服務(wù)中,資源服務(wù)以不同的形式提供各種制造能力.由于在大部分情況下,任務(wù)請(qǐng)求復(fù)雜且眾多,為了調(diào)度執(zhí)行這些任務(wù),將其分解成一組具有優(yōu)先關(guān)系的子任務(wù),且子任務(wù)之間有相互約束關(guān)系.

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

云制造系統(tǒng)調(diào)度問(wèn)題需要考慮如下約束條件:

(1)一個(gè)服務(wù)在同一時(shí)間只可執(zhí)行一個(gè)任務(wù);

(2)一個(gè)子任務(wù)只可由一個(gè)服務(wù)執(zhí)行處理;

(3)同一任務(wù)的子任務(wù)存在優(yōu)先關(guān)系,需要按順序執(zhí)行;

(4)任務(wù)不可被搶占,任務(wù)在執(zhí)行過(guò)程中不能被中斷;

(5)材料資源充足,每個(gè)任務(wù)所需的資源不會(huì)短缺;

針對(duì)帶有緊急任務(wù)和服務(wù)暫停的云制造調(diào)度,目標(biāo)是找到一個(gè)最優(yōu)的子任務(wù)序列和服務(wù)序列,使得最大完成時(shí)間最小化.

2 重調(diào)度

云環(huán)境下的任務(wù)在執(zhí)行過(guò)程中會(huì)遇到許多特殊情況,這些特殊情況會(huì)中斷正在執(zhí)行的任務(wù),當(dāng)特殊情況到達(dá)時(shí),需要統(tǒng)計(jì)任務(wù)的完成情況:已經(jīng)完成的任務(wù)、正在加工的任務(wù)、還未執(zhí)行的任務(wù),再根據(jù)具體的情況對(duì)這些任務(wù)進(jìn)行重新調(diào)度.本文對(duì)云制造環(huán)境下的動(dòng)態(tài)調(diào)度研究考慮了兩種常見的中斷類型:“緊急任務(wù)到達(dá)”和“服務(wù)暫停”,并給出了一種與鄰域搜索相結(jié)合的改進(jìn)遺傳算法,對(duì)緊急任務(wù)的到達(dá)和服務(wù)暫停問(wèn)題得到了很好的解決.

2.1 緊急任務(wù)到達(dá)

云環(huán)境下的任務(wù)來(lái)自于不同的客戶的不同需求,云平臺(tái)根據(jù)相應(yīng)規(guī)則將客戶分為高優(yōu)先級(jí)客戶和普通優(yōu)先級(jí)客戶,高優(yōu)先級(jí)客戶具有優(yōu)先執(zhí)行任務(wù)的權(quán)力.在實(shí)際的任務(wù)執(zhí)行過(guò)程中訂單的優(yōu)先級(jí)都是相同的,當(dāng)優(yōu)先級(jí)高的客戶在云平臺(tái)上發(fā)布任務(wù)需求時(shí),該任務(wù)就會(huì)作為緊急訂單加入到系統(tǒng)中,云制造調(diào)度系統(tǒng)在這時(shí)會(huì)產(chǎn)生一個(gè)中斷,并統(tǒng)計(jì)系統(tǒng)中任務(wù)的完成情況,將還未完成的任務(wù)與緊急任務(wù)作為新的需要重新調(diào)度的任務(wù)輸入到云制造調(diào)度系統(tǒng)中,通過(guò)改進(jìn)的遺傳算法調(diào)度產(chǎn)生最優(yōu)解.在調(diào)度過(guò)程中優(yōu)先考慮完成緊急任務(wù),即當(dāng)緊急任務(wù)與普通任務(wù)選擇同一個(gè)服務(wù)執(zhí)行時(shí),緊急任務(wù)優(yōu)先使用該服務(wù).

若在某時(shí)刻云平臺(tái)的一個(gè)超級(jí)會(huì)員客戶產(chǎn)生了一個(gè)緊急任務(wù),此時(shí)需要統(tǒng)計(jì)在該時(shí)刻還未完成的任務(wù),并將緊急任務(wù)作為優(yōu)先執(zhí)行任務(wù)進(jìn)行重調(diào)度,各個(gè)供應(yīng)商根據(jù)調(diào)度產(chǎn)生的最優(yōu)任務(wù)序列完成相應(yīng)任務(wù).

2.2 服務(wù)暫停

在傳統(tǒng)的柔性作業(yè)車間調(diào)度系統(tǒng)中,工件在機(jī)器上加工,機(jī)器會(huì)因?yàn)榱慵匣?部件磨損等情況導(dǎo)致機(jī)器故障,因此在該機(jī)器上加工的工件需要選擇其他機(jī)器進(jìn)行加工.類似于傳統(tǒng)柔性作業(yè)車間調(diào)度問(wèn)題,在實(shí)際的云環(huán)境生產(chǎn)制造過(guò)程中,機(jī)器故障、資源緊缺等因素會(huì)導(dǎo)致某個(gè)服務(wù)暫停使用,需要使用該服務(wù)的任務(wù)需要選擇其他服務(wù)來(lái)執(zhí)行,從而影響任務(wù)的完成時(shí)間.當(dāng)服務(wù)無(wú)法使用時(shí),服務(wù)只能在恢復(fù)之后才能重新執(zhí)行任務(wù),因此需要在該時(shí)刻重新統(tǒng)計(jì)還未完成的任務(wù),并對(duì)這些任務(wù)重新選擇供應(yīng)商和服務(wù)操作.云制造系統(tǒng)根據(jù)改進(jìn)遺傳算法對(duì)這些任務(wù)進(jìn)行迭代尋優(yōu),產(chǎn)生最優(yōu)調(diào)度任務(wù)序列,獲取最小的最大完成時(shí)間.

3 改進(jìn)遺傳算法

遺傳算法(Genetic Algorithm,GA)因其優(yōu)越的性能和較強(qiáng)的通用性,被認(rèn)為是求解實(shí)際組合優(yōu)化問(wèn)題最典型的基于種群的優(yōu)化算法.本文提出一種改進(jìn)的遺傳算法用于解決帶有緊急任務(wù)和服務(wù)暫停的云制造調(diào)度問(wèn)題.改進(jìn)遺傳算法在傳統(tǒng)遺傳算法的基礎(chǔ)上結(jié)合了鄰域搜索和模擬退火算法,多樣的鄰域結(jié)構(gòu)保證在進(jìn)行全局搜索的過(guò)程中陷入局部最優(yōu).

傳統(tǒng)的遺傳算法包含初始化、適應(yīng)度計(jì)算、選擇交叉、變異操作,本文在以遺傳算法為基本框架,提出了一種改進(jìn)的遺傳算法,該算法包含云制造任務(wù)編碼、輪盤賭選擇、啟發(fā)式規(guī)則交叉、多操作鄰域搜索、兩點(diǎn)變異,具體的實(shí)現(xiàn)方式如下所示:

3.1 編碼方式

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

3.2 遺傳因子

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

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

(1)計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值.

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

(3)計(jì)算個(gè)體的累計(jì)概率.

(4)隨機(jī)生成0–1 之間的小數(shù),并根據(jù)該數(shù)選擇相應(yīng)的個(gè)體.

啟發(fā)式規(guī)則交叉:為了增加種群的多樣性,本文對(duì)遺傳算法進(jìn)行改進(jìn),并提出一種啟發(fā)式規(guī)則的交叉方法,該交叉方法是在一定的數(shù)據(jù)引導(dǎo)下對(duì)兩個(gè)個(gè)體進(jìn)行交叉操作,實(shí)驗(yàn)結(jié)果表明,該交叉方法優(yōu)于傳統(tǒng)的單點(diǎn)交叉、多點(diǎn)交叉、PMX交叉如圖1所示,具體操作方法如下.

圖1 交叉操作

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

(2)根據(jù)R中小于pt的數(shù)對(duì)應(yīng)選擇父代1中的任務(wù),并將其復(fù)制到子代中.

(3)選擇父代2中大于pt的數(shù)對(duì)應(yīng)的任務(wù)復(fù)制到子代中,當(dāng)對(duì)應(yīng)的位置有值時(shí),不予改變.

(4)選擇父代1中大于pt的數(shù)對(duì)應(yīng)的任務(wù)復(fù)制到子代中,當(dāng)對(duì)應(yīng)的位置有值時(shí),不予改變,并且確保解的可行性.

(5)統(tǒng)計(jì)剩余的子任務(wù),并隨機(jī)選擇子代中的空余位置,對(duì)子代進(jìn)行補(bǔ)全.

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

變異:本文采用交換子任務(wù)的位置實(shí)現(xiàn)變異操作,使遺傳算法具有局部的隨機(jī)搜索能力.

3.3 鄰域搜索

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

(1)交換:隨機(jī)選擇個(gè)體的兩個(gè)位置,并將相應(yīng)位置上的任務(wù)進(jìn)行交換.

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

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

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

(5)翻轉(zhuǎn):選擇個(gè)體中的一段基因,進(jìn)行翻轉(zhuǎn).

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

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

(2)獲取種群的最優(yōu)解及其適應(yīng)度值;

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

(4)判斷是否完成相應(yīng)次數(shù)的鄰域搜索,若未達(dá)到,返回第(3)步,若達(dá)到執(zhí)行第(5)步;

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

3.4 改進(jìn)遺傳算法

本文所提出的改進(jìn)遺傳算法用于解決云環(huán)境下的緊急任務(wù)到達(dá)和服務(wù)故障問(wèn)題,具體實(shí)現(xiàn)如下:

(1)統(tǒng)計(jì)中斷點(diǎn)的待加工任務(wù);

(2)根據(jù)待加工任務(wù)進(jìn)行編碼,產(chǎn)生初始種群;

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

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

(5)迭代尋優(yōu),產(chǎn)生最優(yōu)加工序列.

本文對(duì)遺傳算法的交叉操作因子做了具體改進(jìn),啟發(fā)式規(guī)則下的交叉操作使得種群的解更加豐富多樣,同時(shí)降低對(duì)種群有效模式的破壞概率.除此之外,引入鄰域搜索,擴(kuò)大了解的搜索范圍,彌補(bǔ)了遺傳算法容易陷入局部最優(yōu)的缺點(diǎn),提高了解的質(zhì)量,很好的解決了云環(huán)境下的動(dòng)態(tài)調(diào)度問(wèn)題.

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)數(shù)據(jù)

表1給出了不同供應(yīng)商之間的運(yùn)輸時(shí)間,當(dāng)同一個(gè)任務(wù)的不同子任務(wù)使用不同供應(yīng)商的服務(wù)時(shí),在求最大完成時(shí)間時(shí)需要考慮子任務(wù)之間的運(yùn)輸時(shí)間,其中0代表起始點(diǎn),起始點(diǎn)與不同供應(yīng)商之間也存在運(yùn)輸時(shí)間,如:起始點(diǎn)為存儲(chǔ)倉(cāng)庫(kù),客戶所需要的任務(wù)最終需要運(yùn)輸?shù)酱说乇４?

表1 供應(yīng)商之間的運(yùn)輸時(shí)間

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

表2 任務(wù)數(shù)據(jù)信息

該數(shù)據(jù)是還未發(fā)生重調(diào)度時(shí)的數(shù)據(jù),在由緊急任務(wù)到達(dá)、服務(wù)故障引起中斷時(shí),此時(shí)需要統(tǒng)計(jì)還未完成的任務(wù),若在中斷點(diǎn)之后還未執(zhí)行的任務(wù)為“13”、“23”、“24”、“34”則在重調(diào)度時(shí)只需將這些任務(wù)重新調(diào)度.

4.2 實(shí)驗(yàn)結(jié)果

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

表3 實(shí)驗(yàn)結(jié)果

在實(shí)例6中,有29個(gè)子任務(wù)由9個(gè)服務(wù)執(zhí)行,這些子任務(wù)一共有6 種類型,調(diào)度的最大完成時(shí)間是28,在執(zhí)行時(shí)間為15 時(shí),到達(dá)一個(gè)緊急任務(wù),重調(diào)度之后的最大完成時(shí)間是33.若沒(méi)有緊急任務(wù)到達(dá),且在執(zhí)行時(shí)間為18 時(shí)發(fā)生,第一個(gè)供應(yīng)商的第二個(gè)服務(wù)無(wú)法使用,重調(diào)度之后的最大完成時(shí)間是29.

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

圖3 實(shí)驗(yàn)結(jié)果

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

5 結(jié)論與展望

針對(duì)云制造環(huán)境下的動(dòng)態(tài)調(diào)度問(wèn)題,提出了一種與鄰域搜索相結(jié)合的改進(jìn)遺傳算法,用來(lái)解決動(dòng)態(tài)調(diào)度過(guò)程中由于緊急任務(wù)的到達(dá)和服務(wù)暫停導(dǎo)致的重調(diào)度問(wèn)題,來(lái)獲取任務(wù)的最大完成時(shí)間的最優(yōu)值.實(shí)驗(yàn)結(jié)果表明,該算法能夠有效的得到任務(wù)的最佳執(zhí)行序列解,很好的解決動(dòng)態(tài)調(diào)度問(wèn)題.接下來(lái)將會(huì)對(duì)物流運(yùn)輸進(jìn)行進(jìn)一步的研究,使用機(jī)器人或車輛對(duì)其進(jìn)行搬運(yùn),通過(guò)合理的調(diào)度得到最優(yōu)調(diào)度解,除此之外,將會(huì)嘗試優(yōu)化算法,最小化最大完成時(shí)間.