第四方檢驗檢測平臺任務動態調度策略優化

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

（北京信息科技大學經濟管理學院，北京 100192）

0 引言

第四方檢驗檢測平臺是檢驗檢測行業在第三方平臺的基礎上做出的創新，通過進一步集中市場現存的檢驗檢測資源，整合檢測領域產業鏈上的多個主體，從而實現檢驗檢測領域的一站式集成化服務的專業領域集成化平臺。在第四方平臺運營的過程中，由于檢測任務日趨復雜和集成化，因此需要拆分成若干個檢測子任務，并由平臺中的多個檢測服務機構合作完成。在檢測任務完成的過程中，新的檢驗檢測訂單不斷進入，因此，如何對大量檢測任務進行科學合理地動態調度是第四方檢驗檢測平臺面臨的一個亟待解決的問題。高效有序的任務動態調度對于加快檢測領域的發展和促進第四方檢驗檢測平臺的落地有重大推進作用。調度優化的目的是根據約束目標，合理分配資源，使調度目標達到最優[1]。

隨著互聯網+和大數據的快速發展，平臺的動態調度優化吸引了大量學者的研究。曾薇[2]提出一種云平臺大量任務的多目標約束調度模型，運用蟻群算法求解來達到調度目標最優。Liu 等[3]提出了一個多任務的云制造調度模型，并通過仿真實驗研究了不同的基于工作負載的任務調度方法對系統性能的影響。當前的相關研究中針對檢驗檢測領域的專業集成化平臺動態調度問題的研究尚不多見。本文擬從復雜網絡的視角出發，將大量檢測子任務抽象為網絡節點，通過約束規則構建成復雜網絡模型，并對蟻群算法進行改進，使其適用于求解模型，為檢驗檢測平臺下的任務動態調度提供有效的優化方案，提高平臺檢測任務調度效率的同時也帶動檢驗檢測服務業的發展，具有較高的研究價值與意義。

1 第四方檢驗檢測平臺任務復雜動態調度模型構建

第四方檢驗檢測平臺中的檢測任務是不斷隨機到達的，一個檢測任務需要分解為多個檢測子任務進行檢測，在復雜網絡中表現為若干個節點的增多，子任務檢測完成后會退出網絡，表現為節點的減少，因此網絡是不斷變化的，這種網絡結構的動態變化稱為更新規則。因此可以將復雜網絡表示為節點、邊和更新規則的三元組[4]，即

將檢測任務抽象為復雜網絡的規則如下：用網絡中的節點代表每個檢測子任務，根據子任務間的資源約束和任務約束將節點連接起來。假設有4 個檢測任務，第四方檢驗檢測平臺中有n 個檢測資源，檢測任務與檢測資源的匹配情況如表1 所示。

表1 檢測任務與檢測資源匹配結果

根據復雜網絡構建規則得到的復雜網絡如圖1 所示。

圖1 中Lxy表示檢測資源x 與檢測資源y 之間進行任務運輸所消耗的時間。雖然檢測任務的加入和退出使得復雜網絡表現出很強的動態性，但任意時刻的網絡都和圖1相似。通過以上規則構建復雜網絡模型，可以用復雜網絡的節點遍歷解決第四方檢驗檢測平臺任務動態調度問題。

圖1 復雜網絡調度模型

2 改進蟻群算法

2.1 路徑選擇規則優化

優先遍歷度值較大的點，可以降低網絡的耦合度，縮短遍歷時間。同時檢測子任務有其特定屬性：子任務檢測時間越長或后序子任務數越多，越有可能優先檢測。因此本文將節點度值與任務屬性相結合[5]，引入螞蟻路徑選擇規則中，引導螞蟻在節點轉移時，優先選擇度值與任務屬性的綜合值較大的節點，用hj表示節點綜合任務屬性，綜合值計算方法如式（4）所示。

節點度值和任務屬性的計算公式用式5）-（6）表示。

kj-um表示節點j 的無向邊數目；kj-in表示節點j 的入度值，入度由有向邊指向節點引起的；kj-out表示節點j 的出度值，出度由有向邊從該節點指出引起的。

Vj表示節點j 對應子任務的檢測時間。pnn（Vj）表示節點j 的后續節點數。

螞蟻遍歷過程中，將所有可達節點根據度值分為三種類型，并保存在不同的集合中，如表2 所示。

