云计算环境下多尺度计费服务的批任务工作流调度

Batch-task workflow scheduling is a new problem in Cloud computing, which is widespread in many fields such as the commercial data analysis and the scientific computation. Based on the multi-scale payment mode for services, we will construct the estimating model for the float intervals of batch-tasks. Constrains and interactions will be analyzed for the data transmission time, the cost of software installation and available time slots. Priorities of services are calculated in terms of the weighted factors. We will analyze the time competition and the resource sharing among the batch-tasks of the deadline constrained workflows. A mathematical model will be established for batch-task workflows under the multi-scale payment mode to minimize the total renting cost. The workflow deadline is divided into batch-task deadlines. We will develop algorithms for batch-task workflows with multi-scale payments. A trade-off will be studied between the cost of available intervals and the flexible capabilities of services. A multi-objective mathematical model will be constructed for batch-task workflow scheduling to optimize the total renting cost, the total finish time and the balanced utilization of resources. As well, algorithms for such problem will be introduced.

云计算环境下批任务工作流调度是广泛存在于各种商业数据分析、科学计算等领域的新问题。依据服务资源的多尺度计费模式，提出活动结点为批任务的执行浮动区间估计模型。分析数据传输时间、软件安装成本等服务本地化因素与服务资源可用时间槽间的相互影响和制约关系；建立多因素加权的资源优先级计算规则；采用方差分析确定各因素权重，提出多因素约束的服务资源选择算法。分析截止期约束下工作流各批任务间的时间竞争和资源共享关系，以最小化资源租赁成本为目标，建立多尺度计费的批任务工作流调度模型；提出工作流批任务截止期划分方法；设计多尺度计费的批任务工作流调度方法。分析多尺度计费区间成本和服务资源弹性能力的权衡关系；以批任务工作流的资源总租赁成本、总完成时间、资源均衡利用等为优化目标，建立多尺度计费的批任务工作流多目标调度模型，提出相应的调度优化方法。

云计算环境下的批任务工作流调度广泛应用于科学计算、商业分析、交通规划、生产制造等领域。针对不同资源计费模式，为不同特点的批任务工作流应用匹配合适的资源以最小化资源租赁总成本是云计算环境下工作流调度的重要问题。在资源管理方面，考虑资源的多尺度计费模式，分别建立预留、按需、竞价模式下的任务浮动区间估计模型；基于动态ARIMA和两种马尔可夫体制转换自回归模型提出竞价实例的价格预测机制；基于系统资源状态，构建系统任务的排队论模型，提出均衡的任务资源匹配机制。在批任务工作流调度方面，采用按需方式租赁资源。针对不可拆分批处理工作流，提出基于非共享服务的截止期划分方法，提出基于执行效率和时间片利用率的的时间槽选择方法；针对可拆分批处理工作流,提出基于单元的截止期划分方式和可拆分式任务调度方法。在复杂工作流调度方面，采用多种计费模式结合的方式租赁资源。针对长期的周期性工作流应用，采用预留模式租赁虚拟机资源，提出基于优先级树搜索的启发式方法；针对带有柔性任务的工作流应用，采用预留和按需相结合的模式，提出基于多序列的启发式算法；针对长期的批处理工作流应用，采用预留和按需相结合的模式，提出自适应概率种群迭代算法；针对短期的带有可抢占和不可抢占任务的工作流应用，采用按需和竞价模式相结合的模式，提出基于空闲时间块的解的构造方法。在其它调度方面，针对异地环境下工作流调度的能耗优化问题，提出自适应局部搜索算法；针对带截止期和时间窗约束的云服务工作流调度问题，提出迭代启发式搜索算法；针对多目标组合优化问题，提出A*算法。通过仿真实验分析，校正了各算法的参数，并验证了所提出方法的有效性。相关的研究工作提高了工作流调度的适用性，拓展了云工作流调度理论，并有效地解决了云计算中迫切关注的实际问题。