一種并行測試任務調度優化方法

王正元, 劉衛東, 景慧麗, 屈娜

(西安高技術研究所， 陜西 西安 710025)

0 引言

一些導彈武器、雷達裝備在作戰使用前需要按照一定工序測試維護，測試合格的武器裝備才能投入使用[1-3]。通常情況下，測試車間預設多條測試流水線，每1條流水線上從左至右預先布置了多個工位，任意1條流水線上最多同時容納一定數量的裝備接受測試，任意工位任意時刻最多對1臺裝備進行測試，1臺裝備任意時刻最多在1個工位接受測試，所有裝備從測試車間入口到某一流水線按照固定工位順序接受測試，測試完后從出口離開測試車間。戰時通常有多臺同類別不同型號的裝備進入測試車間接受測試，為保障作戰任務順利進行，要求全部裝備完成測試所需時間越短越好。確定裝備測試順序，使得測試任務完成時間最短的問題就是一種裝備測試任務調度問題。

裝備測試任務調度問題實際上是一種并行任務調度問題。在每1條流水線上，各臺裝備測試任務調度問題與同順序作業調度問題(FSP)類似。由于1條流水線上同時只能容納一定數量的裝備接受測試，導致該問題與FSP不同。此外，測試車間存在多條流水線，因而需要把待測試裝備分配給各條流水線。裝備測試調度問題的特點使得問題精確求解變得較為困難，目前主要采用仿真方法[1]、Petri網[4]、計劃評審技術(PERT)[5]、分支定界法[6]、圖染色理論[7]以及智能優化方法[8-16]計算調度方案，在計算過程中為簡化問題有時采用優先權方法[1-3]。裝備并行測試任務調度問題中，各裝備測試順序是可調整的，相應的網絡結構也是可調整的，因而可利用PERT方法計算完工時間；實際問題求解過程中有一些規律可用于簡化問題求解，如問題的下界、按照一定規律排列的待測試裝備分配方案等。本文針對一種特殊的裝備并行測試任務調度問題，建立了數學模型，并提出了該問題的啟發式求解方法。根據裝備測試任務調度問題的特點，提出了單一流水線裝備測試任務調度問題的下界算法，利用下界算法進行各流水線待測試裝備初始分配，構造了裝備并行測試任務調度優化問題的求解算法，較好地解決了裝備測試任務調度優化問題。

1 裝備測試任務調度問題數學模型

裝備測試任務調度的目的是為了在盡可能短的時間內完成裝備測試任務，因而可以選擇測試任務完成時間為目標函數。假設共有某類別m種不同型號裝備等待測試，型號i的裝備ni臺，共有測試流水線h條。每臺裝備最多在n個工位完成測試，每個工位執行一道工序，型號i的裝備在工位j上測試時間為tij. 安排在流水線u(u≤h)上測試的第k臺裝備型號為yku，流水線u上測試型號i的裝備xiu臺，1條流水線上任意時刻最多a臺裝備處于測試狀態，任意工位任何時刻最多只測試1臺裝備。為簡單起見，下面僅考慮a=2，a>2時可用類似方式得到相應結論。裝備測試任務調度問題數學模型為

s.t.

dj+1(k,u)=
max{dj(k,u),dj+1(k-1,u)}+tykuj,k>1，
dj+1(1,u)=dj(1,u)+ty1uj，
d1(k,u)=d1+n(k-2,u),k>2d1(k,u)=d1+n(k-2,u)，k>2,
d1(k,u)=0,k=1,2.

(1)

(2)

(3)

yku=1,2,…,m,
y1u≠y2u.

(4)

其中

約束條件(1)式確保1條流水線上最多2臺裝備處于測試狀態，并且1個工位最多1臺裝備處于測試狀態；約束條件(2)式使得在h條流水線上測試完各型號裝備；約束條件(3)式使得各型號待測試裝備都安排到第u條流水線；約束條件(4)式使得測試裝備型號在給定的型號范圍內。

2 單一流水線上裝備測試任務調度問題的下界

單一流水線u(u=1,2,…,h)上待測試裝備給定時，各工位測試時間總和為

(5)

由于同一流水線上最多允許2臺裝備在不同工位上測試，任何時刻都有2臺裝備處于測試狀態時，完成測試全部裝備的時間為T(u)/2. 實際上，測試裝備在1個工位測試結束后，后續測試裝備才能使用該工位，因而完成測試全部裝備的時間不小于T(u)/2. 此外，所有裝備都必須在最后1個工位上測試，不妨假設倒數第2臺裝備測試完后立即在工位n上測試最后1臺裝備，這樣完成測試任務時間最短。

