欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2019112518387
申请人: 山东师范大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种多目标任务调度方法,其特征在于,包括:

以最大完工时间以及映射阶段和归约阶段所有slots的总能耗最小化为目标,将MapReduce系统任务调度构建为两阶段混合流水车间调度模型;

采用改进的多目标入侵杂草优化算法求解两阶段混合流水车间调度模型,得到调度优化方案;

利用得到的调度优化方案对MapReduce系统中两阶段任务进程进行调度;

所述最大完工时间的目标函数为:

其中,i为工件指数;j为任务指数;Cmax为最大完工时间;r表示归约阶段,n为工件数量;

为在归约阶段中,工件Ji的任务集;

所述总能耗最小化的目标函数为:

其中,k为slots指数;x为slots数量;i为工件指数;j为任务指数;JJk为分配给slot k的一组任务;ek为slot k的单位时间内的能耗;Pi,j,k为由slot k执行的任务 的处理时间;

为在任务集 中的任务j;α∈{m,r}表示映射阶段或归约阶段,m表示映射阶段,r表示归约阶段;

所述MapReduce系统中,作业加工过程包括映射阶段和归约阶段,MapReduce系统中每个作业均在两阶段中进行处理,并且从第一阶段到第二阶段进行加工,每个阶段存在若干个并行solts,在每个阶段,每个作业选择一台机器进行处理;

所述两阶段混合流水车间调度模型的约束包括:每个任务在映射阶段和归约阶段划分为多个子任务,每个子任务在不同的并行位置solts上进行处理;

或,每个任务不能被划分,只能在一台机器上进行处理;

所述采用改进的多目标入侵杂草优化算法求解两阶段混合流水车间调度模型的过程包括:采用二维整数向量的方式对每个任务调度问题进行编码,其中第一维向量表示映射阶段和归约阶段的每个slot,第二维向量表示相应slot上处理的任务作业编号;

初始化每个作业中给定数量的任务,并为每个阶段的随机slot分配任务;

设置所有任务的处理顺序后,为每个阶段中的每个任务设置开始时间和释放时间,得到解码启发式;

采用解码修复法对解码启发式是否可行进行判断并调整;

采用非支配帕累托排序法和p‑最优性算法,在两个优化目标下,对解码启发式进行繁殖,得到调度优化方案;

所述解码修复法包括:

计算每个slot的任务处理数量和内存需求总量;

根据solt的限制能力将其分成两组,第一集合包括分配任务的总数已超过其限制能力的slot,以及第二集合包括分配任务的总数未超过其限制能力的slot;

对第一集合中的每个solt中的任务进行重新分配,直到所有slot满足其限制能力;

所述重新分配过程为:

选择第一集合中任意一个solt中的任意一个任务,将其分配到第二集合中任意一个solt中,并在第一集合中删除该任务;

在保证第二集合中接收该任务的solt的任务处理数量和内存需求满足其限制能力下,更新解码启发式;

所述解码启发式具体为,设置所有任务的处理顺序后,为每个阶段中的每个任务设置开始时间;在映射阶段,考虑每个slot,决定每对连续任务和每个任务的输入数据时间之间的设置时间;为了将每组任务推送到归约阶段,决定释放时间,同时启动归约阶段。

2.如权利要求1所述的一种多目标任务调度方法,其特征在于,采用非支配帕累托排序法和p‑最优性算法,在两个优化目标下,对解码启发式进行繁殖,得到调度优化方案,所述繁殖过程包括:使用非支配帕累托排序法对当前种群中的所有杂草进行排序;

将当前存档中的所有杂草划分为不同的Pareto等级;

对于第一层Pareto等级中的所有杂草使用p‑最优性算法计算p值,选择以最小p值作为最优解;

对于最后一层Pareto等级中的所有杂草计算p值,通过添加p值和级别数计算上一层Pareto等级中解的适应度值,选择最大适应度值的解作为最坏解;

计算每个Pareto等级中的每个解的适应度值和每种杂草的种子数量;

对当前种群中的每个解生成多个后代,并将新生成的解存储到临时集合中。

3.一种多目标任务调度系统,用于执行如权利要求1所述的一种多目标任务调度方法,其特征在于,包括:调度优化模型构建模块,其用于以最大完工时间以及映射阶段和归约阶段所有slots的总能耗最小化为目标,构建两阶段混合流水车间调度模型;

调度优化方案求解模块,其用于采用改进的多目标入侵杂草优化算法求解两阶段混合流水车间调度模型,得到调度优化方案;

调度模块,其用于利用得到的调度优化方案对异构分布式平台的任务进程进行调度;

所述最大完工时间的目标函数为:

其中,i为工件指数;j为任务指数;Cmax为最大完工时间;r表示归约阶段,n为工件数量;

为在归约阶段中,工件Ji的任务集;

所述总能耗最小化的目标函数为:

其中,k为slots指数;x为slots数量;i为工件指数;j为任务指数;JJk为分配给slot k的一组任务;ek为slot k的单位时间内的能耗;Pi,j,k为由slot k执行的任务 的处理时间;

为在任务集 中的任务j;α∈{m,r}表示映射阶段或归约阶段,m表示映射阶段,r表示归约阶段。

4.一种计算机可读存储介质,其中存储有多条指令,所述指令适于由终端设备的处理器加载并执行如权利要求1‑2任一项所述方法的步骤。

5.一种终端设备,包括处理器和计算机可读存储介质,处理器用于实现各指令;计算机可读存储介质用于存储多条指令,所述指令适于由处理器加载并执行如权利要求1‑2任一项所述方法的步骤。