中文摘要：

随着网格和云计算工作流技术的发展,近来关于多DAG（Directed Acyclic Graph）共享资源调度的研究取得了一些进展,然而,关于具有最晚完成期限约束的多DAG共享一组有限异构资源的调度及其费用最低化等问题还有待进一步研究和解决.针对这些问题,文中首先提出了衡量DAG期限紧急水平的“相对严格程度”的新方法,并在此基础上提出了基于相对严格程度的调度算法MDRS （Scheduling for Multi-DAGs with Deadline based on Relative Stritness）.该算法不仅能够合理处理多个DAG之间调度的紧急水平关系,也能对由于DAG期限过于严格而可能产生的“过饱和”情况进行探测和处理.一旦遇到“过饱和”情况,则采用“堆栈”与“调度回溯”相结合的机制尽可能少地丢弃其中的DAG,从而达到DAG吞吐量最大化调度目标.在MDRS算法的基础上,为了满足各DAG期限内完成约束条件,并尽可能公平地降低多个DAG执行的费用,又提出了基于单位相对严格程度变化量的费用降低率最大化方法的费用优化算法CDVRS （Cost Decrease based on Variance of the Relative Strictness）.实验表明：这些方法及算法能够达到较好的性能.

英文摘要：

Along with developing of the technology of Grid workflows and Cloud workflows, recent researches into the problem of scheduling multiple DAG （Directed Acyclic Graph） sharing resources have been making progress and have solved some problems. However, the problems of scheduling and cost optimization of multiple DAGs with deadline sharing finite heterogeneous resources need to be solved. To solve the problems, a new method of ＂relative strictness＂ used in measuring urgency level of a DAG＇s deadline constraint is proposed first, and then, the MDRS algorithm is presented. The algorithm can not only reasonably determine the relationship of multiple DAGs＇ urgency levels, but also can deal with possible ＂oversaturation＂ which may be caused by rigid deadline constraints of each DAG. Once the ＂oversaturation＂ happens, the algorithm can drop as few DAGs as possible and try to schedule the rest of DAGs to maximize the throughput of DAG through the mechanism of ＂Backtracking＂ combining with ＂Stack＂. Furthermore, in order to fairly minimize the total cost of these DAG while meeting a user-defined deadline, we propose another algorithm called CDVRS （Cost tive Strictness）. Last experiments demonstrate that our related performances. Decrease based on Variance of the Rela algorithms and methods can improve theAbstract Along with developing of the technology of Grid workflows and Cloud workflows, recent researches into the problem of scheduling multiple DAG （Directed Acyclic Graph） sharing resources have been making progress and have solved some problems. However, the problems of scheduling and cost optimization of multiple DAGs with deadline sharing finite heterogeneous resources need to be solved. To solve the problems, a new method of ＂relative strictness＂ used in measuring urgency level of a DAG＇s deadline constraint is proposed first, and then, the MDRS algorithm is presented. The algorithm can not only reasonably determine the relationship of multiple DAGs＇ urgency levels, but also