IaaS云满足预算约束的工作流应用调度算法

WORKFLOW APPLICATIONS SCHEDULING ALGORITHM MEETING BUDGET CONSTRAINT IN IAAS CLOUD

为了解决IaaS(Infrastructure as a Service)云的工作流调度优化问题,提出基于预算约束的工作流调度算法。以最小化工作流调度时长为目标,算法分调度任务选择和虚拟机实例选择两阶段进行。第一阶段将工作流任务依据依赖关系作层次划分,同层次组成包任务,以Min-Max方法对层次任务估算时间作标准化处理,定义最迟完成时间与最早完成时间差值最大者为调度任务;第二阶段在期望预算下以最早完成时间最小为标准选择资源,实现任务与资源间的映射。利用算例阐述了算法实现过程,并通过仿真实验测试了算法性能。结果证实,改进算法执行效率与调度成功率优于同类算法。

In order to solve the problem of workflow scheduling optimization in IaaS cloud,we propose a workflow scheduling algorithm based on budget constraints.To minimize the workflow scheduling time,our algorithm was divided into two stages:the scheduling task selection and the virtual machine instance selection.The first phase divided the workflow tasks into different levels according to the dependencies.And tasks in the same level constructed bags of tasks.The evaluation computing time of tasks in levels were normalized by Min-Max method and we regarded the finish time difference value as scheduling tasks.The second phase selected the resource with the minimizing of the earliest completion time under the expected budget,which could realize the mapping between tasks and resources.An example was applied to elaborate the new designed algorithm.Through the simulation,we tested the algorithm performance in different types of workflow structures and different budget constraint.Experiments verify that the improved algorithm has a higher execution efficiency and scheduling success rate than the compared algorithms.