武丽芬，严学勇

(1.晋中学院 信息技术与工程系，山西 晋中 030600；2.中国联通晋中分公司 信息支撑中心，山西 晋中 030600)

0 引 言

云计算环境中，资源可根据应用需求动态地分配至用户任务，而用户对资源的支付方式是即付即用的，这极大地区别于传统的网格等分布式计算环境。这种特有的使用特征使得云计算提供了对科学工作流调度的最好支持。每一种大规模的工作流应用均可建模为有向无循环图DAG结构，其中包含大量相互依赖和相互独立的任务，有些可同步执行，有些则需按照先后次序执行。为了满足用户应用的QoS需求，云工作流调度需要寻找有效的调度方案，实现任务与多资源间的映射与执行。

目前，云资源的使用特征导致已有调度算法拥有以下不足：①资源使用时间固定。本文中资源只要在空闲状态即可释放，资源获取是任意的，这样可节省资源使用代价；②资源定价未使用账单模型。本文应用Amazon EC2的资源账单定价模型，在已付账单中，先前任务的空闲时间片可被下一任务继续利用，以节省代价；③涉及多QoS参数时，已有搜索或元启发式算法复杂度过高。本文将设计时间复杂度更低的工作流调度算法，同步满足截止时间和预算约束，寻找调度可行解。

1 相关研究

对于工作流调度多目标优化问题，本文将调度算法分为两种类型：单工作流调度和多工作流调度。单工作流调度仅涉及一次从入口任务至出口任务的执行过程，而多工作流调度涉及入口任务与出口任务间的多次执行过程。……