云制造環(huán)境下的動態(tài)調(diào)度①

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

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

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

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

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

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

1 問題描述

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

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

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

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

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

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

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

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

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

2 重調(diào)度

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

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

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

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

2.2 服務(wù)暫停

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

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

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

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

3.1 編碼方式

種群中每一個解包含兩個部分,任務(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]}其中第一個向量的第一個“2”表示第2個訂單的第1個子任務(wù),第二“2”表示第2個訂單的第2個子任務(wù),第二個向量表示每個子任務(wù)所對應(yīng)的供應(yīng)商及其服務(wù),比如表示第2個訂單的第1個子任務(wù)是由供應(yīng)商6的第一個服務(wù)來完成的.

3.2 遺傳因子

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

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

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

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

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

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

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

圖1 交叉操作

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

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

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

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

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

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

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

3.3 鄰域搜索

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

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

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

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

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

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

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

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

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

(3)從種群中隨機選擇一個個體S進(jìn)行鄰域搜索:根據(jù)上述鄰域操作產(chǎn)生鄰域解S′,計算增量?s(S′和S的適應(yīng)度值之差),若?s小于0,則以一定的概率接受差解,若?s大于0,則用新產(chǎn)生的鄰域解代替原來的解,再更新種群最優(yōu)值,若適應(yīng)度值優(yōu)于種群最優(yōu),則代替,并對其進(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ù)故障問題,具體實現(xiàn)如下:

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

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

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

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

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

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

4 實驗結(jié)果

4.1 實驗數(shù)據(jù)

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

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

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

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

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

4.2 實驗結(jié)果

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

表3 實驗結(jié)果

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

實例6的實驗結(jié)果甘特圖如圖3所示,該圖包含3個子圖:無特殊情況的調(diào)度結(jié)果圖3(a)、在時間為15時由于緊急任務(wù)9的插入引起的重調(diào)度結(jié)果圖3(b)、在時間為18 時由于第一個供應(yīng)商的第二個服務(wù)暫停引起的重調(diào)度結(jié)果圖3(c).橫軸為時間軸,縱軸為相應(yīng)的服務(wù),如:“11”代表第一個供應(yīng)商的第一個服務(wù).紅線代表中斷時間點,在圖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ù)“22”.

圖3 實驗結(jié)果

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

5 結(jié)論與展望

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