和 楓，王曉明，葉志鵬，沈海闊

（1.北京宇航系統(tǒng)工程研究所，北京，100076；2.北京交通大學(xué)，北京，100044）

0 引言

測(cè)試在制造業(yè)，尤其是在航空航天以及特種設(shè)備制造領(lǐng)域中具有舉足輕重的作用，新的產(chǎn)品開發(fā)通常需要一系列的測(cè)試項(xiàng)目。一般來說，每臺(tái)設(shè)備由多個(gè)子系統(tǒng)組成，每個(gè)子系統(tǒng)都需要通過一些特定的測(cè)試項(xiàng)目。要測(cè)試的子系統(tǒng)被命名為待測(cè)單元，待測(cè)單元的特定測(cè)試項(xiàng)被命名為測(cè)試任務(wù)。待測(cè)單元的不同測(cè)試任務(wù)可能有預(yù)定的技術(shù)測(cè)試順序，并且取決于不同類型的資源（儀器）。技術(shù)測(cè)試順序的限制來源于測(cè)試任務(wù)的工程需求，即部分測(cè)試任務(wù)必須在其他相關(guān)任務(wù)完成后才能開展測(cè)試。

對(duì)于并行測(cè)試任務(wù)其目標(biāo)可以是單一的，也可以是多個(gè)。Jain和Grossman［1］首先將并行測(cè)試任務(wù)調(diào)度建模為一個(gè)混合整數(shù)線性規(guī)劃模型，該模型將兩個(gè)相關(guān)目標(biāo)加權(quán)為單個(gè)優(yōu)化目標(biāo)。與上述線性加權(quán)法不同，Lu等［2-6］針對(duì)該優(yōu)化問題提出了一系列基于帕累托法則的優(yōu)化方法，主要是采用NSGA-II作為算法框架［3-5］，提出可變鄰域方法使交叉跨度合理［5］，利用混沌映射避免陷入局部最優(yōu)［4］，其中考慮了最小化最大測(cè)試完成時(shí)間和平均工作量兩個(gè)待優(yōu)化目標(biāo)。此外，其對(duì)特定場(chǎng)景下的單目標(biāo)優(yōu)化也進(jìn)行了充分的研究。Do Ngoc等［7］考慮大型發(fā)動(dòng)機(jī)測(cè)試過程的額外空間和時(shí)間約束，利用遺傳算法來尋找候選項(xiàng)目的最佳組合，以獲得最大利潤。對(duì)于具有單一目標(biāo)的標(biāo)準(zhǔn)TTSP，Lu 和Zhang［8］采用分布估計(jì)算法求解測(cè)試任務(wù)排序，并結(jié)合禁忌搜索防止迂回搜索。Shi 等［9］提出了解決TTSP 中資源沖突的方案選擇規(guī)則，并開發(fā)了遺傳算法來尋找合適的任務(wù)序列。隨后，Yang等［10］在充分考慮預(yù)先確定的技術(shù)測(cè)試順序的基礎(chǔ)上，重點(diǎn)研究了標(biāo)準(zhǔn)TTSP，提出了隱含序列尋找過程和基于序列的迭代優(yōu)化過程，以減少計(jì)算時(shí)間。Liao等［11］研究了在有交貨期限制的過載情況下的加權(quán)任務(wù)，其目標(biāo)是使延遲任務(wù)的總權(quán)重值最小。約束滿足問題通常出現(xiàn)在拓?fù)鋵W(xué)研究領(lǐng)域［12］，其主要特點(diǎn)是變量之間存在指定的拓?fù)潢P(guān)系［13］，但約束滿足技術(shù)也已廣泛應(yīng)用于規(guī)劃和調(diào)度等領(lǐng)域［14］。求解約束滿足問題的關(guān)鍵步驟是構(gòu)造一個(gè)不違反任何拓?fù)潢P(guān)系約束的可行調(diào)度［15］。

