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

摘要:

权利要求书:

1.一种基于实时状态监控的多目标粒子群优化的工作流调度方法,其特征在于:包括:A、工作流预调度;

B、初始化种群个体;

C、实时监控种群进化状态;

D、根据进化状态选择相应的进化策略;

E、更新种群,再次迭代;

F、若达到最大的迭代次数,输出外部精英文档中的工作流调度解集。

2.根据权利要求1所述的一种基于实时状态监控的多目标粒子群优化的工作流调度方法,其特征在于:所述步骤A,其包括:A1,利用BHEFT算法进行工作流预调度,判断工作流调度的时间和执行费用是否满足用户设定的截止时间和预算约束;如果不满足,则提醒用户重新设置截止时间/预算;如果满足条件,则执行后续步骤。

3.根据权利要求1所述的一种基于实时状态监控的多目标粒子群优化的工作流调度方法,其特征在于:所述步骤B,其包括:B1,初始化全局精英文档的容量V、最大迭代次数、初始迭代次数、满足工作流优化调度解离散特性的粒子的速度和位置;

B2,计算每个粒子对应的三个目标函数值,所述目标函数值分别是工作流调度时间、费用和可靠性;

(1)工作流的调度时间计算公式:

其中N为工作流中任务的个数, 指任务ti被分配到 虚拟机 上执行, 代表任务ti的完成时间,而其中 代表任务ti的开始时间, 代表任务

ti在虚拟机上的执行时间;

(2)工作流的调度费用计算公式:

对于虚拟机vmm, 和 分别代表vmm上的第一个和最后一个被执行的任务, 代表虚拟机执行任务所需要的单价;

(3)工作流的调度可靠性:

其中P(vmm)代表虚拟机vmm的

可靠性,计算公式 f(vmm)表示虚拟机vmm执行任务的失败率,ET(vmm)表示虚拟机vmm上所有任务的执行时间,TP(vmm,vmn)代表虚拟机vmm,vmn间的传输可靠性,计算公式 tf(vmm,vmn)表示虚拟机vmm,vmn间的传输失败率,CT(vmm,vmn)表示任务在vmm,vmn间的传输时间;

B3,判断每个粒子对应的调度时间和调度费用,然后与约束条件相比较,选择满足条件的粒子保存到可行调度方案集合,如果粒子不满足约束条件,则重新生成粒子;

B4,把可行调度方案集合中的所有粒子都存入外部精英文档,然后对全局精英文档进行占优排序,保留占优粒子;

B5,保存每个粒子到个体精英文档。

4.根据权利要求1所述的一种基于实时状态监控的多目标粒子群优化的工作流调度方法,其特征在于:所述步骤C,其包括:C1,计算全局精英文档中每一维值映射到二维坐标系的整数标号,得到坐标分量集合;

C2,使用Pareto方差计算二维坐标系中坐标分量的分布均匀的程度;

C3,设定收敛临界阈值和停滞临界阈值,如果Pareto方差大于停滞临界阈值,那么判定此时是停滞阶段;如果Pareto方差小于收敛临界阈值,那么判定此时是收敛阶段;如果Pareto方差位于两个临界阈值之间,那么判定为多样阶段。

5.根据权利要求1所述的一种基于实时状态监控的多目标粒子群优化的工作流调度方法,其特征在于:所述步骤D,其包括:D1,当进化状态处于多样阶段,采取外部精英文档自优化策略对文档中的所有粒子分别按照三个维度的目标值进行排序,从每次排序中按等比间隔方法抽取一定比例的粒子组成样本集合;

D2,对样本集合中的粒子进行高斯扰动,计算扰动后的粒子对应的三个目标函数值;

D3,检验每个粒子对应的调度时间和调度费用是否在约束条件内,将满足条件的粒子保存到可行调度方案集合中,将可行调度方案集合中的粒子并入到外部精英文档中,然后进行占优排序,如果非占优解的占优值相同,那么采取邻居数量密度策略进行升序排序,选取前V个粒子更新外部精英文档;

D4,当进化状态处于停滞阶段,采取逃离策略,把当前粒子分为2个子种群,子群A中的粒子位置随机重置,子群B中的粒子随机选择二维向子群A的各粒子学习;

D5,计算子群A和B中的粒子所对应的的三个目标函数值,判断调度时间和费用是否满足约束,将可行调度方案集合中的粒子并入到外部精英文档中,然后进行占优排序,如果非占优解的占优值相同,那么采取邻居数量密度策略进行升序排序,选取前V个粒子更新外部精英文档。

6.根据权利要求1所述的一种基于实时状态监控的多目标粒子群优化的工作流调度方法,其特征在于:所述步骤E,其包括:E1,计算外部精英文档中每个工作流调度解的邻居数量密度,然后进行升序排序;

E2,选择邻居密度最小的工作流调度解作为全局最优解;

E3,每个粒子与上次迭代产生的个体最优解进行占优排序,如果该粒子占优,那么选取当前粒子为个体最优解;

E4,如果该粒子与上次迭代产生的个体互为非占优关系最优解,那么这两个粒子与全局最优解进行比较,选择欧氏距离小的粒子作为个体最优解;

E5,如果不满足最大迭代次数,则根据离散粒子群迭代公式更新粒子的速度和位置,再次迭代,否则,输出外部精英文档中的工作流调度解集。