摘要
本文采用整数线性规划，实现了并行测试的最优设计．该方法使得并行测试图（ＰＴＧ）的最大完全子图（ＭＣＳ）的顶点数最少，即ＰＴＧ的点着色数（ＶＣＮ）最少，因而使得总的测试时间最少．文中提出了一个Ｏ（ｎ２）的最优测试调度算法．实验证明该模型是有效的，正确的．
An integer linear programming (ILP) model is presented to design for optimal parallel testing,which minimizes the vertex number of the Maximum Complete Subgraph (MCS)in the parallel testing graph (PTG) as well as the vertex chromatic number(VCN)of the PTG.The whole test time of a partioned circuit is thus minimal.An optimal test scheduling algorithm of a partitioned circuit is also presented in quadratic time. An existent ILP program is used to prove the correctness of this model.
出处
《计算机学报》
EI
CSCD
北大核心
1994年第1期37-45,共9页
Chinese Journal of Computers
关键词
电路
并行测试
最优设计
线性规划
Parallel testing
test scheduling
test point
integer linear programming
optimal design.
