基于遗传算法的云计算任务调度研究(2)
定义1：集合C={c1，c2，…cn}表示由n个异构的物理机构成的云环境下提供服务的物理服务器资源。
定义2：集合T={t1，t2，…tm}表示由m个独立的任务构成的任务集合。
本文所要解决的主要问题是如何将M个任务合理的调度到N台服务器上以使任务的总完成时间最短。为了解决该问题，我们对单个物理服务器、单个任务以及任务完成时间有如下定义。
定义3：单个物理服务器ServiceComputer(Cid,ComputeAbility)其中，Cid表示服务器编号，ComputeAbility表示服务器的计算能力。
定义4：单个任务Task(Tid,TaskData)其中，Tid表示任务的编号，TaskData表示任务需要处理的数据量。
定义5：矩阵CT=其中，ctij表示tj在物理服务器ci上的执
行时间，矩阵初始状态为∞，代表tj不在服务器ci上。
2.2数学模型的建立
云环境下的离线式任务调度问题实际就是批处理机随机调度问题，即M个任务在N个处理机上进行调度执行。为简单起见，本论文中所讨论的任务都是独立的，并且处理机之间是异构的。针对上节中的定义，那么一个可行的调度π可描述为：π中还有M个任务，N个处理机，于是：π=（Jctij）。现在我们所要解决的问题就是如何把M个任务合理的分配到N个处理机上，使得所有任务的完成时间最短。
给定C，T，CT，那么我们的目标是设计一个调度算法使得
其中ctij表示第i个任务在第j个处理机上的完成时间。Ttotal表示任务的总完成时间。
3基于遗传算法的云环境任务调度算法实现
3.1遗传算法简介
遗传算法（GA）是模拟生物在自然环境下的遗传和进化过程而形成的一种适应性的全局优化概率搜索方法[7]。它采纳了自然进化模型，从可能潜在解集的一个种群开始，该初始种群是由经过基因编码的特定数目的个体组成的。初始种群产生后，按照优胜劣汰和适者生存的原则，逐代产生出越来越优的解，其大致过程为：
（1）在每一代，根据问题域中个体的适应度值选择个体；
（2）借助遗传算子和变异算子进行基因交叉和主客观变异，产生出新的解集，并将其作为下一代的初始种群。这一过程要循环执行，直到满足终止条件为止；
（3）末代个体经解码，生成最优解或近似最优解。这种种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，最终找到最优解或者近似最优解。
3.2模拟退火算法简介
模拟退火算法(Simulated Annealing，SA)最早由Kirkpatrick等应用于组合优化领域，它是基于Monte-Carlo迭代求解策略的一种随机寻优的算法[8]。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其冷却，加温时，固体内部粒子随温度升高逐渐变为无序状态，内能增大，而冷却时粒子随温度降低逐渐变为有序状态，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小[9]。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法[10]：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索算法[11]。
3.3算法设计
3.3.1适应度函数的选取
本文研究的主要内容是如何将M个任务调度到N台服务器上使得M个任务的总完成时间最小，为简单起见，本文只考虑了任务的完成时间最短这一个因素。由2.2节中建立的数学模型我们知道，我们现在的目标是使任务的总完成时间最短，因此适应度函数设计如下：
下一篇：数字签名系统的设计与实现+流程图