定理1流水線u上，給定待測試各型號裝備數量xiu(i=1,2,…,m)，型號i的裝備在工位j所需測試時間為tij，流水線同時容納2臺裝備進行測試，任意時刻每個工位最多對1臺裝備進行測試，則得到單一流水線裝備測試任務調度問題的下界，即單一流水線上完成全部測試任務所需時間的下界為

(6)

證明：假設流水線u上待測試裝備按照一定次序排放，奇數、偶數序號裝備測試完畢所需時間總和分別記為To、Te，而各工位上測試全部裝備所需時間和為

則

To+Te=T(u).

不妨設最后1臺裝備序號為奇數，記

tmin=min {tin|xiu>0,i=1,2,…,m},

則測試完成時間T滿足

T≥max {To-tmin,Te}+tmin≥
(To-tmin+Te)/2+tmin=
(To+tmin+Te)/2=
(T(u)+tmin)/2,

所以完成全部測試任務所需時間的下界為

B(u)=(T(u)+min {tin|xiu>0,i=1,2,…,m})/2.

流水線上待測試裝備已排序時，奇偶數序號裝備測試任務所需時間分別為To、Te，則下界B(u)為

(7)

3 單一流水線裝備測試任務調度問題求解的啟發式方法

給定流水線上待測試裝備時，裝備測試任務調度問題就是一種排序問題。利用問題的領域知識構造啟發式方法，可以實現問題的快速求解。對于單一流水線上裝備測試任務調度問題，啟發式求解方法步驟描述如下。

算法1單一流水線上裝備測試任務調度問題求解的啟發式方法。

步驟1輸入待測試各型裝備數量xiu(i≤m)，輸入各型號裝備在各工位上測試時間tij(1≤j≤n)，計算流水線u上待測試的裝備總量為

步驟2首先將裝備測試序號分成兩個子集，相應裝備在流水線上奇數或偶數序號測試。

步驟4改變當前解中裝備的測試順序，得到解Y.

步驟5計算目標函數值f(u)，如果f(u)

步驟6改變兩個子集的組成，按(7)式計算測試時間下界B(u)，若B(u)

步驟7比較不同子集劃分方式對應近似解的目標函數值，選擇最優目標函數值對應近似解為裝備測試任務調度問題的解。

求解過程通常從最均衡的子集開始，即優先考慮下界最小的情形。計算得到測試調度初始方案以后，再考慮下界略大的子集情形。一旦某種子集對應下界高于已得到調度方案目標值，則可以結束計算。由于使用了(7)式計算測試時間下界，可以很快確定有些情況不能得到最優解，從而簡化了問題求解過程。

4 多流水線待測試裝備分配方法

裝備測試任務在多條測試流水線上進行時，首先需要進行待測試裝備在不同流水線上的分配。實際問題求解過程中，通常需要對多流水線待測試裝備進行多次重分配，每次分配都是圍繞一個基準方案展開。基準方案中，各流水線上分配的測試任務量盡可能靠近，即每條流水線上各工位完成測試任務所需時間之和與各流水線上平均測試任務量A的誤差平方和最小。由于

是常量，選擇多流水線待測試裝備初始分配模型為

模型求解步驟描述如下。

算法2多流水線待測試裝備初始分配模型求解方法。

步驟1輸入待測試各型裝備數量ni(1≤i≤m)，在各工位測試時間tij(1≤j≤n)。

步驟2將各型號待測試裝備按照每臺裝備所需測試時間由大到小依次分配到各流水線，已分配測試任務量最小的流水線優先分配任務，直到全部待測試裝備分配完畢。

步驟3計算各流水線分配測試任務總量，調整承擔測試任務量最大、最小流水線的裝備測試任務，直到不能調整。

對于實際問題，依據各流水線待測試裝備分配結果進一步求解裝備測試任務調度問題，計算結果與問題的下界偏差較大。為了進一步降低完成測試任務所需時間，需要對分配給各流水線的待測試裝備進行調整。調整時主要圍繞初始分配模型的解展開，在目標函數值變化不大的范圍內尋找可進一步降低完成測試任務所需時間的解。

5 裝備并行測試任務調度問題求解的啟發式方法

裝備并行測試任務調度問題求解過程較為復雜，可以把它分解為多個子問題迭代求解得到問題的解。問題求解步驟描述如下。

算法3裝備并行測試任務調度問題求解的啟發式方法。

步驟1輸入流水線數量h、工位數n、裝備型號數m，各型號裝備數量ni(1≤i≤m)，型號i裝備在工位上測試所需時間tij(1≤j≤n)。

