第四方檢驗(yàn)檢測(cè)平臺(tái)任務(wù)動(dòng)態(tài)調(diào)度策略優(yōu)化

黃素貞HUANG Su-zhen；王瑩WANG Ying

（北京信息科技大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100192）

0 引言

第四方檢驗(yàn)檢測(cè)平臺(tái)是檢驗(yàn)檢測(cè)行業(yè)在第三方平臺(tái)的基礎(chǔ)上做出的創(chuàng)新，通過進(jìn)一步集中市場(chǎng)現(xiàn)存的檢驗(yàn)檢測(cè)資源，整合檢測(cè)領(lǐng)域產(chǎn)業(yè)鏈上的多個(gè)主體，從而實(shí)現(xiàn)檢驗(yàn)檢測(cè)領(lǐng)域的一站式集成化服務(wù)的專業(yè)領(lǐng)域集成化平臺(tái)。在第四方平臺(tái)運(yùn)營的過程中，由于檢測(cè)任務(wù)日趨復(fù)雜和集成化，因此需要拆分成若干個(gè)檢測(cè)子任務(wù)，并由平臺(tái)中的多個(gè)檢測(cè)服務(wù)機(jī)構(gòu)合作完成。在檢測(cè)任務(wù)完成的過程中，新的檢驗(yàn)檢測(cè)訂單不斷進(jìn)入，因此，如何對(duì)大量檢測(cè)任務(wù)進(jìn)行科學(xué)合理地動(dòng)態(tài)調(diào)度是第四方檢驗(yàn)檢測(cè)平臺(tái)面臨的一個(gè)亟待解決的問題。高效有序的任務(wù)動(dòng)態(tài)調(diào)度對(duì)于加快檢測(cè)領(lǐng)域的發(fā)展和促進(jìn)第四方檢驗(yàn)檢測(cè)平臺(tái)的落地有重大推進(jìn)作用。調(diào)度優(yōu)化的目的是根據(jù)約束目標(biāo)，合理分配資源，使調(diào)度目標(biāo)達(dá)到最優(yōu)[1]。

隨著互聯(lián)網(wǎng)+和大數(shù)據(jù)的快速發(fā)展，平臺(tái)的動(dòng)態(tài)調(diào)度優(yōu)化吸引了大量學(xué)者的研究。曾薇[2]提出一種云平臺(tái)大量任務(wù)的多目標(biāo)約束調(diào)度模型，運(yùn)用蟻群算法求解來達(dá)到調(diào)度目標(biāo)最優(yōu)。Liu 等[3]提出了一個(gè)多任務(wù)的云制造調(diào)度模型，并通過仿真實(shí)驗(yàn)研究了不同的基于工作負(fù)載的任務(wù)調(diào)度方法對(duì)系統(tǒng)性能的影響。當(dāng)前的相關(guān)研究中針對(duì)檢驗(yàn)檢測(cè)領(lǐng)域的專業(yè)集成化平臺(tái)動(dòng)態(tài)調(diào)度問題的研究尚不多見。本文擬從復(fù)雜網(wǎng)絡(luò)的視角出發(fā)，將大量檢測(cè)子任務(wù)抽象為網(wǎng)絡(luò)節(jié)點(diǎn)，通過約束規(guī)則構(gòu)建成復(fù)雜網(wǎng)絡(luò)模型，并對(duì)蟻群算法進(jìn)行改進(jìn)，使其適用于求解模型，為檢驗(yàn)檢測(cè)平臺(tái)下的任務(wù)動(dòng)態(tài)調(diào)度提供有效的優(yōu)化方案，提高平臺(tái)檢測(cè)任務(wù)調(diào)度效率的同時(shí)也帶動(dòng)檢驗(yàn)檢測(cè)服務(wù)業(yè)的發(fā)展，具有較高的研究價(jià)值與意義。

1 第四方檢驗(yàn)檢測(cè)平臺(tái)任務(wù)復(fù)雜動(dòng)態(tài)調(diào)度模型構(gòu)建

