李文娟，张启飞，平玲娣，潘雪增

（1. 浙江大学 计算机学院，浙江 杭州 310018；2. 杭州师范大学 钱江学院，浙江 杭州 310012）

1 引言

云计算（cloud computing）是在网格计算、并行计算、P2P和虚拟化等技术基础上发展起来的一种新型的共享信息基础设施的模式，也是未来提供网络服务的重要形式[1～3]。云计算的宗旨是为企业和其他终端用户提供廉价按需服务，因而特别强调QoS。而任务调度模型的优劣直接影响云服务质量，毋庸置疑是云计算研究的重要组成部分[4～6]。云计算研究目前仍处于初级阶段，有关云调度的算法还非常稀少，但传统的其他并行分布式系统中的调度模型[7,8]有很多。其中以最小化作业完成时间为目标的元任务调度算法有OLB、贪心（greedy）算法、最大最小（max-min）、最小最小（min-Min）、Sufferage算法[9～12]等以及基于人工智能的调度算法（遗传算法、蚁群算法）[13,14]等。上述算法将任务与资源绑定时，更多的是考虑如何缩短任务执行时间，但云计算的目标是提供按需服务，这样无法反映用户真实的QoS要求。另外，传统的任务调度算法在选择资源时，其针对的对象是全体服务资源，未考虑资源本身的特性和用户或任务的偏好，导致资源选择的开销大且存在盲目性。因此找到一种合适的方法对资源进行一定程度的划分能够缩小资源选择范围，从而降低任务调度开销。聚类方法是对目标进行分类的有效手段。聚类的主要方法有：谱系聚类法、基于等价关系的聚类方法、图论聚类法和基于目标函数的聚类方法等[15～17]。……