并行測(cè)試任務(wù)調(diào)度在于縮短測(cè)試進(jìn)程的最終完成時(shí)間，對(duì)于本文而言，每個(gè)測(cè)試任務(wù)的可用資源都有各自的依賴關(guān)系。因此，需要設(shè)計(jì)有效的算法保證各測(cè)試任務(wù)在依賴資源無沖突的前提下，滿足測(cè)試任務(wù)間的既定時(shí)序依賴關(guān)系，而國內(nèi)外學(xué)者對(duì)此類問題鮮有研究。本研究通過對(duì)每個(gè)任務(wù)編碼以及輸入既定各測(cè)試任務(wù)間的時(shí)序約束與任務(wù)與資源間的依賴關(guān)系，通過設(shè)計(jì)有效的人工蜂群啟發(fā)式算法（Hybrid artifical Bee Colong，H-ABC）進(jìn)行優(yōu)化，以獲得各測(cè)試任務(wù)在其相應(yīng)資源上的先后安排，同時(shí)使得最終測(cè)試項(xiàng)目的完成時(shí)間最小化。

1 H-ABC算法理論研究

首先通過定義以下符號(hào)集對(duì)本項(xiàng)目所需解決的問題做如下簡要概述。令集合T={ti：1 ≤i≤m}表示m個(gè)測(cè)試任務(wù)，集合R={rk：1 ≤k≤n}表示n個(gè)測(cè)試所需的資源或設(shè)備，集合τ={τi：1 ≤i≤m}對(duì)應(yīng)于所有測(cè)試任務(wù)的時(shí)間消耗，TR是一個(gè)m×n維的矩陣，表示測(cè)試任務(wù)和資源之間的依賴關(guān)系。矩陣TS表示預(yù)定的技術(shù)測(cè)試順序矩陣，與實(shí)際問題需要滿足的約束有關(guān)，例如TS(1)=[i，j]表示對(duì)任務(wù)ti的測(cè)試必須在對(duì)任務(wù)tj的前面。為了實(shí)現(xiàn)并行測(cè)試，可以通過預(yù)定的線程數(shù)量d來同時(shí)處理不同的測(cè)試任務(wù)，所有滿足TS限制的時(shí)間序列都可以被認(rèn)為是可行的解決方案。

另外，本項(xiàng)目所需解決的問題可以做如下改進(jìn)：

a）任何資源最多可以同時(shí)由一個(gè)測(cè)試任務(wù)占用；

b）占用資源的時(shí)間消耗等于相關(guān)測(cè)試任務(wù)的時(shí)間消耗；

c）所有測(cè)試任務(wù)的排序必須滿足預(yù)定的技術(shù)測(cè)試順序；

d）所有資源上同時(shí)測(cè)試的任務(wù)數(shù)量必須小于預(yù)定的線程數(shù)量。這個(gè)問題的目標(biāo)是盡量減少上次測(cè)試任務(wù)的完成時(shí)間。

為建立一個(gè)標(biāo)準(zhǔn)的整數(shù)規(guī)劃模型，以下內(nèi)容首先定義了相關(guān)的決策變量。令二值變量zij∈{0，1}表示任務(wù)ti與任務(wù)tj之間的排布關(guān)系，其中zij=1表示任務(wù)tj排布在任務(wù)ti之后（可以不連續(xù)），反之表示任務(wù)tj排布在任務(wù)ti之前。令非負(fù)整型變量si表示任務(wù)ti的最早開始測(cè)試時(shí)間，因此任務(wù)ti完成測(cè)試的時(shí)間為si+τi。非負(fù)整型變量Tmax表示整個(gè)并行測(cè)試系統(tǒng)的完工時(shí)間。此外，M表示為一個(gè)極大的正整數(shù)，在數(shù)學(xué)模型中對(duì)非關(guān)鍵約束起到虛化的作用。

該問題的混合整數(shù)規(guī)劃線性模型建立如下：

