基于復(fù)雜網(wǎng)絡(luò)理論的復(fù)雜調(diào)度問(wèn)題求解方法研究.pdf

1、調(diào)度作為資源分配的一種手段在各個(gè)領(lǐng)域都得到了廣泛的重視。現(xiàn)實(shí)中的調(diào)度對(duì)象通常具有動(dòng)態(tài)性，隨機(jī)性，以及不確定性等特點(diǎn)，本文中把該類(lèi)調(diào)度對(duì)象稱(chēng)為復(fù)雜調(diào)度對(duì)象，而相應(yīng)的調(diào)度問(wèn)題則稱(chēng)為復(fù)雜調(diào)度問(wèn)題。調(diào)度規(guī)則由于其簡(jiǎn)單靈活的特點(diǎn)，被廣泛采用于求解復(fù)雜調(diào)度問(wèn)題。當(dāng)前的調(diào)度規(guī)則大多源于生產(chǎn)實(shí)際，缺少一種系統(tǒng)化的方法。復(fù)雜網(wǎng)絡(luò)作為研究復(fù)雜系統(tǒng)結(jié)構(gòu)的一種新興的理論為調(diào)度提供了新的契機(jī)。本文通過(guò)給復(fù)雜調(diào)度對(duì)象建立復(fù)雜網(wǎng)絡(luò)模型，從而將復(fù)雜調(diào)度問(wèn)題轉(zhuǎn)換成復(fù)雜網(wǎng)

2、絡(luò)上的節(jié)點(diǎn)遍歷問(wèn)題，并且在復(fù)雜網(wǎng)絡(luò)的框架下提出了系統(tǒng)化設(shè)計(jì)調(diào)度規(guī)則的方法。最后將這些調(diào)度規(guī)則用于求解多資源獨(dú)立任務(wù)復(fù)雜調(diào)度問(wèn)題取得了不錯(cuò)的效果。本文的研究?jī)?nèi)容以及創(chuàng)新點(diǎn)主要包括以下幾個(gè)方面： 根據(jù)現(xiàn)實(shí)的復(fù)雜系統(tǒng)特點(diǎn)從三種不同的視角提出了三個(gè)多特征復(fù)雜網(wǎng)絡(luò)模型，包括區(qū)域固定局部世界模型，能力固定局部世界模型，以及基于博弈的動(dòng)態(tài)演變模型。 首次給出了復(fù)雜調(diào)度對(duì)象的網(wǎng)絡(luò)化描述，將復(fù)雜調(diào)度問(wèn)題轉(zhuǎn)換成復(fù)雜調(diào)度網(wǎng)絡(luò)上的節(jié)點(diǎn)遍歷問(wèn)題，

3、這為解決實(shí)際復(fù)雜調(diào)度問(wèn)題提供了新的視角和方法。 通過(guò)某種映射關(guān)系可以把調(diào)度目標(biāo)轉(zhuǎn)換成復(fù)雜調(diào)度網(wǎng)絡(luò)的某個(gè)全局特征，從而將復(fù)雜調(diào)度網(wǎng)絡(luò)的局部特征作為設(shè)計(jì)調(diào)度規(guī)則的啟發(fā)式信息。比如網(wǎng)絡(luò)平均度值以及平均功效和復(fù)雜調(diào)度問(wèn)題之間就存在某種關(guān)聯(lián)，而節(jié)點(diǎn)度值，節(jié)點(diǎn)聚類(lèi)系數(shù)，以及本文提出的節(jié)點(diǎn)冗余度均可作為設(shè)計(jì)調(diào)度規(guī)則的啟發(fā)式信息。 給出了復(fù)雜調(diào)度網(wǎng)絡(luò)建模的具體步驟，并且通過(guò)這些步驟在基于一些假設(shè)的基礎(chǔ)上給四類(lèi)復(fù)雜調(diào)度對(duì)象，多資源獨(dú)立任務(wù)

4、每個(gè)事件所需資源數(shù)服從均勻分布調(diào)度對(duì)象，多資源獨(dú)立任務(wù)每個(gè)事件所需資源數(shù)服從冪律分布調(diào)度對(duì)象，多資源非獨(dú)立任務(wù)每個(gè)事件所需資源數(shù)服從均勻分布調(diào)度對(duì)象，以及多資源非獨(dú)立任務(wù)每個(gè)事件所需資源數(shù)服從冪律分布調(diào)度對(duì)象，構(gòu)建了各自的復(fù)雜調(diào)度網(wǎng)絡(luò)模型，并對(duì)這些復(fù)雜調(diào)度網(wǎng)絡(luò)進(jìn)行了結(jié)構(gòu)特征分析。 提取了三種基于復(fù)雜調(diào)度調(diào)度網(wǎng)絡(luò)結(jié)構(gòu)的調(diào)度規(guī)則，主要包括基于節(jié)點(diǎn)度值，聚類(lèi)系數(shù)，以及冗余度的調(diào)度規(guī)則，并將它們用于求解多資源獨(dú)立任務(wù)復(fù)雜調(diào)度問(wèn)題，相比幾