第四方檢驗(yàn)檢測(cè)平臺(tái)中的檢測(cè)任務(wù)是不斷隨機(jī)到達(dá)的，一個(gè)檢測(cè)任務(wù)需要分解為多個(gè)檢測(cè)子任務(wù)進(jìn)行檢測(cè)，在復(fù)雜網(wǎng)絡(luò)中表現(xiàn)為若干個(gè)節(jié)點(diǎn)的增多，子任務(wù)檢測(cè)完成后會(huì)退出網(wǎng)絡(luò)，表現(xiàn)為節(jié)點(diǎn)的減少，因此網(wǎng)絡(luò)是不斷變化的，這種網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)變化稱為更新規(guī)則。因此可以將復(fù)雜網(wǎng)絡(luò)表示為節(jié)點(diǎn)、邊和更新規(guī)則的三元組[4]，即

將檢測(cè)任務(wù)抽象為復(fù)雜網(wǎng)絡(luò)的規(guī)則如下：用網(wǎng)絡(luò)中的節(jié)點(diǎn)代表每個(gè)檢測(cè)子任務(wù)，根據(jù)子任務(wù)間的資源約束和任務(wù)約束將節(jié)點(diǎn)連接起來。假設(shè)有4 個(gè)檢測(cè)任務(wù)，第四方檢驗(yàn)檢測(cè)平臺(tái)中有n 個(gè)檢測(cè)資源，檢測(cè)任務(wù)與檢測(cè)資源的匹配情況如表1 所示。

表1 檢測(cè)任務(wù)與檢測(cè)資源匹配結(jié)果

根據(jù)復(fù)雜網(wǎng)絡(luò)構(gòu)建規(guī)則得到的復(fù)雜網(wǎng)絡(luò)如圖1 所示。

圖1 中Lxy表示檢測(cè)資源x 與檢測(cè)資源y 之間進(jìn)行任務(wù)運(yùn)輸所消耗的時(shí)間。雖然檢測(cè)任務(wù)的加入和退出使得復(fù)雜網(wǎng)絡(luò)表現(xiàn)出很強(qiáng)的動(dòng)態(tài)性，但任意時(shí)刻的網(wǎng)絡(luò)都和圖1相似。通過以上規(guī)則構(gòu)建復(fù)雜網(wǎng)絡(luò)模型，可以用復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)遍歷解決第四方檢驗(yàn)檢測(cè)平臺(tái)任務(wù)動(dòng)態(tài)調(diào)度問題。

圖1 復(fù)雜網(wǎng)絡(luò)調(diào)度模型

2 改進(jìn)蟻群算法

2.1 路徑選擇規(guī)則優(yōu)化

優(yōu)先遍歷度值較大的點(diǎn)，可以降低網(wǎng)絡(luò)的耦合度，縮短遍歷時(shí)間。同時(shí)檢測(cè)子任務(wù)有其特定屬性：子任務(wù)檢測(cè)時(shí)間越長或后序子任務(wù)數(shù)越多，越有可能優(yōu)先檢測(cè)。因此本文將節(jié)點(diǎn)度值與任務(wù)屬性相結(jié)合[5]，引入螞蟻路徑選擇規(guī)則中，引導(dǎo)螞蟻在節(jié)點(diǎn)轉(zhuǎn)移時(shí)，優(yōu)先選擇度值與任務(wù)屬性的綜合值較大的節(jié)點(diǎn)，用hj表示節(jié)點(diǎn)綜合任務(wù)屬性，綜合值計(jì)算方法如式（4）所示。

節(jié)點(diǎn)度值和任務(wù)屬性的計(jì)算公式用式5）-（6）表示。

kj-um表示節(jié)點(diǎn)j 的無向邊數(shù)目；kj-in表示節(jié)點(diǎn)j 的入度值，入度由有向邊指向節(jié)點(diǎn)引起的；kj-out表示節(jié)點(diǎn)j 的出度值，出度由有向邊從該節(jié)點(diǎn)指出引起的。

Vj表示節(jié)點(diǎn)j 對(duì)應(yīng)子任務(wù)的檢測(cè)時(shí)間。pnn（Vj）表示節(jié)點(diǎn)j 的后續(xù)節(jié)點(diǎn)數(shù)。

螞蟻遍歷過程中，將所有可達(dá)節(jié)點(diǎn)根據(jù)度值分為三種類型，并保存在不同的集合中，如表2 所示。

表2 節(jié)點(diǎn)類型示意圖

螞蟻的轉(zhuǎn)移節(jié)點(diǎn)選擇分為三步：首先遍歷集合Uk1中的節(jié)點(diǎn)，當(dāng)Uk1中的節(jié)點(diǎn)為空時(shí)，再開始遍歷Uk3中的節(jié)點(diǎn)，最后遍歷集合Uk2的節(jié)點(diǎn)，直到網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量為0。

