林麗娜 孫光輝 唐晶

摘要：本文給出一種基于圖約束裝箱算法的構(gòu)件調(diào)度策略生成算法，將構(gòu)件動態(tài)部署和調(diào)度策略的生成描述成新的裝箱問題，將CPU看做箱子，構(gòu)件看做物品。當兩個CPU之間有構(gòu)件存在數(shù)據(jù)收發(fā)關(guān)系時，需要在CPU之間創(chuàng)建RapidIO數(shù)據(jù)鏈路。構(gòu)件部署完成后，得到一張以CPU為頂點、RapidIO數(shù)據(jù)鏈路為邊的關(guān)系圖，需要在該圖滿足頂點容量、邊的度數(shù)等約束條件下，使得占用箱子數(shù)量最小，是一個復雜的NP完全問題。實驗表明，本文給出的基于圖約束裝箱算法的構(gòu)件調(diào)度策略生成算法，能夠較好地解決大規(guī)模構(gòu)件的動態(tài)部署問題。

Abstract： This paper presents a component scheduling strategy generation algorithm based on graph-constrained bin packing algorithm. The dynamic deployment of components and the generation of scheduling strategies are described as a new packing problem， the CPU is regarded as a box， and the component is regarded as an item. When there is a data receiving and sending relationship between two CPUs， a RapidIO data link needs to be created between the CPUs. After the component is deployed， a relationship graph with the CPU as the vertex and the RapidIO data link as the edge is obtained. The graph needs to meet the constraints of vertex capacity， edge degree and other constraints， so that the number of occupied boxes is minimized， which is a complex NP-complete problem. Experiments show that the component scheduling strategy generation algorithm based on graph-constrained bin packing algorithm presented in this paper can better solve the problem of dynamic deployment of large-scale components.

關(guān)鍵詞：構(gòu)件;設(shè)備軟件;服務(wù)調(diào)度

Key words： component;equipment software;service scheduling

中圖分類號：TP311.52 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1006-4311（2020）30-0205-03

1 ?圖約束裝箱問題BPPR的形式化表達

結(jié)合嵌入式信息處理設(shè)備中的構(gòu)件調(diào)度問題，將BPPR裝箱問題可描述如下：

采用RapidIO高速總線的嵌入式多CPU單元的信息處理裝備中，給定一組容量為W的箱子（CPU）B={b1，b2，…，bm}，和n個物品（構(gòu)件）的序列L={a1，a2，…，an}，物品ai的體積（如：CPU、內(nèi)存占用率）為wi（wi？燮W），要求將這些物品裝進若干箱子中，使得每個箱子中裝載的物品總體積不大于W，并使所用的箱子數(shù)目最小。

在通過求解裝箱問題來生成構(gòu)件部署策略時，除了滿足經(jīng)典裝箱問題所需要考慮的箱子容量和物品體積條件外，還需要滿足硬件環(huán)境中CPU的通信鏈路數(shù)量限制。因此，需要建立裝箱過程的圖約束條件。

給定一組待部署的構(gòu)件，建立構(gòu)件間通信關(guān)系的對稱鄰接矩陣A：

其中，aij表示構(gòu)件i與構(gòu)件j之間存在數(shù)據(jù)收發(fā)關(guān)系，如果它們被部署到不同的CPU之上，則需要在兩個CPU之間建立一條RapidIO通信鏈路。后面可通過鄰接矩陣A，對構(gòu)件進行輔助搜索。

當構(gòu)件部署到CPU單元后，以CPU為頂點，CPU之間的RapidIO通信鏈路為邊，便得到一張m個頂點的無向圖G=（B，E）。要求圖的所有頂點的“度”不大于數(shù)值c（c∈N*），即每個CPU所建立的RapidIO通道數(shù)目不大于c。

基于以上符號約定，將BPPR裝箱問題用線性規(guī)劃的方式描述如下：

其中，dk表示第k個CPU（頂點）的度，變量x，y是兩個二叉決策模型，其含義分別是：

可見，BPPR裝箱問題是一個雙目標優(yōu)化問題，目標函數(shù)（1）是為了使所使用的CPU數(shù)量收斂到最小，目標函數(shù)（2）的目標是使所需要創(chuàng)建的RapidIO通道數(shù)量最小。約束公式（3）保證了單個構(gòu)件被且僅被分配到一個CPU上。約束公式（4）保證了CPU資源能夠滿足其加載的所有構(gòu)件的計算資源需求。約束公式（6）確保不會超過單個CPU的RapidIO通道限制。本文給出的BPPR模型為一維裝箱問題，實際上可以根據(jù)需要擴展到高維度裝箱問題，其原理相同。

2 ?BPPR裝箱問題求解

本文給出的BPPR裝箱問題求解方法，其特點是一種變權(quán)綜合目標函數(shù)求解算法，該算法包括兩個階段的計算，用以求解復雜的BPPR多目標優(yōu)化問題。算法結(jié)合了廣度優(yōu)先搜索技術(shù)以及可變權(quán)重的排序算法，稱為VWSOF（Variable Weight Synthesizing Objective Function）算法。第一階段，排序。通過可變組合系數(shù)法，依據(jù)物品的權(quán)重對構(gòu)件進行降序排序;第二階段，改進的FFD搜索算法，對給定的構(gòu)件序列，從降序序列中取出第一個未裝箱的物品，并采用廣度優(yōu)先搜索算法從隊列中依次取出未分配物品，求解其最優(yōu)裝箱策略。循環(huán)迭代上述兩個階段的計算過程，直到滿足收斂條件或達到預先設(shè)定的迭代次數(shù)。