表2 節點類型示意圖

螞蟻的轉移節點選擇分為三步：首先遍歷集合Uk1中的節點，當Uk1中的節點為空時，再開始遍歷Uk3中的節點，最后遍歷集合Uk2的節點，直到網絡中的節點數量為0。

轉移概率計算公式如式（7）所示。

按照上述步驟，可以使螞蟻在遍歷節點的過程中，首先遍歷那些入度為0 的節點，而出度為0 的點在最后遍歷，從而保證子任務按優先級順序進行檢測。

2.2 并行螞蟻優化

本文采用并行螞蟻的策略，設置和檢測資源數量相等的螞蟻數目，將蟻群中的每只螞蟻分配到每個檢測資源上，讓每只螞蟻獨立負責一個檢測資源所構成的小網絡的遍歷。蟻群搜索過程中利用節點度值與任務屬性的綜合值來引導螞蟻的路徑選擇。多只螞蟻同時遍歷，使收斂速度加快。每只螞蟻遍歷完成所在檢測資源上的所有節點時，對該檢測資源所構成的小型網絡進行局部的信息素更新，所有螞蟻完成遍歷后，對整個網絡進行全局的信息素更新。并行螞蟻思想在第四方檢驗檢測平臺中的任務遍歷過程如圖2 所示。

圖2 并行螞蟻策略在第四方檢驗檢測平臺中的應用原理

局部信息素更新根據式（8）進行。

按式（9）-（11）進行全局信息素更新。

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

其中Tbest是當前解的最優值，ε 是信息素因子的下限，一般設置為特別小的一個正數。

3 第四方檢驗檢測平臺動態任務重調度方案生成

3.1 重調度驅動機制和重調度策略設計

基于最大任務數的事件驅動機制的思想是：設置一個最大任務數上限值θs，當有新任務到達時，判斷θ 的大小，若θ＜θs，則接受該新任務，觸發重調度，否則不再接受該新任務的加入，繼續按照原調度方案執行直至所有子任務檢測完成退出網絡。

第四方檢驗檢測平臺下的任務調度問題中，為每個子任務分配檢測資源后不再改變，需要確定的是子任務間的檢測順序安排，因此本部分研究問題的完全重調度就是對子任務檢測順序的重新安排。完全重調度策略可描述為：當有新任務加入觸發重調度時，檢測資源首先需要將正在進行的檢測任務完成，然后再對新增加的子任務和其他剩余未檢測的子任務進行檢測順序的安排，得到新的檢測順序方案。

3.2 有新任務加入的動態重調度方案生成

基于預測反應式動態調度模型和復雜網絡思想，當由新任務到達時，觸發重調度，同時加入多個檢測子任務，即復雜網絡中有多個節點和邊的增加，符合網絡的生長規則。根據排隊論思想,當新任務到達時遵循先到先服務的原則，新到達的任務根據到達順序加入到網絡中。根據重調度驅動機制、重調度策略，得到有新任務加入的第四方檢驗檢測平臺任務重調度方案如圖3 所示。

圖3 重調度方案執行流程圖

4 仿真實驗

本節設計仿真對比實驗，設置相同的資源數目，當任務數量不同時，對比本文算法與文獻[6]算法的性能。實驗數據和算法參數如表3 所示。其中需要為子任務隨機分配檢測資源，同時生成檢測子任務的檢測時間。

表3 實驗數據

實驗環境保持相同開始實驗，將10 次實驗結果的平均值作為最終對比結果，兩種算法在任務數不同時的平均最長檢測完成時間、平均迭代次數對比結果如圖4 所示。

圖4 不同?任務數下兩種算法實驗結果對比圖

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

5 結論

本文針對第四方檢驗檢測平臺中任務隨機到達的動態任務調度問題，從復雜網絡的視角出發，構建出復雜網絡模型。采用預測反應式動態調度模型，并結合基于最大任務數的事件驅動機制和完全重調度策略，將第四方檢驗檢測平臺中有任務到達的動態調度問題轉變為相對穩定的靜態調度問題，生成第四方檢驗檢測平臺任務重調度方案，并使用改進蟻群算法對重調度方案進行求解。通過與其他算法進行實驗對比，發現本文提出的改進蟻群算法在求解重調度問題中效率更高。