预算约束下关联式云任务调度算法

关联式云任务是科学工作流的典型应用模式,其调度不同于传统的独立任务形式。为了解决这种云工作流任务的调度优化问题,提出了一种满足预算约束的工作流调度算法。算法将任务与实例间的最优映射方案求解划分为4个阶段进行:工作流结构划分、预算分割、任务选择和实例选择。工作流结构划分旨在以工作流结构特征为基础将各个任务划分为不同的层次,预算分割旨在将用户定义的工作流执行预算在每个工作流层次间进行重新分配,任务选择旨在以升秩/降秩之和赋予任务优先级,形成就绪任务列表,实例选择旨在选择满足可用子预算的最佳实例执行任务。通过仿真实验,测试了算法在不同类型工作流结构和不同约束严格程度下的性能。结果表明,算法的执行效率与调度成功率要优于同类型算法,具有较好的可行性。