基于均衡适应度的云工作流调度算法
|
摘要
针对工作流任务调度优化问题,提出一种云工作流任务调度遗传算法。为了寻找工作流执行时间与执行代价的同步最优解,建立了遗传调度模型。在个体编码方面,采用了一种二维排列编码方法,可以更好地展现工作流任务间的执行次序;综合考虑任务执行代价与最早完成时间两个因素,设计了一种均衡适应度函数;为了丰富种群个体多样性,引入三种遗传交叉操作和两种遗传变异操作,以产生新的个体,增加了最优解的求解概率。通过数值仿真实验,在多个性能指标上对算法进行分析。结果表明,该调度算法能更好地平衡执行代价与调度效率,性能优于同类算法。
For the optimization of workflow task scheduling, we presented the cloud workflow task scheduling genetic algorithm. To search the synchronous optimal solution of workflow execution time and cost, we built the genetic scheduling model. In the individual coding, two-dimension array coding method was adopted, which could better show the execution order between workflow tasks. Considering both the task execution cost and earliest finish time, we designed the trade-off fitness function. For enriching the diversity of the population individuals, we introduced three kinds of genetic crossover operation and two kinds of genetic mutation operation, which generated new individuals and increased the probability of obtaining the optimal solution. Through the numerical simulation experiments, we analyzed the algorithm in multiple performance indexes. The results show that the scheduling algorithm can achieve a better balance between the execution cost and the scheduling efficiency, and its performance is superior to that of similar algorithms.
For the optimization of workflow task scheduling, we presented the cloud workflow task scheduling genetic algorithm. To search the synchronous optimal solution of workflow execution time and cost, we built the genetic scheduling model. In the individual coding, two-dimension array coding method was adopted, which could better show the execution order between workflow tasks. Considering both the task execution cost and earliest finish time, we designed the trade-off fitness function. For enriching the diversity of the population individuals, we introduced three kinds of genetic crossover operation and two kinds of genetic mutation operation, which generated new individuals and increased the probability of obtaining the optimal solution. Through the numerical simulation experiments, we analyzed the algorithm in multiple performance indexes. The results show that the scheduling algorithm can achieve a better balance between the execution cost and the scheduling efficiency, and its performance is superior to that of similar algorithms.
引文
[1] Laili Y,Tao F,Zhang L,et al.A study of optimal allocation of computing resources in cloud manufacturing systems[J].International Journal of Advanced Manufacturing Technology,2012,63(5):671-690.
[2] Liu L,Zhang M,Lin Y,et al.A survey on workflow management and scheduling in cloud computing[C]//14th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2014:837-846.
[3] Yassa S,Chelouah R,Kadima H,et al.A Genetic Algorithm Approach to QoS based Workflow Scheduling in Cloud computing Environment[C]//International Conference on Distributed Systems and Decision.IEEE,2017:22-34.
[4] Sahni J,Vidyarthi D.A Cost-Effective Deadline-Constrained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment[J].IEEE Transactions on Cloud Computing,2015,2(1):1-12.
[5] Calheiros R N,Buyya R.Meeting deadlines of scientific workflows in public clouds with tasks replication[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(7):1787-1796.
[6] Chen W N,Zhang J.A set-based discrete PSO for cloud workflow scheduling with user-defined QoS constraints[C]//2012 IEEE International Conference on Systems,Man,and Cybernetics (SMC).IEEE,2012.
[7] Mirzayi S,Rafe V.A hybrid heuristic workflow scheduling algorithm for cloud computing environments[J].Journal of Experimental & Theoretical Artificial Intelligence,2015,27(6):721-735.
[8] Lin X Y,Wu Q S.On scientific workflow scheduling in clouds under budget constraint[C]//42nd International Conference on Parallel Processing,IEEE,2013:90-99.
[9] Wu C Q,Lin X Y,Yu D T,et al.End-to-End Delay Minimization for Scientific Workflows in Clouds under Budget Constraint[J].IEEE Transactions on Cloud Computing,2015,3(2):169-181.
[10] Zeng L F,Veeravalli B,Zomaya A Y.An integrated task computation and data management scheduling strategy for workflow applications in cloud environments[J].Journal of Network and Computer Applications,2015,50:39-48.
[11] Zeng L,Veeravalli B,Li X.SABA:A security-aware and budget-aware workflow scheduling strategy in clouds[J].Journal of Parallel & Distributed Computing,2015,75:141-151.
[12] Lee Y C,Zomaya A Y.Stretch Out and Compact:Workflow Scheduling with Resource Abundance[C]//IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2013:219-226.
[13] Bessai K,Youcef S,Oulamara A,et al.Bi-criteria Workflow Tasks Allocation and Scheduling in Cloud Computing Environments[C]//IEEE,International Conference on Cloud Computing.IEEE,2012:638-645.
[14] Su S,Li J,Huang Q,et al.Cost-efficient task scheduling for executing large programs in the cloud[J].Parallel Computing,2013,39(4/5):177-188.
[2] Liu L,Zhang M,Lin Y,et al.A survey on workflow management and scheduling in cloud computing[C]//14th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2014:837-846.
[3] Yassa S,Chelouah R,Kadima H,et al.A Genetic Algorithm Approach to QoS based Workflow Scheduling in Cloud computing Environment[C]//International Conference on Distributed Systems and Decision.IEEE,2017:22-34.
[4] Sahni J,Vidyarthi D.A Cost-Effective Deadline-Constrained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment[J].IEEE Transactions on Cloud Computing,2015,2(1):1-12.
[5] Calheiros R N,Buyya R.Meeting deadlines of scientific workflows in public clouds with tasks replication[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(7):1787-1796.
[6] Chen W N,Zhang J.A set-based discrete PSO for cloud workflow scheduling with user-defined QoS constraints[C]//2012 IEEE International Conference on Systems,Man,and Cybernetics (SMC).IEEE,2012.
[7] Mirzayi S,Rafe V.A hybrid heuristic workflow scheduling algorithm for cloud computing environments[J].Journal of Experimental & Theoretical Artificial Intelligence,2015,27(6):721-735.
[8] Lin X Y,Wu Q S.On scientific workflow scheduling in clouds under budget constraint[C]//42nd International Conference on Parallel Processing,IEEE,2013:90-99.
[9] Wu C Q,Lin X Y,Yu D T,et al.End-to-End Delay Minimization for Scientific Workflows in Clouds under Budget Constraint[J].IEEE Transactions on Cloud Computing,2015,3(2):169-181.
[10] Zeng L F,Veeravalli B,Zomaya A Y.An integrated task computation and data management scheduling strategy for workflow applications in cloud environments[J].Journal of Network and Computer Applications,2015,50:39-48.
[11] Zeng L,Veeravalli B,Li X.SABA:A security-aware and budget-aware workflow scheduling strategy in clouds[J].Journal of Parallel & Distributed Computing,2015,75:141-151.
[12] Lee Y C,Zomaya A Y.Stretch Out and Compact:Workflow Scheduling with Resource Abundance[C]//IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2013:219-226.
[13] Bessai K,Youcef S,Oulamara A,et al.Bi-criteria Workflow Tasks Allocation and Scheduling in Cloud Computing Environments[C]//IEEE,International Conference on Cloud Computing.IEEE,2012:638-645.
[14] Su S,Li J,Huang Q,et al.Cost-efficient task scheduling for executing large programs in the cloud[J].Parallel Computing,2013,39(4/5):177-188.