具有随机执行时间的批任务工作流云资源弹性租赁与调度方法

Dynamic resource provisioning for batch-task based workflows is one of the most important problem in the areas of scientific research, electronic commerce, smart city, etc. The actual situation is different with the schedule because of the deviation between the predicted task execution time and the actual time, which decreased the performance of scheduling algorithms. The interval-based cloud pricing models make the scheduling with stochastic execution times more complicated. Therefore, the goal of this project is to design batch-task based workflow scheduling algorithms with well adaptability to the interval-based pricing models and the stochastic execution times. A historical data based method will be proposed to model the deviation of predicted task execution times and a Monte Carlo method will be developed to generate the distribution of the total execution time of multiple tasks. For the execution time and resource renting cost minimization problems of batch-task based workflows, dynamic scheduling algorithms based on stochastic execution time modeling will be investigated separately. For different constraints, a configuration updating cost based deadline division method and an execution time decreasing rate based budget division method will be proposed. For batch-task scheduling problems in the dynamic scheduling algorithm with different constraints, resource renting and scheduling algorithms will be developed based on the mathematical expectation of the cost of added pricing intervals, the probability of violating the task deadline, the mathematical expectation of total task finish times in the waiting queues. Implement the goal of increasing the data processing ability and decreasing the resource renting cost of cloud users.

批任务工作流应用广泛存在于科学计算、商业数据分析等领域，云计算资源动态租赁与工作流调度是其核心问题。任务预测执行时间与实际执行时间的偏差（随机性）使得实际执行结果与调度产生较大偏差，降低了调度算法鲁棒性；云资源按区间计费方式和执行时间随机性使得调度更加复杂，提出对任务执行时间随机性具有良好鲁棒性的批任务工作流资源租赁与调度方法具有一定挑战性。针对任务执行时间随机性，本课题拟提出预测偏差概率分布建模方法和生成多任务总执行时间概率分布的蒙特卡罗方法；针对批任务工作流执行时间和资源租赁成本最小化问题，分别提出基于随机任务执行时间建模的动态调度方法；对于不同约束，分别提出基于加配成本和执行时间降低效率的截止期划分和预算分配方法；针对批任务调度问题，分别提出基于新增计费区间成本期望、满足截止期概率值、等待队列总执行时间期望的资源租赁与任务调度方法；提升云用户的数据处理能力，降低数据处理成本。

批任务工作流应用广泛存在于科学计算、商业数据分析等领域，云计算资源动态租赁与批任务工作流调度是其核心问题。任务预测执行时间与实际执行时间的偏差（随机性）使得实际执行结果与原调度产生较大偏差，降低了调度算法鲁棒性。研究内容包括：（1）研发了支持任务执行时间不确定性建模的云计算仿真平台；针对任务执行概率分布的不同类型，提出了基于均值和标准差之和的任务执行时间预估方法；（2）基于竞价型虚拟机的价格波动特点，提出了基于移动平均与自回归、隐马尔可夫和马尔可夫多区制转移等模型的虚拟机价格预测方法；（3）针对截止期约束，提出了基于批结构感知、预计浪费成本变化率的截止期分配方法；基于任务执行时间不确定性建模、虚拟机价格预测和截止期分配方法，提出了最小化资源租赁成本的批任务工作流调度方法；（4）针对预算约束，提出了基于串行度增加效率和配置更新有效性等指标的预算分配方法；基于任务执行时间不确定性建模、虚拟机价格预测和预算分配方法，提出了最小化任务执行时间的批任务工作流调度方法；（5）针对分布式计算平台Spark中的多个实际批任务工作流，提出了多个调度与优化方法，降低任务的内存消耗与执行时间，是对已有批任务工作流调度理论的初步实践。本研究研发的批任务工作流模拟平台是云计算调度算法性能验证的有效途径之一；提出的虚拟机价格预测与多个批任务工作流调度算法降低了云计算应用的虚拟机资源租赁成本与任务执行时间，具有广泛的应用前景。