题目：单目标测试任务调度研究

近年来测试任务调度由于可以提高测试系统资源利用率、降低测试成本，提升测试系统工作效率，逐渐成为国内外研究的热点。它是一个复杂、难以优化的NP (Non-deterministic Polynomial) 难题，需要考虑资源冲突、系统死锁，以及任务最优排列等问题。因此，研究测试任务调度方法并搭建测试任务调度软件平台具有重要的意义。本文研究了不同情况下的测试任务调度问题，具体包括无约束确定时间、有约束确定时间、无约束不确定时间情况，其中以无时序约束的测试任务调度问题为核心，以适应度地形和智能优化算法为理论基础，以测试完成时间为优化目标，搭建了仿真验证平台。具体研究内容如下：1、 通过统计方法深入研究测试任务调度的适应度地形，证明该问题难，同时给出测试任务调度问题的解分布和解之间的关系，为测试任务调度问题的算法提供指导。2、 针对无约束测试任务调度问题，分别提出了分步解决和集成解决两种方法。分步解决方法将测试任务调度问题分为任务序列和方案选择两个子问题，分别采用遗传算法和方案选择规则进行求解。这种方法降低了问题的求解难度，同时方案选择规则的使用大大缩短了搜索到最优解所需的时间。集成解决则将任务序列和方案选择集成到同一实数编码中，避免了判断测试任务和方案是否匹配的过程，然后结合粒子群算法求解问题。集成解决为测试调度问题提供了更广阔的解决思路，使得连续问题的优化方法可以应用到该测试任务调度问题上。3、 针对有约束，尤其是网状约束下的测试任务调度问题，采用优先权编码包含所有的约束信息，产生满足时序约束的测试任务序列。该优先权编码的方式，和传统优化方式相比，可以产生均符合约束条件的测试任务序列，避免不可行解的生成；和满足的方法，该方法的计算方法复杂度低，运算速度快。实验证明优先权编码的方式可以有效的解决含有约束的测试任务调度问题。4、 针对不确定的测试任务调度问题，提出用模糊表达时间不确定性。其中三角模糊数因为计算冗余度低，成为描述测试任务调度问题模糊时间的首选。实验给出了模糊时间下测试任务调度问题的最优的测试调度时间。5、 在以上理论研究的基础上，结合Visual Studio 2008和DB2开发环境，搭建了测试任务调度仿真平台。该平台包括测试信息维护、数据库存储、适应度地形分析和任务调度规划等模块。该平台以模块化、层次化的方式搭建，具有良好的开放性和可扩展性，为测试任务调度问题的实际应用提供了基础。