混合云环境中调度执行多工作流费用优化算法

Scheduling Multi-Workflow Cost Optimization Algorithm in Hybrid Cloud

云计算服务拥有计算能力强、价格低廉等特点,因此越来越多的企业或机构选择将工作流应用放到云端执行。本文研究的是在企业或者机构的混合云环境下执行用户动态提交的多工作流问题。为了保证工作流执行需求同时优化系统费用支出,需要设计合适的工作流调度算法。提出一种基于移动和回填的异构最早完成时间的启发式调度算法(MIHEFT)用于工作流在私有云中的调度执行,该算法充分考虑工作流的内部结构特征,为工作流中不同子任务制定合理的调度顺序,并充分利用资源的空闲等待时间,提升私有云资源利用效率。在此基础上提出混合云下的动态多工作流调度算法(HCDMW),该算法使用MIHEFT将动态提交到系统的工作流优先在私有云中调度执行,从而充分利用私有云资源,当私有云资源不足时将工作流进行分割,然后调度部分子工作流到公有云执行,使系统的费用支出最小化。实验表明,所提的算法能够有效降低系统整体费用支出。

Cloud computing services have strong computing ability,low price and other characteristics,therefore more and more enterprises or institu⁃tions choose to execute workflows in the clouds.In this paper,we study the multi-workflow,which are dynamically submitted by different users,execution problem in the enterprises or organizations'hybrid cloud.It is necessary to design suitable workflow scheduling algorithm to optimal system cost and meet workflows'some requirements.We propose a move and insert based heterogeneous earliest finish time heuristic scheduling algorithm(Move and Insert-based Heterogeneous Earliest Finish Time,MIHEFT)to schedule and execute work⁃flows in the private cloud.The algorithm takes full account of the internal structure of the workflows,then sets reasonable scheduling order for different sub-tasks,and it makes full use of the idle waiting time of private cloud resources to improve the efficiency of resource utiliza⁃tion.On this basis,a dynamic multi-workflow scheduling algorithm(Hybrid Cloud Dynamic Multiple Workflows Scheduling,HCDMW)is proposed.The algorithm uses MIHEFT to execute workflows in the private cloud preferentially to take full advantage of private cloud re⁃sources.When the private cloud resources are insufficient,the algorithm will divide the workflow into some sub-workflows and then dis⁃patch part of the sub-workflow to public cloud to minimize the system cost.Simulation results show that the HCDMW algorithm can great⁃ly reduce the cost of the system.