轉(zhuǎn)移概率計(jì)算公式如式（7）所示。

按照上述步驟，可以使螞蟻在遍歷節(jié)點(diǎn)的過程中，首先遍歷那些入度為0 的節(jié)點(diǎn)，而出度為0 的點(diǎn)在最后遍歷，從而保證子任務(wù)按優(yōu)先級(jí)順序進(jìn)行檢測(cè)。

2.2 并行螞蟻優(yōu)化

本文采用并行螞蟻的策略，設(shè)置和檢測(cè)資源數(shù)量相等的螞蟻數(shù)目，將蟻群中的每只螞蟻分配到每個(gè)檢測(cè)資源上，讓每只螞蟻獨(dú)立負(fù)責(zé)一個(gè)檢測(cè)資源所構(gòu)成的小網(wǎng)絡(luò)的遍歷。蟻群搜索過程中利用節(jié)點(diǎn)度值與任務(wù)屬性的綜合值來引導(dǎo)螞蟻的路徑選擇。多只螞蟻同時(shí)遍歷，使收斂速度加快。每只螞蟻遍歷完成所在檢測(cè)資源上的所有節(jié)點(diǎn)時(shí)，對(duì)該檢測(cè)資源所構(gòu)成的小型網(wǎng)絡(luò)進(jìn)行局部的信息素更新，所有螞蟻完成遍歷后，對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行全局的信息素更新。并行螞蟻思想在第四方檢驗(yàn)檢測(cè)平臺(tái)中的任務(wù)遍歷過程如圖2 所示。

圖2 并行螞蟻策略在第四方檢驗(yàn)檢測(cè)平臺(tái)中的應(yīng)用原理

局部信息素更新根據(jù)式（8）進(jìn)行。

按式（9）-（11）進(jìn)行全局信息素更新。

考慮加入最大最小螞蟻系統(tǒng)的思想，來防止某條路徑上的信息素積累過多，從而陷入局部最優(yōu)，將信息素的量限制在某個(gè)范圍內(nèi)，和的值分別按式（12）-（13）計(jì)算。

其中Tbest是當(dāng)前解的最優(yōu)值，ε 是信息素因子的下限，一般設(shè)置為特別小的一個(gè)正數(shù)。

3 第四方檢驗(yàn)檢測(cè)平臺(tái)動(dòng)態(tài)任務(wù)重調(diào)度方案生成

3.1 重調(diào)度驅(qū)動(dòng)機(jī)制和重調(diào)度策略設(shè)計(jì)

基于最大任務(wù)數(shù)的事件驅(qū)動(dòng)機(jī)制的思想是：設(shè)置一個(gè)最大任務(wù)數(shù)上限值θs，當(dāng)有新任務(wù)到達(dá)時(shí)，判斷θ 的大小，若θ＜θs，則接受該新任務(wù)，觸發(fā)重調(diào)度，否則不再接受該新任務(wù)的加入，繼續(xù)按照原調(diào)度方案執(zhí)行直至所有子任務(wù)檢測(cè)完成退出網(wǎng)絡(luò)。

第四方檢驗(yàn)檢測(cè)平臺(tái)下的任務(wù)調(diào)度問題中，為每個(gè)子任務(wù)分配檢測(cè)資源后不再改變，需要確定的是子任務(wù)間的檢測(cè)順序安排，因此本部分研究問題的完全重調(diào)度就是對(duì)子任務(wù)檢測(cè)順序的重新安排。完全重調(diào)度策略可描述為：當(dāng)有新任務(wù)加入觸發(fā)重調(diào)度時(shí)，檢測(cè)資源首先需要將正在進(jìn)行的檢測(cè)任務(wù)完成，然后再對(duì)新增加的子任務(wù)和其他剩余未檢測(cè)的子任務(wù)進(jìn)行檢測(cè)順序的安排，得到新的檢測(cè)順序方案。

3.2 有新任務(wù)加入的動(dòng)態(tài)重調(diào)度方案生成

