基于混沌遗传算法的网格工作流调度应用

摘要

In dynamic grid environment,workflow scheduling problem with multi-QoS (quality of service) constraints is the key to decide the task execution success and efficiency.The existing grid workflow scheduling algorithm was difficult to meet the different needs of practical application,and the algorithm was lack of optimization,it was difficult to provide a variety of strategy,so this paper introduced an improved chaos-genetic algorithm based on the deadline and budget QoS constraints.In order to avoid algorithm appear convergence stagnation,it used the chaos mechanism to combine with genetic algorithms and dynamically adjusted the probability of mutation.Then it put forward the concept of linear combination of time and budget,so that the objective function was transformed into a fitness function.Finally the results of applying chaos-genetic scheduling algorithm show greater performances on both balanced and unbalanced worlflows.%动态网格环境中,多QoS(服务质量)约束下的工作流调度问题是决定其任务执行成功与否及效率高低的关键.现有的网格工作流调度算法难以满足实际应用中的不同需求,同时算法欠优化,难以提供多种策略,由此提出了一种基于期限与预算两个QoS约束的改进型混沌遗传算法.首先,为避免算法出现收敛停滞将混沌机制引入遗传算法并对变异概率进行自适应处理.其次,提出时间和预算的线性结合概念,将目标函数转换为适应值函数.最终基于工作流调度中的平衡结构和非平衡结构测试了算法的有效性.