VWSOF算法的主要流程如下：

第一步：參數(shù)初始化。根據(jù)BPPR裝箱問題的描述，初始化箱子和物品的參數(shù)，以及約束圖的相關(guān)參數(shù)。

第二步：采用可變組合系數(shù)法，為所有物品計算權(quán)重。變權(quán)目標函數(shù)定義如下：

公式（7）中的變量wi表示權(quán)重wi的歸一化值，變量表示ai在RapidIO數(shù)據(jù)傳輸方面的影響系數(shù)的歸一化數(shù)值。公式（8）中的變量j表示算法的第j次迭代。

第三步：根據(jù)最新的物品權(quán)重，對物品進行降序排列。

第四步：選擇一個待裝箱的物品。從排序好的物品序列中第一個尚未被裝箱的物品開始，以鄰接矩陣給出的物品間的連接關(guān)系為路徑，采用深度搜索算法BFS（Breadth First Search）搜索出下一個待裝箱的物品。

第五步：采用經(jīng)典FFD算法對物品進行裝箱。在對物品進行裝箱求解時，出判斷物品總體積是否超過箱子容積外，還需要同時滿足公式（3）、（4）、（5）、（6）的約束條件。

第六步：重復執(zhí)行步驟（四）、步驟（五），直到所有物品裝箱完成，并將裝箱結(jié)果記錄。若裝箱過程中有物品無法找到能夠滿足所有裝箱和圖約束條件的箱子來裝載，則返回步驟（二）。

第七步：重復執(zhí)行步驟（二）到步驟（六）的過程，直到達到迭代次數(shù)。

第八步：選擇近似最優(yōu)的裝箱策略。本文所設(shè)計的VWSOF算法對于多目標函數(shù)最優(yōu)化問題最佳方案的判定方法是（算法1中的步驟6），根據(jù)ListOfSolution中各備選方案所對應的無向圖G=（B，E）的頂點數(shù)量m和邊的數(shù)量E兩個評價指標進行對比。具體方法是，采用熵權(quán)法根據(jù)每個方案si的兩個指標mi和邊的數(shù)量Ei的值對指標進行賦權(quán)，進而實現(xiàn)對比。對于待評價ListOfSolution中的u個裝箱方案，和v=2個評價指標，形成原始數(shù)據(jù)矩陣R=（rij）u×v：

其中，rij表示第j個指標下第i個待評價方案的評價值。則，本文的基于熵權(quán)法的最佳方案的判定方法具體實現(xiàn)步驟如下：

①計算第j個指標下第i個項目的指標值的比重pij：

至此，得到兩個評價指標的綜合權(quán)數(shù)，對每個方案進行加權(quán)評價，選出箱子和通道資源消耗最小的一組裝箱方案為問題的最佳方案。

3 ?實驗驗證

對VWSOF算法進行實驗驗證，設(shè)置主要的圖約束條件如下：

#define inDegree 4 ?//頂點的最大入度

#define outDegree 8 ?//頂點的最大出度

#define BucketVolume 1.0 //箱子的最大容量W

#define WeidgtControl 0.6 ?//物品權(quán)重wi取值空間（0，0.6]

其中，頂點最大入度為4，頂點最大出度為8，單個箱子的最大容量為1，單個物品權(quán)重取值為（0，0.6]之間的隨機數(shù)。動態(tài)生成一定數(shù)量的物品，分別采用BFD和VWSOF算法進行裝箱，得到實驗結(jié)果如表1。

如表1所示，傳統(tǒng)BFD算法由于在裝箱過程中只根據(jù)物品重量和箱子容量進行裝箱，因此很難滿足圖的邊約束條件。而本文VWSOF算法，通?？梢杂嬎愠鰸M足圖約束條件的裝箱解。由于VWSOF算法相比BFD算法多計算了邊約束條件，因此所使用的箱子數(shù)量通常比后者多。另外，本文VWSOF算法在某些情況下也無法得到滿足約束條件的裝箱解，但是隨著迭代次數(shù)的增大，得到解的概率增大。

4 ?結(jié)論

本文給出一種基于圖約束裝箱算法的構(gòu)件調(diào)度策略生成方法，滿足基于RapidIO高速總線的嵌入式信息處理設(shè)備下，對于大量具有復雜信息交互關(guān)系的服務(wù)構(gòu)件的快速部署策略生成，并能夠充分滿足設(shè)備計算資源、RapidIO高速數(shù)據(jù)總線資源的合理利用與分配。

參考文獻：

[1]陳廷斌，魯艷霞，袁磊.面向動態(tài)服務(wù)的物聯(lián)網(wǎng)Web Services組合調(diào)度方法研究[J].情報雜志，2011，30（S2）：134-137.

[2]薄夢雅.時間序列數(shù)據(jù)壓縮算法研究[D].石家莊鐵道大學，2019.

[3]李偉，楊超宇，孟祥瑞.基于混合遺傳算法的多品種貨物裝箱問題研究[J].包裝與食品機械，2020，38（03）：51-56.