在软件回归测试中，由于客观因素（例如时间、成本等）的制约，庞大的测试用例集不可能全部被执行。测试用例预优化是一种通过调整测试用例的执行顺序来优化回归测试过程的技术。传统的测试用例预优化技术主要针对单一测试准则进行优化排序研究，以及研究不同测试准则和平均错误检测率之间的相关性。然而，在实际的回归测试环境中，测试人员可能会同时考虑多个测试准则和多种客观因素，从而综合地作出测试用例预优化方案，传统的测试用例预优化技术很显然不能满足这样的需求。另外，进化算法是一类以达尔文进化论为依据的智能算法，广泛应用于不同领域里的实际优化问题中，但由于它是一个以种群为单位进行大规模遗传迭代的过程，所以执行效率必然会随着种群大小和测试用例集规模的增大而急剧下降，这已成为进化算法发展的一大软肋。针对上述两个问题，本论文首先提出了一种基于NSGA-II算法的多目标测试用例预优化方法，该方法可以同时将多个测试准则和客观因素作为优化目标；在此基础上，本论文一方面针对方法中最耗时的适应度评估部分，给出了一种基于CPU+GPU异构模式的并行适应度评估策略；另一方面，针对遗传操作中最复杂且最耗时的交叉操作部分，本论文探讨了三种基于CPU+GPU异构模式的并行交叉策略，即序列编码并行交叉策略、顺序编码并行交叉策略和基于scan操作的并行交叉策略。实验结果表明本论文提出的基于NSGA-II算法的多目标测试用例预优化方法在所有的被测程序上都可以获得测试用例的最优排序方案集合，并且在规模较大的space程序上得到了较好的Pareto前沿。表明该方法可以有效地解决符合实际回归测试需求的测试用例预优化问题。此外，几种并行策略的实验结果显示适应度评估部分可以获得50倍以上的加速，而三种并行交叉策略也可以获得不同程度的加速效果，其中基于scan操作的并行交叉策略加速效果最为明显。因此，这几种并行策略确实可以有效地提高基于NSGA-II算法的多目标测试用例预优化方法的执行效率，可以应用于一些对时间要求苛刻的软件回归测试过程中。