步驟2使用算法2計算各流水線待測試裝備初始分配方案。

步驟3使用算法1計算各流水線裝備測試任務調度方案，得到這時裝備測試任務完成所需時間為

步驟4改變各流水線待測試裝備分配方案，使用下界算法計算各流水線裝備測試任務完成所需時間的下界B(u).

步驟5選擇滿足Tf>max {B(u)|1≤u≤h}的待測試裝備分配方案。

步驟6使用算法1計算各流水線裝備測試任務調度方案，得到這種情況下裝備測試任務完成所需時間T′f.

步驟7如果T′fmax {B(u)|1≤u≤h}的待測試裝備分配方案。

步驟8輸出計算結果，退出計算。

6 實例分析

現有2條流水線，每條流水線上有7個工位，需要測試交付使用的裝備數量及其在各工位上測試所需時間如表1所示。

每條流水線上最多容納2臺裝備同時測試，任意時刻每個工位最多測試1臺設備，每臺裝備均從工位1開始測試(時間為0時不需要測試)，到工位7上測試完畢后離開測試流水線。確定甲、乙、丙3型裝備測試任務調度方案，使得測試任務完成時間盡可能短。

表1 待測試裝備數量及其在各工位測試時間

為了計算較好的裝備測試任務調度初始方案，采用算法2求得2條流水線上待測試裝備初始分配方案，裝備初始分配方案為型號甲、乙、丙的裝備數量相同，即2條流水線上各有5臺甲型裝備、5臺乙型裝備和10臺丙型裝備。使用算法1求解裝備測試任務調度方案如表2所示，2條流水線上任務調度方案相同，完成測試時間為635 s.

表2 裝備測試任務調度初始方案

對于單一流水線上裝備測試任務調度，給定20臺待測試裝備時共涉及36種情況，求解時只需考慮6種情形(下界不超過635 s)，計算量大大減少。利用定理1，得到這種情況下裝備測試任務調度問題下界為624 s，與當前解對應目標函數值635 s有一定差距。按照算法3，改變2條流水線上待測試裝備分配方案，不考慮下界大于635 s的分配方案，選擇滿足條件的新分配方案如表3所示。

表3 2條流水線上待測試裝備分配方案

使用算法1計算新分配方案下裝備測試任務調度方案，結果如表4所示。

待測試裝備新分配方案中，流水線1承擔測試任務量1 248 s，完成測試任務所需時間下界628 s，測試任務調度方案對應完成測試時間632 s；流水線2承擔測試任務量1 232 s，完成測試任務所需時間下界620 s，測試任務調度方案對應完成測試時間624 s. 因而，完成全部測試任務只需632 s，比初始方案縮短3 s.

表4 調整后裝備測試任務調度方案

求解過程中，利用對問題自身的認識，從任務量最均衡時特殊初始解出發得到較好的近似解，進一步利用給定待測試裝備分配方案下測試任務調度問題的下界與當前最優解目標函數值比較，可以預先排除一些分配方案，從而可以減少計算量，提高問題求解效率。如例中，按照算法3，改變測試任務量分配時，總計1 271種情形，只需考慮11種(2條軌道中最大測試任務量介于1 240 s與1 253 s之間)，這樣，大大降低了問題求解計算量。

7 結論

裝備測試任務調度問題是一類較為復雜的組合優化問題，本文結合裝備測試任務調度問題的特點構造了問題求解的系列算法，提出了這類問題目標函數值的一種下界，并將問題求解過程分解為各流水線待測試裝備分配和給定流水線上待測試裝備時測試任務調度。 裝備測試任務調度問題分解成2個子問題求解的方式大大降低了問題求解的難度，計算結果非常接近最優解，甚至就是最優解，這說明本文方法是解決裝備測試任務調度問題的一種有效方法。

)

[1] 畢義明, 楊寶珍, 楊萍,等. 導彈批量測試仿真研究[J]. 火力與指揮控制, 2003, 28(5): 98-100.

BI Yi-ming, YANG Bao-zhen, YANG Ping, et al. Simulation study on missile batch testing problem[J]. Fire Control & Command Control, 2003, 28(5): 98-100.(in Chinese)

[2] 趙鑫, 肖明清, 夏銳. 基于綜合優先級的并行測試調度算法設計及實現[J]. 計算機測量與控制, 2007, 15(4): 423-425.

ZHAO Xin, XIAO Ming-qing, XIA Rui. Parallel test scheduling algorithm based on integrated priority and its implementation[J]. Computer Measurement & Control, 2007, 15(4): 423-425.(in Chinese)

