摘要
工作流是云计算环境下任务的主要表现形式,工作流任务调度问题是一个典型的NPC问题,进化算法在解决这类问题方面具有明显优势。然而,传统的进化算法容易陷入局部最优,造成早熟结果。提出一种考虑截止时间约束条件下的自适应遗传进化方法,采用适应度修正均值来自适应计算交叉概率、变异概率,引入惩罚函数自适应修正适应度,以避免陷入局部最优。在WorkflowSim仿真环境上,选用具有代表性的Montage科学工作流,与5种算法的对比实验结果表明在4种不同截止时间约束下,所提方法的约束满足程度最高,且能够在贴近用户截止时间约束的执行时间下花费更小的成本。
Workflow is the main manifestation of tasks in cloud computing environment.Workflow task scheduling problem is a typical NPC problem.Evolutionary algorithm has obvious advantages in solving such problems.However,the traditional evolutionary algorithm has the problem of being easy to fall into the local optimum and causing premature convergence.In this study,a deadline-constrained adaptive genetic evolutionary approach which calculates the probability of mutation and selection based on the modified mean fitness adaptively is proposed,and a penalty function to update the fitness adaptively to avoid falling into the local optimum is introduced.On the basis of WorkflowSim simulation environment,the representative Montage workflow is selected.Compared with five algorithms,experimental results show that under the constraints of four different deadlines,the proposed method had the best constraint satisfaction rate and smaller costs at execution times closed to user’s deadline constraints.
作者
党云龙
封筠
殷梦莹
Dang Yunlong;Feng Jun;Yin Mengying(School of Information Science and Technology,Shijiazhuang Tiedao University,Shijiazhuang 050043,China)
出处
《石家庄铁道大学学报（自然科学版）》
2019年第3期94-100,共7页
Journal of Shijiazhuang Tiedao University(Natural Science Edition)
关键词
工作流
任务调度
自适应进化
截止时间约束
workflow
tasks scheduling
adaptive evolution
deadline constraint
