孙长亚 王向文

1(上海电力大学计算机科学与技术学院 上海 200090)2(上海电力大学电子与信息工程学院 上海 200090)

0 引 言

云计算的基础设施规模比单一的物理设备大很多，但是其提供的虚拟资源仍然有限，面对庞大的云任务，如何高效地将子任务分配给虚拟资源，进行合理的任务调度已成为一项必不可缺的研究课题[1-4]。先前解决云计算任务调度问题的各种努力主要针对完工时间[5-6]。随着按需付费模式的普及，用户也会重点关注执行成本，对云服务提供商而言，还需要考虑虚拟机的负载均衡。几种经典的调度算法虽然实现简单，但是缺点很明显，如Min-Min算法[7]、Max-Min算法[8]和先进先出(First In First Out，FIFO)算法[9]。前两个算法未能有效利用资源，从而容易导致负载不均衡的问题；FIFO算法按任务提交顺序安排资源，如果较早提交的任务占用大量计算资源，则后面较小的任务必须等待很长时间。许多研究者使用启发式算法解决云计算任务调度的问题。例如:文献[10]提出了一种基于粒子群算法(PSO)的云任务调度方案，用于减少总执行时间和任务传输时间，并且证明了PSO比遗传算法运行的更快，有效减少了任务的执行时间，但是PSO可能会陷入局部最优解，容易导致求解精度下降，进而增加任务的完工时间和执行成本；文献[11]使用改进的蚁群算法进行云计算资源调度，通过信息素的累积和更新寻找较精确的解决方案，但是由于求解初期信息素匮乏，导致求解速率较慢，这样可能会占用用户大量时间，不能很好地满足用户的服务质量需求；……