云计算环境下基于随机键遗传算法的工作流调度优化方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN111078360A(43)申请公布日2020.04.28(21)申请号201911259919.1(22)申请日2019.12.10(71)申请人浙江工商大学地址310012浙江省杭州市西湖区教工路149号(72)发明人谢毅桂奉献(74)专利代理机构杭州浙科专利事务所(普通合伙)33213代理人吴秉中(51)Int.Cl.G06F9/455(2006.01)G06N3/12(2006.01)权利要求书6页说明书25页附图1页(54)发明名称云计算环境下基于随机键遗传算法的工作流调度优化方法(57)摘要本发明公开了一种云计算环境下基于随机键遗传算法的工作流调度优化方法，包括以下步骤：获取调度所需信息；计算任务的排序值和层次值；初始化当代种群；进行进化：采用FBI&D和LDI方法改进当代种群并计算适应度值，采用精英保留、个体迁徙、参数化均匀交叉形成新的当代种群，直到满足进化终止条件；输出调度优化方案。本发明基于随机键实数编码可以实现全域搜索，在初始种群中播入基于HEFT_lbt的个体可以缩短收敛时间，采用个体迁徙方法替代变异操作能在更大程度上破坏个体、保持种群多样性，有利于避免进入局部最优和早熟，提高求解效率和质量。CN111078360ACN111078360A权利要求书1/6页1.一种云计算环境下基于随机键遗传算法的工作流调度优化方法，其特征在于：包括以下步骤：步骤1：形式化调度问题，获取调度优化所需的信息；获取任务集T＝{t1,t2,...,tI}，其中I是任务的数量，ti表示任务i，即编号为i的任务；获取任务间的时序关系：任务i的父任务集PRi，任务i的子任务集SCi，其中i＝1,2…,I；获取任务相关参数：任务i的长度ti.length，即任务i被虚拟机处理时需要耗费的指令数量，处理任务i时需要的输入文件列表ti.IFL，任务i被处理后产生的输出文件列表+ti.OFL，及文件列表中文件file的大小file.size，其中i＝1,2…,I；任务i是任务i的父任务的充要条件为：存在一个文件file，file是任务i的输出文件同时又是任务i+的输入文件，即：获取云计算环境下的虚拟机集VM＝{vm1,vm2,…,vmJ}，其中J是虚拟机的数量，vmj表示虚拟机j，即编号为j的虚拟机；获取虚拟机相关参数：虚拟机j的计算能力vmj.ps，虚拟机j的带宽vmj.bw，其中j＝1,2…,J；获取任务与虚拟机之间的支持关系：虚拟机j可以处理的任务集Tj，其中j＝1,2…,J；可以处理任务i的虚拟机集VMi，其中i＝1,2…,I；步骤2：计算任务的排序值rank；先计算ti执行时的平均处理时间需要从共享数据库获得输入文件的平均传输时间需要从其它虚拟机获得输入文件的平均传输时间ti执行时的平均处理时间计算如下：ti执行时需要从共享数据库获得输入文件的平均传输时间为：ti执行时需要从其它虚拟机获得输入文件的平均传输时间为：其中为和ti间的文件平均传输时间，其计算如下：2CN111078360A权利要求书2/6页然后，计算任务i的自下而上排序值其计算过程如下：对于没有子任务的结束任务i：其它任务的自下而上排序值采用如下递归公式进行计算：接着，计算任务i的自上而下排序值其计算过程如下：对于没有父任务的开始任务i：其它任务的自上而下排序值采用如下递归公式进行计算：最后，计算任务i的排序值ranki：在所有ranki中值最大的对应的任务称为关键任务；步骤3：计算任务的层次值；对于没有父任务的开始任务i，其层次值为：leveli＝1(10)其它任务的层次值采用如下递归公式进行计算：步骤4：初始化当代种群；基于HEFT_lbt生成1个个体，然后，基于个体随机生成操作生成剩余的N-1个体，形成初始种群；其中N为种群规模；所述个体采用I位实数编码，其方法如下：ch＝{g1,…,gI}，其中I是任务的数量，基因gi是一个正实数，整数部分表示给任务i分配的虚拟机编号，即把任务i分配给虚拟机小数部分表示任务i在调度时的优先级，数值越小优先级越高；所述基于HEFT_lbt生成1个个体包括如下步骤：步骤A1：令所有虚拟机可得时间段列表vatlj＝{[0,M]}，j＝1,…,J，M为一个接近无穷大的数；令所有任务的就绪时间rti＝0，i＝1,…,I；生成I个[0,1)之间的随机数，不妨设这3CN111078360A权利要求书3/6页些随机数从小到大为：α1,α2,…,αI；令计数变量k＝1、任务集UT＝T；步骤A2：在UT中找出层次值最小的任务，从中取出rank最大的一个任务，不妨设为ti；步骤A3：令ti的可得虚拟机集AVMi＝VMi，计算把ti分别分配给AVMi中的每个虚拟机后ti的完成