截止时间约束的工作流调度自适应进化方法

党云龙, 封筠, 殷梦莹

doi:10.13319/j.cnki.sjztddxxbzrb.20180018

石家庄铁道大学学报（自然科学版） ›› 2019, Vol. 32 ›› Issue (03) : 94 -100. DOI: 10.13319/j.cnki.sjztddxxbzrb.20180018

截止时间约束的工作流调度自适应进化方法

党云龙, 封筠, 殷梦莹

作者信息 +

Author information +

文章历史 +

PDF

摘要

工作流是云计算环境下任务的主要表现形式,工作流任务调度问题是一个典型的NPC问题,进化算法在解决这类问题方面具有明显优势。然而,传统的进化算法容易陷入局部最优,造成早熟结果。提出一种考虑截止时间约束条件下的自适应遗传进化方法,采用适应度修正均值来自适应计算交叉概率、变异概率,引入惩罚函数自适应修正适应度,以避免陷入局部最优。在WorkflowSim仿真环境上,选用具有代表性的Montage科学工作流,与5种算法的对比实验结果表明在4种不同截止时间约束下,所提方法的约束满足程度最高,且能够在贴近用户截止时间约束的执行时间下花费更小的成本。