基于預(yù)測(cè)反應(yīng)式動(dòng)態(tài)調(diào)度模型和復(fù)雜網(wǎng)絡(luò)思想，當(dāng)由新任務(wù)到達(dá)時(shí)，觸發(fā)重調(diào)度，同時(shí)加入多個(gè)檢測(cè)子任務(wù)，即復(fù)雜網(wǎng)絡(luò)中有多個(gè)節(jié)點(diǎn)和邊的增加，符合網(wǎng)絡(luò)的生長規(guī)則。根據(jù)排隊(duì)論思想,當(dāng)新任務(wù)到達(dá)時(shí)遵循先到先服務(wù)的原則，新到達(dá)的任務(wù)根據(jù)到達(dá)順序加入到網(wǎng)絡(luò)中。根據(jù)重調(diào)度驅(qū)動(dòng)機(jī)制、重調(diào)度策略，得到有新任務(wù)加入的第四方檢驗(yàn)檢測(cè)平臺(tái)任務(wù)重調(diào)度方案如圖3 所示。

圖3 重調(diào)度方案執(zhí)行流程圖

4 仿真實(shí)驗(yàn)

本節(jié)設(shè)計(jì)仿真對(duì)比實(shí)驗(yàn)，設(shè)置相同的資源數(shù)目，當(dāng)任務(wù)數(shù)量不同時(shí)，對(duì)比本文算法與文獻(xiàn)[6]算法的性能。實(shí)驗(yàn)數(shù)據(jù)和算法參數(shù)如表3 所示。其中需要為子任務(wù)隨機(jī)分配檢測(cè)資源，同時(shí)生成檢測(cè)子任務(wù)的檢測(cè)時(shí)間。

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

實(shí)驗(yàn)環(huán)境保持相同開始實(shí)驗(yàn)，將10 次實(shí)驗(yàn)結(jié)果的平均值作為最終對(duì)比結(jié)果，兩種算法在任務(wù)數(shù)不同時(shí)的平均最長檢測(cè)完成時(shí)間、平均迭代次數(shù)對(duì)比結(jié)果如圖4 所示。

圖4 不同?任務(wù)數(shù)下兩種算法實(shí)驗(yàn)結(jié)果對(duì)比圖

從實(shí)驗(yàn)結(jié)果比對(duì)圖中可得知，在不同的任務(wù)數(shù)量下，本文提出的結(jié)合復(fù)雜網(wǎng)絡(luò)改進(jìn)的蟻群算法在檢測(cè)完成時(shí)間和算法迭代次數(shù)上都優(yōu)于文獻(xiàn)[6]，說明本文提出的改進(jìn)蟻群算法具有良好的解決實(shí)際調(diào)度問題的性能。尤其在迭代次數(shù)上，隨著任務(wù)數(shù)量的不斷加大，收斂速度相對(duì)文獻(xiàn)[6]表現(xiàn)出的優(yōu)勢(shì)越來明顯。實(shí)驗(yàn)結(jié)果可以充分表明，將度值與任務(wù)屬性的綜合值應(yīng)用于轉(zhuǎn)移概率公式中引導(dǎo)螞蟻對(duì)節(jié)點(diǎn)的選擇，對(duì)基本蟻群算法的路徑選擇規(guī)則優(yōu)化，并將并行螞蟻思想應(yīng)用于蟻群算法后，得到的改進(jìn)蟻群算法在調(diào)度性能上優(yōu)于文獻(xiàn)[6]的算法。

5 結(jié)論

本文針對(duì)第四方檢驗(yàn)檢測(cè)平臺(tái)中任務(wù)隨機(jī)到達(dá)的動(dòng)態(tài)任務(wù)調(diào)度問題，從復(fù)雜網(wǎng)絡(luò)的視角出發(fā)，構(gòu)建出復(fù)雜網(wǎng)絡(luò)模型。采用預(yù)測(cè)反應(yīng)式動(dòng)態(tài)調(diào)度模型，并結(jié)合基于最大任務(wù)數(shù)的事件驅(qū)動(dòng)機(jī)制和完全重調(diào)度策略，將第四方檢驗(yàn)檢測(cè)平臺(tái)中有任務(wù)到達(dá)的動(dòng)態(tài)調(diào)度問題轉(zhuǎn)變?yōu)橄鄬?duì)穩(wěn)定的靜態(tài)調(diào)度問題，生成第四方檢驗(yàn)檢測(cè)平臺(tái)任務(wù)重調(diào)度方案，并使用改進(jìn)蟻群算法對(duì)重調(diào)度方案進(jìn)行求解。通過與其他算法進(jìn)行實(shí)驗(yàn)對(duì)比，發(fā)現(xiàn)本文提出的改進(jìn)蟻群算法在求解重調(diào)度問題中效率更高。