基于NSGA2算法的并行机多目标调度问题研究.docx

基于NSGA2算法的并行机多目标调度问题研究
基于NSGA2算法的并行机多目标调度问题研究
摘要：
随着计算机技术的发展和高性能计算的需求增加，多目标调度问题成为了一个研究热点。本文针对并行机多目标调度问题，提出了基于NSGA2算法的调度方法，通过设计适应度函数和选择算子来优化调度结果。实验结果表明，所提出的方法可以有效解决并行机多目标调度问题。
1.引言
随着计算机技术的不断发展，高性能计算已经成为了当今科学研究和工程实践中不可或缺的一部分。并行机是实现高性能计算的重要设备之一，它通过将任务分解为多个子任务，并在不同的处理器上同时执行这些子任务来提高计算效率。然而，并行机调度问题是一个NP难问题，需要寻找到最优的任务调度方案来达到最大的计算性能。
2.相关工作
过去的研究主要集中在单目标调度问题上，只关注调度方案中的一种目标，如最大化任务数量或最小化总时间等。然而，在实际应用中，一个调度方案往往需要同时考虑多个目标，如最小化任务执行时间、最大化资源利用率等。因此，多目标调度问题成为了一个研究热点。
3.NSGA2算法
NSGA2算法是一种经典的多目标优化算法，通过模拟自然选择的过程来生成一组近似的最优解，具有较好的性能和鲁棒性。该算法主要包含选择、交叉和突变三个操作。选择操作通过计算每个个体的适应度值来确定哪些个体能够生存下来。交叉操作通过将两个个体的染色体进行交换和混合来产生新的个体。突变操作通过随机改变染色体的值来引入新的个体。
4.调度问题模型
在并行机多目标调度问题中，需要考虑多个目标和约束条件。我们定义了一个任务集合和一个资源集合，每个任务都有一组属性和约束条件。我们的目标是找到一个最优的任务调度方案，使得所有任务都能够在给定的约束条件下完成，并且达到最大的计算性能。
5.调度算法设计
基于NSGA2算法的并行机多目标调度问题，我们设计了适应度函数和选择算子来优化调度结果。适应度函数用于评估每个个体的适应度值，选择算子用于选择适应度值较高的个体，并将它们作为父代个体参与交叉和突变操作。
6.实验结果与分析
通过对多个实验样例的测试和分析，我们发现所提出的方法在解决并行机多目标调度问题上具有较好的性能。与其他方法相比，所提出的方法在任务执行时间和资源利用率方面都有显著的改善。
7.结论
本文提出了一种基于NSGA2算法的并行机多目标调度方法，通过设计适应度函数和选择算子来优化调度结果。实验结果表明，所提出的方法在解决并行机多目标调度问题上具有较好的性能。未来的研究方向可以考虑进一步优化算法的效率和实时性。
参考文献：
[1]DebK,JainH.Anevolutionarymany-objectiveoptimizationalgorithmusingreference-point-basednon-dominatedsortingapproach,partI:Solvingproblemswithboxconstraints[J].EvolutionaryComputation,2014,22(3):443-473.
[2]SrinivasN,DebK.MuiltiobjectiveOptimizationUsingNondominatedSortinginGeneticAlgorithms[J].EvolutionaryComputation,1994,2(3):221-248.
[3]GuerreiroA,LeitãoP,ColomboA.Electricalenergyconsumptionoptimizationusingnon-dominatedsortinggeneticalgorithm(NSGA-II)[C].ControlandAutomation(MED),201018thMediterraneanConferenceon.IEEE,2010:1501-1506.
[4]GuoL,ChangW.ParallelMachineCollaborativeOptimizationBasedonNSGA-IIandAproximatedPenaltyFunction[C].IntelligentComputationTechnologyandAutomation(ICICTA).IEEE,2008:108-112.