魏士伟 邓 维

(桂林航天工业学院计算机科学与工程学院 广西 桂林 541004)

0 引 言

云计算是一种新兴的信息技术，它将传统的以单机节点形式的任务处理方式转换成以网络为中心的任务处理模式，从而提高了系统扩展的灵活性，降低了硬件建设的成本[1]。用户只需将他们所要完成的任务提交到云计算系统，云计算服务提供商就可根据用户的需求快速提供计算和存储等服务，从而完成任务的执行，真正实现按需计算[2]。云计算服务提供商提供的服务通常以虚拟机(Virtual Machine,VM)的形式表示[3]。通常，云计算系统中用户的数量和用户提交的任务数量规模很大，云计算中心每时每刻都要处理海量的任务。因此，如何高效而合理地进行任务调度是云计算要解决的一个关键问题。然而，云计算任务调度问题已被证明是一个NP完全问题[4-5]。云计算系统中的节点具有异构、动态、复杂等特点，使用传统的、具有固定规则式的调度策略和算法来解这类问题会面临很大挑战。因此，在具体的工程实践中，研究人员常常用进化算法、启发式算法等来求解云资源的调度问题[6-11]，并且取得了不错的效果。虽然这些算法不能保证一定可以求解出云资源任务调度问题的全局最优解(精确解)，但其求解出来的较优解(或局部最优解)往往与精确解的差别很小，完全能够满足工程实践的需要。因此，用进化算法来解决云资源调度问题已经成为一个研究热点。

遗传算法是最经典的一种进化算法，在1975年由Holland[12]首次提出。……