式（1）表示為模型的目標(biāo)函數(shù)，即為最小化整個(gè)系統(tǒng)的總測(cè)試時(shí)間。剩余公式定義了本模型的約束和決策變量。約束（2）為各測(cè)試任務(wù)完工時(shí)間的時(shí)序約束。當(dāng)TS(i，j)=1 時(shí)，約束1 轉(zhuǎn)化為si+τi≤sj+τj，即要求任務(wù)tj的結(jié)束時(shí)間大于任務(wù)ti；反之，模型中沒有任務(wù)tj與任務(wù)ti的結(jié)束約束。約束（3）、（4）是保證多任務(wù)占用資源的非沖突約束。在約束（3）和約束（4）中，當(dāng)存在條件TR(i，k)·TS(j，k)=1 時(shí)，表明任務(wù)ti與任務(wù)tj都與資源rk有關(guān)聯(lián)。為避免出現(xiàn)這兩個(gè)任務(wù)搶占同一資源的情況，任務(wù)ti與任務(wù)tj必然存在其完成時(shí)間與開始時(shí)間的時(shí)序關(guān)系。因此，約束（3）與約束（4）有效，反之，約束（3）與約束（4）不存在于模型中。同時(shí)，二值變量zij保證了兩個(gè)任務(wù)之間無沖突的時(shí)序關(guān)系；當(dāng)zij=1時(shí)，約束（3）轉(zhuǎn)換為sj≥τi+si，即任務(wù)tj在任務(wù)ti之后，而約束（4）無效；當(dāng)zij=0 時(shí)，約束（4）轉(zhuǎn)換為si≥τj+sj，即任務(wù)ti在任務(wù)tj之后，而約束（3）無效。約束（5）建立了整個(gè)系統(tǒng)測(cè)試完工時(shí)間與測(cè)試任務(wù)之間的關(guān)系，即測(cè)試結(jié)束時(shí)間Tmax為所有測(cè)試任務(wù)結(jié)束時(shí)間的最大值。約束（6）和（8）為相應(yīng)的決策變量定義。

2 H-ABC算法設(shè)計(jì)

H-ABC 算法首先通過時(shí)序遞歸搜索找到一系列任務(wù)隱含序列，然后依次執(zhí)行全局個(gè)體優(yōu)化、部分個(gè)體強(qiáng)化和少量個(gè)體淘汰3個(gè)主搜索流程，糾正找到的隱含序列ABC 算法的單個(gè)編碼。在執(zhí)行全局個(gè)體優(yōu)化和少量個(gè)體強(qiáng)化流程時(shí)，均會(huì)依次執(zhí)行二進(jìn)制選擇、鄰域搜索模塊、隱集編碼修正，如果隨機(jī)搜索的概率滿足局部搜索條件，還會(huì)執(zhí)行局部搜索模塊以及再一次的隱集編碼修正。

不同的是，在全局個(gè)體優(yōu)化搜索流程中，每次進(jìn)入鄰域搜索模塊的是一個(gè)順序選擇個(gè)體和一個(gè)經(jīng)過二進(jìn)制選擇的個(gè)體；而進(jìn)入部分個(gè)體強(qiáng)化搜索流程中鄰域搜索模塊兩個(gè)個(gè)體均為經(jīng)過二進(jìn)制選擇的個(gè)體。當(dāng)執(zhí)行完全局個(gè)體優(yōu)化和部分個(gè)體強(qiáng)化搜索流程后，則會(huì)在少量個(gè)體淘汰搜索流程階段對(duì)超過限定迭代次數(shù)而未優(yōu)化的個(gè)體進(jìn)行淘汰。最后，經(jīng)過一次迭代之后更新全局最優(yōu)個(gè)體記錄。H-ABC 算法的基本流程如圖1所示。

圖1 優(yōu)化算法基本流程Fig.1 Flow chart of the optimization algorithm

圖1中的二進(jìn)制選擇主要用來進(jìn)行高質(zhì)量個(gè)體的選擇，其操作為從種群中連續(xù)隨機(jī)選擇兩個(gè)不同的個(gè)體，然后選擇這對(duì)個(gè)體中最佳的（適應(yīng)度值最高的）作為二進(jìn)制選擇的輸出個(gè)體。

2.1 時(shí)序遞歸搜索技術(shù)

