混合云计算环境下多工作流的混合调度及费用优化

Many information processing and computing can be converted into a DAG workflow process in the fields of production, economics and scientific computing, which need to be scheduled and executed on a certain parallel and distributed system to realize high effect. Recent researches into workflows on cloud environment have been making progress and have solved some problems. However, there are many problems to be resolved. The project aim at to solve some new problems in scheduling for multiple DAG workflows sharing on hybrid cloud system, which include the throughput maximization of workflows scheduled on private cloud, the request for public cloud resources on the peak times of workflow and fair economic cost optimization of multiple workflows scheduled on the public cloud resources. The solution of these problems will promote the development of research and application about multiple workflows on cloud environment and will have both theoretical and applicable value, which will make better use of cloud resource, reduce economic cost of multiple workflows and avoid waste of resources in extension of the public cloud to meet the request of multiple workflows execution.

生产、经济及科学计算领域中很多工作的信息处理或计算过程都能转化为一个DAG（Directed Acyclic Graph有向无环图）工作流执行过程，并需要在一些分布式计算系统上进行调度和执行。目前关于云计算环境下工作流的调度及应用研究已受到研究者们的关注，并有了初步进展，但还有很多新问题有待解决。本项目首次提出并旨在解决混合云计算环境下多工作流混合调度的若干问题。这些问题主要包括，在私有云上有期限约束的多DAG调度吞吐量最大化问题、工作流峰值时段需扩展的公有云资源类型和数量估算问题以及公有云资源上多DAG调度的费用优化及费用优化的公平性问题。这些问题的提出和解决将对混合云计算环境下多用（租）户工作流应用系统运行效率的提高和费用成本的降低等方面具有重要的理论意义和现实应用价值。

生产、经济及科学计算领域中很多工作的信息处理或计算过程都能转化为一个DAG（Directed Acyclic Graph有向无环图）工作流执行过程，并需要在一些分布式计算系统上进行调度和执行。本项目课题组研究和解决了混合云计算环境下有执行期限约束的多工作流混合调度中所面临的若干关键问题，主要的研究内容及创新成果如下：. 首先，研究了具有期限约束的多DAG共享资源调度的吞吐量最大化问题，提出了基于相对严格程度的调度算法MDRS和基于宽松度优先LLF方法与MDRS算法相结合的LLF-Sim-MDRS调度算法。另外，进一步针对MDRS算法时间复杂度较高的问题，又提出了基于“弹性时隙”扩张机制的ESB (Expansion Slot Backfill)的改进算法。相关的实验表明，上述研究成果中的MDRS和 ESB算法的性能指标均优于现有的EDF、Round-Robin和Fairness等方法。. 其次，针对云资源上多DAG调度的费用优化及费用优化的公平性等问题，提出了一种基于MDRS算法和总费用降低量探测算法PDTC，进而研究了费用优化中出现“马太效应”的较大不公平性的可能性，并提出了衡量费用优化公平性的有关方法和基于单位相对严格程度变化量的费用降低率最大化的费用优化算法CDVRS。实验表明，与MDRS和PDTC等算法相比，CDVRS算法不仅能有效降低多DAG的总费用，也能够改善多个DAG费用优化的公平性。. 最后，针对有期限约束的多工作流峰值时段调度运行所需公有云资源数量的估算问题，并在分析了多DAG数量、结构属性特点与资源需求强度之间的关系基础上提出了基于资源需求强度预测变异的进化算法EFRD。最后的实验表明，与EMTS等算法相比，EFRD能够更快、有效地搜索到最优解。. 本课题上述这些研究成果，在提高混合云计算环境下的多租户或多用户工作流应用系统的执行效率，降低用户工作流的经济费用，避免在私有云资源不足时对公有云资源的扩展中的资源浪费等方面将具有较大的理论意义和现实应用价值。