海軍裝備部裝備項(xiàng)目管理中心 林麗娜 胡子穎

本文給出一種基于圖約束裝箱算法的構(gòu)件調(diào)度策略生成算法，將構(gòu)件動(dòng)態(tài)部署和調(diào)度策略的生成描述成新的裝箱問題。實(shí)驗(yàn)表明，本文給出的基于圖約束裝箱算法的構(gòu)件調(diào)度策略生成算法，能夠較好地解決大規(guī)模構(gòu)件的動(dòng)態(tài)部署問題。

現(xiàn)有信息系統(tǒng)軟件服務(wù)構(gòu)件的部署和調(diào)度，通常采用兩種簡(jiǎn)化的策略：基于預(yù)案的方法、人工調(diào)度方法。而對(duì)于抽象問題而言，構(gòu)件部署問題屬于典型的裝箱問題，是復(fù)雜的組合最優(yōu)化問題。從計(jì)算復(fù)雜性來講，裝箱問題是一個(gè)NP完全問題，難以精確求解，當(dāng)下的解決方案是近似算法，包括FF,NF,FFD,BFD算法。

基于預(yù)案的調(diào)度方法，是事先人為制定好構(gòu)件與CPU計(jì)算單元的對(duì)應(yīng)關(guān)系，制定構(gòu)件缺省加載配置表。基于預(yù)案的調(diào)度方法缺點(diǎn)在于，對(duì)于大型復(fù)雜系統(tǒng)軟件，完全人工制定預(yù)案的方式工作量大，預(yù)案效果難以得到保證。完全人工調(diào)度的方法則存在效率低和難以給出最優(yōu)方案的問題。

本文所給出的基于圖約束裝箱算法BPPR的構(gòu)件調(diào)度策略生成方法，以嵌入式信息處理設(shè)備中的CPU為頂點(diǎn)，以CPU計(jì)算資源為頂點(diǎn)權(quán)重，以單個(gè)CPU上RapidIO高速數(shù)據(jù)傳輸通道數(shù)量限制頂點(diǎn)的最大度約束，以不同CPU之間構(gòu)件的通信鏈路為邊，形成一張圖。因此，該類構(gòu)件部署的問題即轉(zhuǎn)化為一個(gè)最優(yōu)圖的求解問題，要求滿足構(gòu)件運(yùn)行資源和數(shù)據(jù)傳輸需求的同時(shí)，使得占用的CPU數(shù)目最小，需要建立的高速數(shù)據(jù)鏈路數(shù)量最少。

1 圖約束裝箱問題BPPR的形式化表達(dá)

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

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

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

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

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

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

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

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

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

2 BPPR裝箱問題求解

本文給出的BPPR裝箱問題求解方法，其特點(diǎn)是一種變權(quán)綜合目標(biāo)函數(shù)求解算法，該算法包括兩個(gè)階段的計(jì)算，用以求解復(fù)雜的BPPR多目標(biāo)優(yōu)化問題。算法結(jié)合了廣度優(yōu)先搜索技術(shù)以及可變權(quán)重的排序算法，稱為VWSOF（Variable Weight Synthesizing Objective Function）算法。

本文所設(shè)計(jì)的VWSOF算法將問題的求解分解為兩個(gè)階段。第一階段，排序。通過可變組合系數(shù)法，依據(jù)物品的權(quán)重對(duì)構(gòu)件進(jìn)行降序排序；第二階段，改進(jìn)的FFD搜索算法，對(duì)給定的構(gòu)件序列，從降序序列中取出第一個(gè)未裝箱的物品，并采用廣度優(yōu)先搜索算法從隊(duì)列中依次取出未分配物品，求解其最優(yōu)裝箱策略。循環(huán)迭代上述兩個(gè)階段的計(jì)算過程，直到滿足收斂條件或達(dá)到預(yù)先設(shè)定的迭代次數(shù)。

VWSOF也是一種近似算法，算法為迭代求解過程，通過Niter次迭代后，得到一個(gè)近似最優(yōu)的裝箱策略，最后從若干有效解中選出最優(yōu)的一個(gè)。VWSOF算法的主要流程如下：

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

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

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

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

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

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

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

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

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

（1）計(jì)算第j個(gè)指標(biāo)下第i個(gè)項(xiàng)目的指標(biāo)值的比重pij：

（2）計(jì)算第j個(gè)指標(biāo)的熵值ej：

（3）計(jì)算第j個(gè)指標(biāo)的熵權(quán)：

至此，得到兩個(gè)評(píng)價(jià)指標(biāo)的綜合權(quán)數(shù)，對(duì)每個(gè)方案si進(jìn)行加權(quán)評(píng)價(jià)，選出箱子和通道資源消耗最小的一組裝箱方案為問題的最佳方案。

3 實(shí)驗(yàn)驗(yàn)證

對(duì)VWSOF算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，設(shè)置主要的圖約束條件如下：

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

表1 本文VWSOF算法核心流程

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

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

（1）將基于RapidIO高速數(shù)據(jù)總線的嵌入式設(shè)備下構(gòu)件的調(diào)度問題抽象為一種全新的基于圖約束的裝箱問題BPPR，是一種多目標(biāo)函數(shù)優(yōu)化問題，并給出問題的形式化表示。

（2）給出所設(shè)計(jì)的BPPR問題的近似求解方法，一種變權(quán)綜合目標(biāo)函數(shù)求解算法，將復(fù)雜的多目標(biāo)函數(shù)最優(yōu)化問題分解為可變權(quán)重排序和基于廣度搜索BFS和FFD裝箱算法相結(jié)合的兩個(gè)計(jì)算階段，并給出基于熵權(quán)法的多指標(biāo)裝箱方案對(duì)比方法。

與現(xiàn)有構(gòu)件調(diào)度策略相比，本文給出的構(gòu)件調(diào)度策略生成算法既保證了構(gòu)件調(diào)度策略計(jì)算的高效性和準(zhǔn)確性，同時(shí)保證了適當(dāng)?shù)撵`活性和擴(kuò)展性，可以推廣到其他類似設(shè)備的構(gòu)件調(diào)度問題的解決。