時(shí)序遞歸搜索技術(shù)是為了找到一系列任務(wù)隱含序列，這些序列不違反屬于每個(gè)待測(cè)單元任務(wù)的預(yù)定測(cè)試順序，然后使用找到的隱含序列糾正ABC 算法的單個(gè)編碼。讓序列表示包含受限制任務(wù)w的待測(cè)單元的序列，Zw是包含輸出子序列?Zw的矩陣。此外，Qw=是一個(gè)標(biāo)準(zhǔn)序列。標(biāo)簽設(shè)置（Lebel Settings，LS）算法是一個(gè)典型的遞歸過程，li=(i，，)表示LS 中的標(biāo)簽，其中i是任務(wù)編碼，是在任務(wù)i結(jié)束的分區(qū)計(jì)劃，是任務(wù)集，可在節(jié)點(diǎn)i擴(kuò)展。假設(shè)lj=(j，，)是li的后繼標(biāo)簽，因此可以根據(jù)擴(kuò)展方程對(duì)li進(jìn)行擴(kuò)展，如式（9）所示。

2.2 鄰域搜索技術(shù)

鄰域搜索技術(shù)結(jié)合了多點(diǎn)插入算子與多點(diǎn)交換算子，該技術(shù)旨在對(duì)一個(gè)個(gè)體編碼及其鄰域編碼實(shí)現(xiàn)高質(zhì)量的子代編碼搜索。假設(shè)Xt是一個(gè)按照順序選擇的個(gè)體，Xf為通過二進(jìn)制選擇的一個(gè)個(gè)體，即為Xt的鄰域個(gè)體。鄰域搜索流程主要依據(jù)概率Pnbr執(zhí)行，如果隨機(jī)概率大于Pnbr，則只對(duì)Xt執(zhí)行多點(diǎn)交換算子。如果隨機(jī)概率小于Pnbr，則首先判斷兩個(gè)體的適應(yīng)度值，如果適應(yīng)度值相同，仍然只對(duì)Xt執(zhí)行多點(diǎn)交換算子，否則，對(duì)兩個(gè)體執(zhí)行多點(diǎn)交換算子獲得子代編碼。

多點(diǎn)插入算子：基于既定的交換點(diǎn)數(shù)量與兩個(gè)個(gè)體，通過給定的規(guī)則生成子個(gè)體。Nnbr表示為既定交換的個(gè)體中的節(jié)點(diǎn)數(shù)量。例如，Xt和Xf可以分別被表示 為Xt=(1，5，3，2，9，8，10，7，4，6) 和Xf=（2，6，5，9，3，1，7，8，4，10）。在Xt中隨機(jī)選擇Nnbr（通常Nnbr=3）個(gè)保留點(diǎn)位，則包含保留點(diǎn)位的Xt可以被表示為

其中，x表示Xt的空白位置。隨后，從Xf中抽取非Xt中保留點(diǎn)位的其他數(shù)值并依次填充入Xt。最終的Xt可以被重新生成為Xt=（6，5，3，2，9，1，7，8，4，10）。上述過程是多點(diǎn)插入算子的標(biāo)準(zhǔn)流程，多點(diǎn)插入算子擅長于在調(diào)度問題中更大幾率發(fā)現(xiàn)質(zhì)量更高的解。

多點(diǎn)交換算子：針對(duì)既定的一個(gè)編碼，通過多個(gè)點(diǎn)的位置交換，從而產(chǎn)生一個(gè)新個(gè)體編碼。多點(diǎn)交換算子依據(jù)一個(gè)隨機(jī)產(chǎn)生的交換點(diǎn)數(shù)量Ns，然后隨機(jī)交換Ns個(gè)節(jié)點(diǎn)的位置，從而產(chǎn)生新編碼。該算子旨在通過多點(diǎn)交換方式從而避免算法陷入局部最優(yōu)的情況。

2.3 局部搜索技術(shù)

局部搜索技術(shù)結(jié)合了貪婪搜索過程，通過局部枚舉的方式盡可能地實(shí)現(xiàn)高質(zhì)量解編碼的生成。局部搜索算子通過一個(gè)弱枚舉的循環(huán)，最大限度地提升個(gè)體解的質(zhì)量。對(duì)于個(gè)體編碼Xt=（x1，x2，…，xi，…，xm），將第1 個(gè)任務(wù)編號(hào)x1與相鄰位置進(jìn)行交換；如果x1交換后無法提高Xt的質(zhì)量（適應(yīng)度值），則重復(fù)上述過程；如果x1交換后提高了解Xt的質(zhì)量（適應(yīng)度值），則終止循環(huán)返回當(dāng)前生成的新個(gè)體。局部搜索算子的執(zhí)行效率較低，但可以配合彌補(bǔ)其他算子收斂性不強(qiáng)的不足。

