基于图顶点染色的并行测试自动调度算法

摘要

目前电子制造业的产品自动测试系统大多采用顺序多工位的测试方式，仪器设备利用率低，并且操作人员需求数量多，故生产测试成本高昂。本文针对此问题，引入了并行测试的改造方案，构建了多DUT(DeviceUnderTest)交错测试系统，重点对系统中的自动调度算法问题进行了深入研究。
　　针对要解决的工程实际问题，本文首先构建了TCG(TestingConflictGraph)和PTG(ParallelTestingGraph)图的概念，将实际要解决的工程问题转化为图论中的顶点染色问题。然后在此理论基础上通过构建特例的方法，提出了可以在多项式时间内获得最优解的静态测试调度算法和多DUT测试任务随机分配的动态测试调度算法。最后基于LabVIEW平台，完成了算法的程序开发和性能测试仿真。仿真结果表明：当PTG为Petersen图时，与传统顺序测试方式相比，测试系统在单个DUT测试的情况下效率提升达72.52％，在8个DUT同时测试的情况下效率提升不低于67.76%。

目录

封面

中文摘要

英文摘要

目录

第1章 序言

1.1 本文研究的目的和意义

1.2 自动测试的发展和现状

1.3 论文的主要工作和内容

1.4 本章小结

第2章 并行测试技术概述

2.1 并行测试的基本概念

2.2 并行测试的分类

2.3 并行测试的优势

2.4 支持并行测试的软件及算法

2.5 本章小结

第3章 自动调度算法的基本概念和理论背景

3.1 图的基本概念[19,20]

3.2 图论模型

3.3 图顶点染色相关理论[19,20]

3.4 并行测试自动调度算法

3.5 本章小结

第4章 并行测试调度的软件设计

4.1 静态测试调度的软件设计

4.2 动态测试调度的软件设计

4.3 本章小结

第5章 自动调度算法性能测试和仿真

5.1 静态测试调度算法的性能测试

5.2 动态测试调度算法的性能仿真

5.3 本章小结

第6章 结论与展望

英文缩写

参考文献

致谢