[3] 丁超，唐力偉，鄧士杰. 基于動態優先級的測試任務搶占調度算法[J]. 系統工程與電子技術, 2016, 38(9): 2080-2085.

DING Chao, TANG Li-wei, DENG Shi-jie. Test task preemptive scheduling algorithm based on dynamic priority[J]. System Engineering and Electronics, 2016, 38(9): 2080-2085.(in Chinese)

[4] 周強,司豐煒, 修言彬. Petri網結合Dijkstra算法的并行測試任務調度方法研究[J]. 電子測量與儀器學報, 2015 (6):920-927.

ZHOU Qiang, SI Feng-wei, XIU Yan-bin. Research on the parallel test task scheduling method with Petri nets and Dijkstra algorithm[J]. Journal of Electronic Measurement and Instrumentation, 2015(6):920-927.(in Chinese)

[5] 胡海生, 張鐸, 李明雨. 基于PERT技術的導彈批量測試流程仿真研究[J]. 彈箭與制導學報, 2008, 28(1): 39-42.

HU Hai-sheng, ZHANG Duo, LI Ming-yu. Study of missile batch testing process simulation based on PERT[J]. Journal of Projectiles, Rockets, Missiles and Guidance, 2008, 28(1): 39-42.(in Chinese)

[6] 路輝, 李昕. 一種基于分支定界的串行測試任務調度算法[J]. 航空學報, 2008, 29(1): 131-135.

LU Hui, LI Xin. A kind of scheduling algorithm for serial test tasks based on branch and bound algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2008, 29(1): 131-135.(in Chinese)

[7] 李昕, 沈士團, 路輝. 基于圖染色理論的并行測試任務調度算法[J]. 北京航空航天大學學報, 2007, 33(9): 1068-1071.

LI Xin, SHEN Shi-tuan, LU Hui. Algorithm of tasks scheduling in parallel test based on graph coloring theory[J]. Journal of Beijing University of Aeronautics and Astronautics, 2007, 33(9): 1068-1071.(in Chinese)

[8] 秦勇, 梁旭. 基于混合遺傳算法的并行測試任務調度研究[J]. 國外電子測量技術, 2016, 35(9): 72-75.

QIN Yong, LIANG XU. Research on hybrid genetic algorithm for parallel test task scheduling[J]. Foreign Electronic Measurement Technology, 2016, 35(9): 72-75.(in Chinese)

[9] 陳利安, 肖明清, 高峰,等. 人工蜂群算法在并行測試任務調度中的應用[J]. 計算機測量與控制, 2012, 20(6): 1470-1472.

CHEN Li-an, XIAO Ming-qing, GAO Feng, et al. Artificial bee colony algorithm for parallel test tasks scheduling[J]. Computer Measurement & Control, 2012, 20(6): 1470-1472.(in Chinese)

[10] 付新華, 肖明清, 劉萬俊,等. 一種新的并行測試任務調度算法[J]. 航空學報, 2009, 30(12): 2363-2370.

FU Xin-hua, XIAO Ming-qing, LIU WAN-jun, et al. A novel algorithm for parallel test task scheduling[J]. Acta Aeronautica et Astronautica Sinica, 2009, 30(12): 2363-2370.(in Chinese)

[11] 夏克寒, 牟建華, 暴飛虎,等. 導彈測試流程優化系統設計與實現[J]. 導彈與航天運載技術, 2012(2): 43-46.

XIA Ke-han, MOU Jian-hua, BAO Fei-hu, et al. Design and implementation of missile test process optimizing system [J].Missiles and Space Vehicles,2012(2):43-46.(in Chinese)

[12] Lu H, Wang X, Liu J. Constraint handling technique in test task scheduling problem[J]. Information Technology Journal, 2014, 13(8):1495-1504.

[13] Addition I. Chaotic Multiobjective evolutionary algorithm based on decomposition for test task scheduling problem[J]. Mathematical Problems in Engineering, 2014(4):11-18.

[14] Lu H, Zhu Z, Wang X, et al. A variable neighborhood MOEA/D for multiobjective test task scheduling problem[J]. Mathematical Problems in Engineering, 2014(3):1-14.

[15] Lu H, Niu R, Liu J, et al. A chaotic non-dominated sorting genetic algorithm for the multi-objective automatic test task scheduling problem[J]. Applied Soft Computing, 2013, 13(5):2790-2802.

[16] Lu H, ZHANG M M. Non-integrated algorithm based on EDA and Tabu search for test task scheduling problem[C]∥Proceedings of 2015 IEEE AUTOTESTCON. National Harbor, MD, US:IEEE,2015： 261-268.