本文綜合多種搜索技術(shù)，可以有效解決多模態(tài)問題即存在多個(gè)局部最優(yōu)解的問題，可以更好地探索全局搜索空間，減少陷入局部最優(yōu)解的風(fēng)險(xiǎn)。同時(shí)，可以更好地處理問題的多樣性，將問題分解為更小的可管理部分，并針對(duì)每個(gè)部分選擇合適的搜索策略。而傳統(tǒng)的啟發(fā)式算法多采用單一搜索技術(shù)求解最優(yōu)序列，求解效率低，易陷入局部最優(yōu)，面對(duì)復(fù)雜問題甚至可能無法求出最優(yōu)解。

3 實(shí)例分析

本部分首先采用隨機(jī)生成的算例測(cè)試H-ABC 的效率和最優(yōu)性。其中，對(duì)于小規(guī)模問題采用整數(shù)規(guī)劃精確算法（Mixed Integer Pragramnrg，MIP）作為HABC的對(duì)比算法，驗(yàn)證H-ABC的最優(yōu)性和求解效率。此外，采用了隨機(jī)生成的大規(guī)模算例n=100，以驗(yàn)證H-ABC 算法的極限性能。測(cè)試用例提供了小規(guī)模算例的具體數(shù)據(jù)，并通過甘特圖展示了大小規(guī)模算例的求解結(jié)果。

其次，在并行測(cè)試任務(wù)的真實(shí)案例上對(duì)算法的性能和優(yōu)化過程進(jìn)行了進(jìn)一步的驗(yàn)證，對(duì)優(yōu)化結(jié)果和迭代過程進(jìn)行了展示。

3.1 小規(guī)模用例算法性能測(cè)試

小規(guī)模測(cè)試用例1 如表1 所示，規(guī)模為任務(wù)數(shù)量m=8，資源數(shù)量n=7的測(cè)試用例數(shù)據(jù)。

表1 小規(guī)模測(cè)試用例1Tab.1 Small-scale test example 1

表1 展示了規(guī)模為任務(wù)數(shù)量為m=8 以及資源數(shù)量為n=7的一個(gè)小規(guī)模算例，其中該算例沒有任務(wù)間的時(shí)序約束。表1的算例分別調(diào)用了基于MIP模型的商業(yè)求解器以及H-ABC 算法求解。兩算法都求解到了該算例的最優(yōu)解，即最優(yōu)完工時(shí)間為Tmax=47，兩算法都在1 秒內(nèi)求解到最優(yōu)解，其最優(yōu)解的甘特圖如圖2所示。

圖2 小規(guī)模測(cè)試用例1結(jié)果甘特圖Fig.2 Gantt chart of example 1

小規(guī)模測(cè)試用例2 如表2 所示，規(guī)模為任務(wù)數(shù)量為15，資源數(shù)量為5的測(cè)試用例數(shù)據(jù)。

表2 小規(guī)模測(cè)試用例2Tab.2 Small-scale test example 2

表2展示了任務(wù)數(shù)量為15以及資源數(shù)量為5的一個(gè)小規(guī)模算例，其中該算例有預(yù)定時(shí)序約束。表2的算例同樣分別調(diào)用了MIP模型以及H-ABC算法求解。兩算法都求解到了該算例的最優(yōu)解，即最優(yōu)完工時(shí)間為Tmax=412。兩種算法都在7 s內(nèi)求解到最優(yōu)解，其最優(yōu)解的甘特圖如圖3所示。

圖3 小規(guī)模測(cè)試用例2結(jié)果甘特圖（有時(shí)序約束）Fig.3 Gantt diagchart ram of example 2（with temporal constraints）

圖4 展示了表2 數(shù)據(jù)下沒有預(yù)定時(shí)序約束的算例結(jié)果。兩算法都求解到了該算例的最優(yōu)解，即最優(yōu)完工時(shí)間為Tmax=412，MIP 的求解時(shí)間為122.6 s，H-ABC的求解時(shí)間小于10 s。MIP模型在無時(shí)序約束的問題下，求解性能會(huì)顯著下降。相比于MIP 模型，H-ABC在求解大規(guī)模算例方面有著較大優(yōu)勢(shì)。

