本发明属于云测试平台任务调度的遗传算法
技术领域：
，具体涉及一种基于改进遗传算法的云测试平台任务调度方法。
背景技术：
：云计算技术作为一种资源管理和供应的模式，把计算、存储和网络等硬件资源虚拟化为一个多用户共享的资源池，再通过网络向用户按需提供可拓展的虚拟资源，突破物理空间的限制。将云计算技术应用到测试中的云测试平台，可以利用大规模虚拟化环境开展测试，即利用云测试平台更加有效的组织和利用各类测试基础设施资源(计算资源、网络资源、存储资源等)，以服务方式提供一种测试资源透明、环境按需、平台开放、高效执行的测试手段，提供一种随时随地使用测试服务的新型应用模式，为测试设计、环境开设、执行管控、状态监视、结果分析等测试活动提供有力支撑。云测试平台面向的用户多，用户提交的任务需求的硬件资源各不相同，任务间的依赖关系复杂，合理的任务调度是保证用户及时得到云测试平台相应，按时完成任务的重要保证。测试任务调度的首要目标是，在满足任务依赖关系限制的前提下寻找一个合理的调度策略，按序将测试任务映射到处理机上，使任务尽可能地并行执行以使系统完成所有任务的时间最短。目前基于遗传算法的云测试平台任务调度的研究中存在限制处理机数量、不考虑任务间依赖、忽略处理机可以并行执行多个任务的情况等问题。。技术实现要素：有鉴于此，本公开提出了一种基于改进遗传算法的云测试平台任务调度方法，能够有效解决处理机数量、任务间依赖和并行执行任务等问题。根据本发明的一方面，提出了一种基于改进遗传算法的云测试平台任务调度方法，所述方法包括：建立所述云测试平台任务调度模型；基于所述云测试平台任务调度模型的测试任务调度方式进行编码，形成测试任务状态表；根据所述测试任务状态表设计所述改进遗传算法的适应度函数；基于所述适应度函数初始化所述改进遗传算法的种群，利用轮盘赌算法选择所述种群中的染色体；对所述改进遗传算法的染色体进行交叉、变异后，当满足所述改进遗传算法的结束条件时，得到所述云测试平台任务调度最短时间。在一种可能的实现方式中，所述云测试平台任务调度模型为五元组g，g＝(t,e,sp,st,r,c)，其中，t为云测试平台任务调度dag图的节点集合，e为云测试平台任务调度dag图的有向边的矩阵，sp为云测试平台的处理机所能提供的资源的矩阵，st为云测试平台测试任务所需的资源的矩阵，r为测试任务在不同处理机上的执行时间的矩阵，c为测试任务件转换时间的矩阵。在一种可能的实现方式中，所述基于所述云测试平台任务调度模型的测试任务调度方式进行编码，形成测试任务状态表，包括：将所述云测试平台任务调度模型的测试任务调度方式的测试任务和所述处理机之间的映射关系形成所述测试任务编码表；根据所述测试任务进入待执行状态的所有前置条件和测试任务执行状态形成测试任务状态表；根据所述测试任务的执行完成时间定义所述测试任务的权重，根据所述测试任务的权重执行所述测试任务；根据所述测试任务状态表计算执行所有所述测试任务的执行完成时间。在一种可能的实现方式中，根据所述测试任务状态表设计所述改进遗传算法的适应度函数，包括：根据所述测试任务状态表和测试任务编码表计算所述云测试平台在执行测试任务期间的处理机的负载；根据所述处理机的负载计算所有处理机负载的平均值，得到所述云测试平台在执行测试任务期间的处理机的负载均衡度；基于所述所述云测试平台完成所有测试任务的最短执行时间和所述云测试平台在执行测试任务期间的处理机的负载均衡度设定所述改进遗传算法的适应度函数。5、根据权利要求4所述的云测试平台任务调度方法，其特征在于，所述测试任务状态表包括：测试任务编号、处理机编号、测试任务的前置任务、测试任务的后继任务、计算核心数、内存大小、硬盘大小、测试任务的前置任务的完成状态、测试任务需求资源的满足状态、测试任务待执行状态、测试任务执行中状态和测试任务已完成状态。在一种可能的实现方式中，所述根据所述测试任务状态表计算执行所述测试任务的执行完成时间，包括：根据测试任务编码表找到测试任务ti和其对应的处理机pj，根据所述云测试平台任务调度模型的dag图查找所述测试任务的前驱任务和后继任务；通过所述测试任务在不同处理机上的执行时间矩阵r计算出分配在所述处理机pj的所以测试任务的权重；当所述测试任务ti的前驱任务已完成，判断所述处理机pj是否满足所述测试任务ti的资源需求；当所述处理机pj满足所述测试任务ti的资源需求，判断所述测试任务ti的测试任务状态表中的待执行状态、执行中状态和已完成状态均为0时，将所述测试任务ti的待执行状态置为1；判断所述测试任务ti在所述处理机pj上的所有待执行测试任务中的权重为最大时，将所述测试任务ti的测试任务状态表中的执行中状态置为1，待执行状态置为0，并在所述处理机pj所提供的资源矩阵sp减去该任务所需的资源，记录所述测试任务开始的时间；将所述测试任务ti执行完成后，将所述测试任务ti的测试任务状态表中的已完成状态置为1，在所述处理机pj所提供的资源矩阵sp中添加该任务所需的资源，记录所述测试任务结束的时间；返回所述测试任务ti的开始时间和结束时间，即得到所述测试任务ti的执行完成时间。在一种可能的实现方式中，所述处理机pj的负载为，其中，c、m、d分别为处理机pj提供的计算核心数、内存大小和硬盘大小，cx为tx时间段内处理机pj被占用的计算核心数，my为ty时间段内处理机pj被占用的内存大小，dz为tz时间段内处理机pj被占用的硬盘大小；所述处理机pj的负载均衡度为，其中，为所有处理机负载的平均值；所述适应度函数为其中，a和b为常数，i和n为正整数。本公开的基于改进遗传算法的云测试平台任务调度方法，通过建立所述云测试平台任务调度模型；基于所述云测试平台任务调度模型的测试任务调度方式进行编码，形成测试任务状态表；根据所述测试任务状态表设计所述改进遗传算法的适应度函数；基于所述适应度函数初始化所述改进遗传算法的种群，利用轮盘赌算法选择所述种群中的染色体；对所述改进遗传算法的染色体进行交叉、变异后，当满足所述改进遗传算法的结束条件时，得到所述云测试平台任务调度最短时间。能够有效解决处理机数量、任务间依赖和并行执行任务等问题。根据下面参考附图对示例性实施例的详细说明，本公开的其它特征及方面将变得清楚。附图说明包含在说明书中并且构成说明书的一部分的附图与说明书一起示出了本公开的示例性实施例、特征和方面，并且用于解释本公开的原理。图1示出根据本公开一实施例的基于改进遗传算法的云测试平台任务调度方法流程图；图2示出根据本公开一实施例的基于改进遗传算法的云测试平台任务调度模型的dag图的示意图；图3示出了根据本公开一实施例的步骤s2的进一步限定流程图；图4示出了根据本公开一实施例的步骤s24的进一步限定流程图；图5示出了根据本公开一实施例的步骤s3的进一步限定流程图。具体实施方式以下将参考附图详细说明本公开的各种示例性实施例、特征和方面。附图中相同的附图标记表示功能相同或相似的元件。尽管在附图中示出了实施例的各种方面，但是除非特别指出，不必按比例绘制附图。在这里专用的词“示例性”意为“用作例子、实施例或说明性”。这里作为“示例性”所说明的任何实施例不必解释为优于或好于其它实施例。另外，为了更好的说明本公开，在下文的具体实施方式中给出了众多的具体细节。本领域技术人员应当理解，没有某些具体细节，本公开同样可以实施。在一些实例中，对于本领域技术人员熟知的方法、手段、元件和电路未作详细描述，以便于凸显本公开的主旨。本公开的任务调度方法，依据云测试平台中任务的特点设计测试任务调度算法的映射编码方法，结合基于测试任务编码表的调度算法的特点，提出根据测试任务状态表计算测试任务完成时间的方法，并根据云测试中的重要评价指标，改进了遗传算法的适应度函数、负载均衡度的计算公式，有效解决了处理机数量、任务间依赖和并行执行任务等问题。图1示出根据本公开一实施例的基于改进遗传算法的云测试平台任务调度方法流程图。如图1所示，该方法可以包括：步骤s1：建立所述云测试平台任务调度模型。其中，云测试平台任务调度模型可以为针对现有的启发式和元启发式测试任务调度算法限制处理机数量、不考虑任务间依赖、忽略处理机可以并行执行多个任务的情况等问题，结合基于测试任务编码表的调度算法的特点，对现有的基于遗传算法的云测试平台任务调度算法做出改进。图2示出根据本公开一实施例的基于改进遗传算法的云测试平台任务调度模型的dag图的示意图。例如，假定云测试平台中有n台处理机{p1,p2,…pn}，用户提交的云测试任务有m个{t1,t2,...tm}。一般情况下，与处理机数量n相比，测试任务数量m的值是远远大于n的。可以定义一个五元组g，g＝(t,e,sp,st,r,c)来表示云测试平台任务调度模型。其中，t为云测试平台任务调度dag图的节点集合，e为云测试平台任务调度dag图的有向边的矩阵。考虑到云测试任务间有先后的调度约束关系，通过有向无环图dag来表示测试任务间的约束关系，图中的节点代表测试任务，节点间的有向边代表测试任务间的依赖关系。如图2所示，t1是t2和t3的前置任务，即在t1执行完成前，t2和t3的不能开始。t5和t6是t7的前置任务，也就是在t5和t6全部执行完成前t7不能开始。根据云测试平台任务调度dag图的有向边的矩阵e的定义，当eij＝1时，ti是tj的前置任务，在ti执行完成之前，tj不能开始执行，此时将ti称为tj的前置任务，tj称为ti的后继任务，当eij＝0时，ti和tj没有直接的先后关系。sp为云测试平台的处理机所能提供的资源的矩阵，st为云测试平台测试任务所需的资源的矩阵。在处理机同时满足多个任务所需资源时可以同时运行多个虚拟机来执行任务，定义sp＝(cp,mp,dp),st＝(ct,mt,dt),其中,向量cp,mp,dp分别表示处理机能够提供的计算核心数、内存大小(单位为gb)和硬盘大小(单位为gb)，向量ct,mt,dt分别表示测试任务所需要的计算核心数量、内存大小和硬盘大小。当测试任务tj被分配到指定处理机pi上时，若处理机能够满足任务执行所需的资源时(ctj<cpi、mtj<mpi和dtj<dpi都满足)，处理机构建一个计算核心数为ctj、内存大小mtj、硬盘大小dtj的虚拟机执行测试任务tj，并从能提供的资源数量中减去对应部分。当测试任务tj执行完成后回收资源，将对应部分重新加回可提供的资源数量中。r为测试任务在不同处理机上的执行时间的矩阵，c为测试任务件转换时间的矩阵。由于每个处理机的cpu、内存、硬盘的型号和性能各不相同，所以不同测试任务分配在不同处理机上的执行时间都是不同的。矩阵r中的元素rji为任务tj分配在处理机pi上的执行时间。矩阵c中的元素cji表示在同一处理机上从任务ti结束到下一个任务tj开始的测试准备时间和数据通信时间。基于上述建立的云测试平台任务调度模型，结合基于测试任务编码表的调度算法的特点，对现有的基于遗传算法的云测试平台任务调度算法做出改进。步骤s2：基于所述云测试平台任务调度模型的测试任务调度方式进行编码，形成测试任务状态表。图3示出了根据本公开一实施例的步骤s2的进一步限定流程图。该步骤可以包括两层操作，第一层操作为编码方法，第二层操作为形成测试任务状态表。在一示例中，如图2所示，步骤s2可以包括：步骤s21：将所述云测试平台任务调度模型的测试任务调度方式的测试任务和所述处理机之间的映射关系形成所述测试任务编码表；步骤s22：根据所述测试任务进入待执行状态的所有前置条件和测试任务执行状态形成测试任务状态表；步骤s23：根据所述测试任务的执行完成时间定义所述测试任务的权重，根据所述测试任务的权重执行所述测试任务；步骤s24：根据所述测试任务状态表计算执行所述测试任务的执行完成时间。其中，编码是将云测试平台任务调度方式的解映射为字符串或数字符串的数学表达式的过程，在云测试任务调度中的解是一种对测试任务执行顺序和执行位置的安排。由于一台处理机可以根据能够提供的资源数量和测试任务需求的资源数量生成数量不定的虚拟机，直接将测试任务调度到对应的虚拟机上会导致编码生成的染色体长度不一，给后续的交叉、变异等操作带来较大的困难，染色体可以为云测试任务调度中的一种可能的测试任务和处理机匹配方式。每一个染色体(调度方案，)是一个m*1的向量，向量中下标为i(1≤i≤m)对应的取值为x代表了任务ti被分配给处理机px。如表1所示，该染色体下标1的对应取值为8，代表将任务t1分配给处理机p8执行。表1染色体编码表向量下标1234567对应取值85128355当同一处理机上分配有不同的测试任务时，测试任务的执行顺序的调度策略可以根据测试任务的权重进行调整和执行。例如，将测试任务t1和t4都分配了处理机p8，首先，需要确定测试任务t1和t4的前置任务是否都已完成。假设任务t1和t4的前置任务都已完成，需判断处理机p8能否提供满足执行测试任务t1和t4所需要的资源。假设资源满足，需要根据测试任务t1和t4的权重决定测试任务t1和t4的执行顺序。当染色体(测试任务调度方案)，也就是测试任务和处理机匹配方式已定时，由步骤s231到步骤s237可知每个测试任务的执行完成时间也就确定了(在矩阵r中查找)。测试任务ti的权重为：其中，ti为测试任务ti的执行时间，tj为ti的后置任务tj的执行时间。当同一处理机上有两个或两个以上的任务处于待执行状态时，由任务的权重决定执行的先后顺序。将测试任务进入待执行状态的所有前置条件和任务所处的执行状态进行归纳得到该测试任务的测试任务状态表，如表2所示。表2测试任务状态表在一示例中，如图表2所示，测试任务状态表可以包括：测试任务编号、处理机编号、测试任务的前置任务、测试任务的后继任务、计算核心数、内存大小、硬盘大小、测试任务的前置任务的完成状态、测试任务需求资源的满足状态、测试任务待执行状态、测试任务执行中状态和测试任务已完成状态共12项内容。其中，测试任务编号可以为按照测试任务提交的顺序对测试任务进行编号，如表2中的测试任务为t4。处理机编号可以为根据染色体(测试任务调度方案)中任务和处理机的匹配方式，查找到染色体向量下标为4时所对应处理机的取值为8，也就是任务t4被分配给了处理机p8。测试任务的前置任务可以为通过描述测试任务间约束关系的dag图查找到任务t4的前置任务为t2和t3。测试任务的后继任务可以通过描述测试任务间约束关系的dag查找到任务t4的后继任务为t5和t6。计算核心数可以为测试任务t4所需求的计算核心数量。内存大小可以为测试任务t4需求的内存大小(单位为gb)。硬盘大小可以为测试任务t4需求的硬盘大小(单位为gb)。测试任务的前置任务完成状态可以为当所有前置任务都处于已完成状态时，该项置1，否则置0。测试任务需求资源满足状态可以为当处理机可以满足测试任务需求的所有资源时，该项置1，否则置0。测试任务待执行状态可以为当执行中状态和已完成状态都为0，且前置任务完成状态和需求资源满足状态都为1时，将待执行状态置1。测试任务执行中状态可以为在完成测试任务待执行状态判断后，根据权重选出被执行的测试任务，并将其测试任务执行中状态置1，待执行状态置0。测试任务已完成状态可以为测试任务执行完成后将已完成状态置1，执行中状态置0。图4示出了根据本公开一实施例的步骤s24的进一步限定流程图。在一示例中，如图4所示，步骤s24可以包括：步骤s241：根据测试任务编码表找到测试任务ti和其对应的处理机pj，根据所述云测试平台任务调度模型的dag图查找所述测试任务的前驱任务和后继任务；步骤s242：通过所述测试任务在不同处理机上的执行时间矩阵r计算出分配在所述处理机pj的所以测试任务的权重；步骤s243：当所述测试任务ti的前驱任务已完成，判断所述处理机pj是否满足所述测试任务ti的资源需求；步骤s244：当所述处理机pj满足所述测试任务ti的资源需求，判断所述测试任务ti的测试任务状态表中的待执行状态、执行中状态和已完成状态均为0时，将所述测试任务ti的待执行状态置为1；步骤s245：判断所述测试任务ti在所述处理机pj上的所有待执行测试任务中的权重为最大时，将所述测试任务ti的测试任务状态表中的执行中状态置为1，待执行状态置为0，并在所述处理机pj所提供的资源矩阵sp减去该任务所需的资源，记录所述测试任务开始的时间；步骤s246：将所述测试任务ti执行完成后，将所述测试任务ti的测试任务状态表中的已完成状态置为1，在所述处理机pj所提供的资源矩阵sp中添加该任务所需的资源，记录所述测试任务结束的时间；步骤s247：返回所述测试任务ti的开始时间和结束时间，即得到所述测试任务ti的执行完成时间。通过上述步骤，即根据测试任务状态表能够计算每个测试任务执行完成时间。步骤s3：根据所述测试任务状态表设计所述改进遗传算法的适应度函数。图5示出了根据本公开一实施例的步骤s3的进一步限定流程图。在一示例，如图5所示，步骤s3可以包括：步骤s31：根据所述测试任务状态表和所述测试任务编码表计算所述云测试平台在执行测试任务期间的处理机的负载；即根据测试任务和处理机之间的对应关系计算处理机的负载。步骤s32：根据所述处理机的负载计算所有处理机负载的平均值，得到所述云测试平台在执行测试任务期间的处理机的负载均衡度；步骤s33：基于所述所述云测试平台完成所有测试任务的最短执行时间和所述云测试平台在执行测试任务期间的处理机的负载均衡度设定所述改进遗传算法的适应度函数。其中，遗传算法通过适应度算法淘汰不良染色体，经过重复不断的迭代得到最优解。结合缩短云平台测试中的测试任务执行时间和负载均衡两方面的考虑，测试任务的调度结果应该满足：云测试平台能够在尽量短的时间内完成所有的测试任务和云测试平台在执行任务期间要保证负载均衡。在测试任务执行时间方面，计算出所有测试任务完成的时间。在负载均衡方面，假定对于处理机pi执行测试任务完成总时间为t，将t划分成n1个时间段，在每个时间段内处理机pi被任务占用的计算核心数总是保持不变。同样地，将t划分成n2、n3个时间段，在每个时间段内处理机pi被任务占用的内存大小、硬盘大小总是保持不变。定义处理机pj的负载为其中，c、m、d分别为处理机pj提供的计算核心数、内存大小和硬盘大小，cx为tx时间段内处理机pj被占用的计算核心数，my为ty时间段内处理机pj被占用的内存大小，dz为tz时间段内处理机pj被占用的硬盘大小。利用处理机pj的负载均衡度为其中，为所有处理机负载的平均值。基于测试任务完成时间和负载均衡度两方面的要求，定义适应度函数为其中，a和b为常数，i和n为正整数。常数a和b的大小由测试任务完成时间和负载均衡两方面的度量指标在适应度函数中所占权重确定。如处理机负载公式可知，测试任务执行总时间越短，负载越均衡时适应度函数的值越大，代表该染色体越优秀，有更大的存活概率。通过适应度函数可以筛选出优秀的染色体种群，既能够达到执行测试任务的最短时间又能够避免仅仅依据测试时间为判定结果的局部优化的情况。步骤s4：基于所述适应度函数初始化所述改进遗传算法的种群，利用轮盘赌算法选择所述种群中的染色体。例如，可以设定初始种群中的30％使用min-min算法生成，其余70％的染色体使用随机数生成，按照任务编号将第1到第n个测试任务分配给随机的处理机。其中，min-min算法是一种易于实现的经典启发式算法，运行时间短，运行效率高，主要是根据测试任务运行时间对测试任务进行排序，先执行所需时间短的小任务，然后分配大任务。假设种群p(k)中有n个染色体，染色体k的适应度函数用f(k)表示，那么染色体k被选择的概率p(k)为：其中，式中的表示种群中n个染色体适应度的总和。轮盘赌选择算法每次计算出的选择概率都在[0,1]之间，且染色体被选择的概率完全由其自身的适应度决定。适应度越高的染色体越有可能被选中，自身优秀的基因更有可能传给下一代，适应程度较低的染色体也有概率被选中，这样增加了种群中染色体的多样性。步骤s5：对所述改进遗传算法的染色体进行交叉、变异后，当满足所述改进遗传算法的结束条件时，得到所述云测试平台任务调度最短时间。其中，交叉算法通常根据设定的交叉概率选取两条染色体，并交换这两条染色体中对应部分的基因序列。举例来说，设两个选定的染色体为f1、f2，交叉算法操作如下：首先，随机选择总测试任务数量x(0.2l≤x≤0.8l)，l是染色体长度；其次，在染色体f1、f2中分别选择一个以总测试任务数量x为中心的染色体片段，其长度为染色体总长度l的分别记作k1、k2；最后，交换染色体片段k1和k2的位置，生成的新的染色体片段分别记作s1、s2。从而实现新的染色体的交叉操作。染色体的变异操作可以有效保证种群基因多样性，防止因遗传算法收敛过早，陷入局部最优解。则染色体的变异操作具体如下：随机选取u、v两个值(u<v)，根据变异概率选择染色体s，取出染色体s中编号从u开始到v结束的染色体片段，将其反向排序后重新注入染色体s的相同位置中，形成染色体s′，将形成的染色体s′注入种群中，实现染色体的变异操作。在染色体完成相应的选择、交叉、变异操作后，遗传算法完成了一次迭代过程，根据遗传算法的迭代结束条件得到云测试平台任务调度方法的最优解，其中，遗传算法的迭代结束条件可以为次数超过预定的数量，遗传算法最近的10次迭代中种群没有发生任何变化，种群中的所有染色体收敛到同一个染色体上，只需要达到该三个条件中的一个时，遗传算法停止并输出当前种群中的最优解。本公开的基于改进遗传算法的云测试平台任务调度方法，通过建立所述云测试平台任务调度模型；基于所述云测试平台任务调度模型的测试任务调度方式进行编码，形成测试任务状态表；根据所述测试任务状态表设计所述改进遗传算法的适应度函数；基于所述适应度函数初始化所述改进遗传算法的种群，利用轮盘赌算法选择所述种群中的染色体；对所述改进遗传算法的染色体进行交叉、变异后，当满足所述改进遗传算法的结束条件时，得到所述云测试平台任务调度最短时间。能够有效解决处理机数量、任务间依赖和并行执行任务等问题。以上已经描述了本公开的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本
技术领域：
的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术改进，或者使本
技术领域：
的其它普通技术人员能理解本文披露的各实施例。当前第1页1 2 3
技术特征：1.一种基于改进遗传算法的云测试平台任务调度方法，其特征在于，所述方法包括：
建立所述云测试平台任务调度模型；
基于所述云测试平台任务调度模型的测试任务调度方式进行编码，形成测试任务状态表；
根据所述测试任务状态表设计所述改进遗传算法的适应度函数；
基于所述适应度函数初始化所述改进遗传算法的种群，利用轮盘赌算法选择所述种群中的染色体；
对所述改进遗传算法的染色体进行交叉、变异后，当满足所述改进遗传算法的结束条件时，得到所述云测试平台任务调度最短时间。
2.根据权利要求1所述的云测试平台任务调度方法，其特征在于，所述云测试平台任务调度模型为五元组g，g＝(t,e,sp,st,r,c)，其中，t为云测试平台任务调度dag图的节点集合，e为云测试平台任务调度dag图的有向边的矩阵，sp为云测试平台的处理机所能提供的资源的矩阵，st为云测试平台测试任务所需的资源的矩阵，r为测试任务在不同处理机上的执行时间的矩阵，c为测试任务件转换时间的矩阵。
3.根据权利要求1所述的云测试平台任务调度方法，其特征在于，所述基于所述云测试平台任务调度模型的测试任务调度方式进行编码，形成测试任务状态表，包括：
将所述云测试平台任务调度模型的测试任务调度方式的测试任务和所述处理机之间的映射关系形成所述测试任务编码表；
根据所述测试任务进入待执行状态的所有前置条件和测试任务执行状态形成测试任务状态表；
根据所述测试任务的执行完成时间定义所述测试任务的权重，根据所述测试任务的权重执行所述测试任务；
根据所述测试任务状态表计算执行所有所述测试任务的执行完成时间。
4.根据权利要求2所述的云测试平台任务调度方法，其特征在于，根据所述测试任务状态表设计所述改进遗传算法的适应度函数，包括：
根据所述测试任务状态表和所述测试任务编码表计算所述云测试平台在执行测试任务期间的处理机的负载；
根据所述处理机的负载计算所有处理机负载的平均值，得到所述云测试平台在执行测试任务期间的处理机的负载均衡度；
基于所述所述云测试平台完成所有测试任务的最短执行时间和所述云测试平台在执行测试任务期间的处理机的负载均衡度设定所述改进遗传算法的适应度函数。
5.根据权利要求4所述的云测试平台任务调度方法，其特征在于，所述测试任务状态表包括：测试任务编号、处理机编号、测试任务的前置任务、测试任务的后继任务、计算核心数、内存大小、硬盘大小、测试任务的前置任务的完成状态、测试任务需求资源的满足状态、测试任务待执行状态、测试任务执行中状态和测试任务已完成状态。
6.根据权利要求5所述的云测试平台任务调度方法，其特征在于，所述根据所述测试任务状态表计算执行所述测试任务的执行完成时间，包括：
根据测试任务编码表找到测试任务ti和其对应的处理机pj，根据所述云测试平台任务调度模型的dag图查找所述测试任务的前驱任务和后继任务；
通过所述测试任务在不同处理机上的执行时间矩阵r计算出分配在所述处理机pj的所以测试任务的权重；
当所述测试任务ti的前驱任务已完成，判断所述处理机pj是否满足所述测试任务ti的资源需求；
当所述处理机pj满足所述测试任务ti的资源需求，判断所述测试任务ti的测试任务状态表中的待执行状态、执行中状态和已完成状态均为0时，将所述测试任务ti的待执行状态置为1；
判断所述测试任务ti在所述处理机pj上的所有待执行测试任务中的权重为最大时，将所述测试任务ti的测试任务状态表中的执行中状态置为1，待执行状态置为0，并在所述处理机pj所提供的资源矩阵sp减去该任务所需的资源，记录所述测试任务开始的时间；
将所述测试任务ti执行完成后，将所述测试任务ti的测试任务状态表中的已完成状态置为1，在所述处理机pj所提供的资源矩阵sp中添加该任务所需的资源，记录所述测试任务结束的时间；
返回所述测试任务ti的开始时间和结束时间，即得到所述测试任务ti的执行完成时间。
7.根据权利要求5所述的云测试平台任务调度方法，其特征在于，
所述处理机pj的负载为，其中，c、m、d分别为处理机pj提供的计算核心数、内存大小和硬盘大小，cx为tx时间段内处理机pj被占用的计算核心数，my为ty时间段内处理机pj被占用的内存大小，dz为tz时间段内处理机pj被占用的硬盘大小；
所述处理机pj的负载均衡度为，其中，为所有处理机负载的平均值；
所述适应度函数为其中，a和b为常数，i和n为正整数。
技术总结本公开的基于改进遗传算法的云测试平台任务调度方法，通过建立所述云测试平台任务调度模型；基于所述云测试平台任务调度模型的测试任务调度方式进行编码，形成测试任务状态表；根据所述测试任务状态表设计所述改进遗传算法的适应度函数；基于所述适应度函数初始化所述改进遗传算法的种群，利用轮盘赌算法选择所述种群中的染色体；对所述改进遗传算法的染色体进行交叉、变异后，当满足所述改进遗传算法的结束条件时，得到所述云测试平台任务调度最短时间。能够有效解决处理机数量、任务间依赖和并行执行任务等问题。
技术研发人员：王志;朱信杰;金东生;傅华章;高倩
受保护的技术使用者：中国电子科技集团公司第十五研究所
技术研发日：2020.11.30
技术公布日：2021.03.12