圖4 小規(guī)模測(cè)試用例2結(jié)果甘特圖（無時(shí)序約束）Fig.4 Gantt chart of example 2（without temporal constraints）

3.2 大規(guī)模用例算法性能測(cè)試

大規(guī)模算例：任務(wù)數(shù)量m=100，資源數(shù)量n=10，結(jié)果如圖5所示。

圖5 大規(guī)模測(cè)試用例結(jié)果甘特圖Fig.5 Gantt chart of large-scale test example

對(duì)大規(guī)模算例，H-ABC 算法可以完全滿性能需求。H-ABC 搜索到最小的完工時(shí)間為Tmax=3 964，HABC 的求解時(shí)間約為412 s。對(duì)于該規(guī)模的問題，MIP模型以及常用求解已無法處理。相比現(xiàn)行傳統(tǒng)求解器對(duì)該問題的求解性能，H-ABC 在求解加大規(guī)模算例方面有極大優(yōu)勢(shì)。

3.3 算法優(yōu)化流程展示

圖6 至圖9 展示了任務(wù)數(shù)為15，資源數(shù)為5 時(shí)的規(guī)模示例調(diào)用H-ABC算法進(jìn)行迭代收斂的相關(guān)結(jié)果。其中，鄰域搜索概率為0.7，局部搜索概率為0.3，最大迭代次數(shù)為100。完工時(shí)間隨迭代次數(shù)的收斂曲線如圖6所示。圖7至圖9則分別展示了第1次、第4次及第5次迭代結(jié)果的甘特圖，相應(yīng)的完工時(shí)間分別為438 s、415 s、412 s。

圖6 H-ABC求解上述15×5規(guī)模示例的算法收斂Fig.6 Algorithm convergence process of the 15×5 scale example

圖7 第1次迭代結(jié)果的甘特圖：完工時(shí)間438 sFig.7 Gantt chart of the first iteration: completion time 438 s

圖8 第4次迭代結(jié)果的甘特圖：完工時(shí)間415Fig.8 Gantt chart of the fourth iteration: completion time 415

圖9 第5次迭代結(jié)果的甘特圖：完工時(shí)間412 sFig.9 Gantt chart of the 5th iteration: completion time 412 s

圖10和圖11分別展示了任務(wù)數(shù)為46和80的大規(guī)模測(cè)試的結(jié)果，由于測(cè)試任務(wù)的規(guī)模較大，難以用甘特圖去展示其迭代結(jié)果，因此只繪制了完工時(shí)間和CPU迭代耗時(shí)的收斂曲線。由圖10a可以看出，完工時(shí)間在迭代40次左右趨于穩(wěn)定，耗時(shí)1 064 s；圖10b顯示了任務(wù)數(shù)為46 時(shí)，進(jìn)行100 次迭代CPU 耗時(shí)229.23 s。當(dāng)測(cè)試任務(wù)達(dá)到80 次時(shí)，完工時(shí)間收斂于2 493 s，算法迭代CPU 耗時(shí)1 113.62 s，具體結(jié)果如圖11a和11b所示。

圖10 H-ABC求解46×10規(guī)模示例性能展示Fig.10 Performance of H-ABC solving 46×10 scale example

圖11 H-ABC求解80×10規(guī)模示例性能展示Fig.11 Performance of H-ABC solving 80×10 scale example

4 結(jié)束語

H-ABC 算法可以通過迭代的方式找到測(cè)試任務(wù)的最優(yōu)方案，極大縮短測(cè)試流程所用的總時(shí)間。通過小規(guī)模用例和大規(guī)模用例測(cè)試，H-ABC 算法都可以實(shí)現(xiàn)目標(biāo)，驗(yàn)證了算法的普適性。本算法可應(yīng)用于相關(guān)弱約束條件復(fù)雜內(nèi)容執(zhí)行過程的優(yōu)化處理，較傳統(tǒng)MIP算法表現(xiàn)出更高的收斂效率和執(zhí)行效果。