1.一种云工作流虚拟机配置和任务调度协同优化方法，其特征在于：包括以下步骤：步骤1：获取云工作流执行优化所需的信息；

获取任务集T＝{t1,...,tI}，ti表示任务i，即编号为i的任务；其中I是需要调度的任务数量；

获取任务间的时序关系：任务i的父任务集PRi，任务i的子任务集SCi，其中i＝1,…,I；

+ +

其中 为任务i的父任务集， 为任务i；

获取任务相关参数：任务i的长度leni、leni＞0，即任务i被虚拟机处理时需要耗费的指令数量，处理任务i时需要的输入文件列表IFLi、 任务i被处理后产生的输出文件列表OFLi、 及文件列表中文件file的大小file.size，其中：i＝1,…,I；任务i是+任务i的父任务的充要条件为：存在一个文件file，file是任务i的输出文件同时又是任务+i的输入文件，即：

获取云计算环境下虚拟机类型集VM＝{vm1,vm2,…,vmJ}，其中J是虚拟机的类型数量，vmj表示j类虚拟机；

获取虚拟机相关参数：j类虚拟机的计算能力psj，j类虚拟机的带宽bwj，j类虚拟机的单位时间成本vcj，j类虚拟机的固定起租成本fcj，j类虚拟机的最小计费时间单位utj，j类虚拟机的最小起租时间ftj；租用j类虚拟机的成本计算如下：其中：lt为租用时间，j＝1,2…,J；

获取云计算环境下工作流执行的成本约束Budget与时间约束Deadline；若没有成本约束则设置Budget＝MBV，若没有时间约束则设置Deadline＝MDV；其中：MBV为成本上限，MDV为时间上限；

步骤2：计算任务的层次值；

对于没有父任务的开始任务i，其层次值为：

lvli＝1                                                             (1)其它任务的层次值采用如下递归公式进行计算：‑ ‑

其中lvli为任务i的层次值，任务i为任务i的一个父任务， 为任务i的层次值；

步骤3：初始化当代种群；

当代种群中包含S个子种群，每个子种群又包含N个个体，N为偶数且N>S，其初始化过程如下：对每个当代子种群基于层次和效益比生成1个个体，然后基于层次的随机方法生成剩余N‑1个不同的个体；

所述个体编码方法如下：ch＝{gr1,…,grI；gs1,…,gsI；gt1,…,gtI}；其中{gr1,…,grI}是任务调度顺序列表，为任务编号的一个拓扑排序；{gs1,…,gsI}是虚拟机分配列表，即虚拟机实例列表，gsi表示给任务i分配的虚拟机实例编号，其中：gs1＝1，gsi≤max{gs1,…,gsi‑1}+1；{gt1,…,gtI}是虚拟机类型列表，gti表示编号为i的虚拟机实例的类型，gt1,…,gtI的取值为1到J之间的整数值；

所述基于层次和效益比生成1个个体的方法包括如下步骤：步骤A1：根据任务层次值从小到大随机排列任务，即层次值小的排在大的前面，具有相同层次值的则随机排列，形成个体的任务调度顺序列表{gr1,…,grI}；

步骤A2：基于效益比生成个体的虚拟机分配列表{gs1,…,gsI}和虚拟机类型列表{gt1,…,gtI}；获得所有任务的开始时间si和结束时间fi，i＝1,…,I；

步骤A3：输出一个个体{gr1,…,grI；gs1,…,gsI；gt1,…,gtI}，操作结束；

进一步的，所述步骤A2中基于效益比生成个体的虚拟机分配列表{gs1,…,gsI}和虚拟机类型列表{gt1,…,gtI}的具体步骤如下：步骤A2.1：令虚拟机实例集 令所有任务的就绪时间rt1＝…＝rtI＝0；令变量α＝1；

步骤A2.2：令变量i＝grα；令变量K＝|INS|、变量k＝1、变量β＝1；计算把ti分别分配给每个潜在虚拟机实例后的综合效益比：步骤A2.2.1：如果k≤K，则转到步骤A2.2.2，否则，转到步骤A2.2.6；

步骤A2.2.2：计算ti分配给编号为k的虚拟机实例后的执行时间其中： 是把ti分配给编号为k的虚拟机实例处理时任务的处理时间，是编号为k的虚拟机实例的处理能力； 是把ti分配给编号为k的虚拟机实例处理时需要从其它的虚拟机获得输入文件的文件传输时间，‑ ‑

k是处理 的虚拟机实例编号， 和 是编号为k和k的虚拟机实例的带宽； 是把ti分配给编号为k的虚拟机实例处理时需要从共享数据库获得输入文件的文件传输时间，步骤A2.2.3：在虚拟机可得时间段列表vatlk中从早到晚找出一个空闲时段[νk,υk]，满足υk‑νk≥eti,k和υk‑eti,k≥rti；

步骤A2.2.4：计算ti分配给编号为k的虚拟机实例后的开始时间si,k＝max{νk,rti}，完成时间fi,k＝si,k+eti,k；

步骤A2.2.5：计算综合效益比ξi,k：

其中：θ∈[0,1]是权重系数，

μ＞0是成本与时间的协调系数，

为ti分配给编号为k的虚拟机实例后编号为k的虚拟机实例的租用时间，ltk′＝Rntk′‑Hrtk′为ti还没有分配给编号为k的虚拟机实例前编号为k的虚拟机实例的租用时间，为ti还没有分配给编号为k的虚拟机实例前编号为k的虚拟机实例的归还时间； 为ti还没有分配给编号为k的虚拟机实例前编号为k的虚拟机实例的开始租用时间；令k＝k+1，转到步骤A2.2.1；

步骤A2.2.6：如果β≤J，转到步骤A2.2.7，否则转到步骤A2.3；

步骤A2.2.7：计算ti分配给一个新的类型为β的虚拟机实例后的执行时间其中：ωi,β是类型为β的虚拟机实例处理ti的时间，ωi,β＝leni/psβ； 是把ti分配给类型为β的虚拟机实例处理时需要从其它的虚拟机获得输入文件的文件传输时间，‑k是处理 的虚拟机实例编号；τi,β是把ti分配给类型为β的虚拟机实例处理时需要从共享数据库获得输入文件的文件传输时间，步骤A2.2.8：计算ti分配给这个新的类型为β的虚拟机实例后的开始时间si,K+β＝rti，完成时间fi,K+β＝si,K+β+eti,K+β；

步骤A2.2.9：计算综合效益比ξi,K+β：其中

为ti分配给新的类型为β的虚拟机实例后这个新的类型为β的虚拟机实例的租用时间；令β＝β+1，转到步骤A2.2.6；

步骤A2.3：从ξi,1,…,ξi,K+J中找出一个最小的，不妨设为 如果下标值 那么令否则，令gsi′＝K+1、 增加一个编号为K+1的虚拟机实例insK+1，即INS＝INS∪insK+1；令vatlK+1＝{[0,∞]}；

步骤A2.4：把任务i分配给虚拟机实例k＝gsi′：步骤A2.4.1：计算任务的开始时间 结束时间 执行时间eti＝si‑fi；

步骤A2.4.2：更新任务i的子任务的就绪时间步骤A2.4.3：在虚拟机可得时间段列表vatlk中从早到晚找出一个空闲时段[νk,υk]，满足υk‑νk≥eti和υk‑eti≥rti；

步骤A2.4.4：在vatlk中删除[νk,υk]，插入区间长度大于0的[νk,si]和[fi,υk]；

步骤A2.5：令α＝α+1；如果α≤I，那么转到步骤A2.2，否则转到步骤A2.6；

步骤A2.6：按任务编号顺序对虚拟机实例进行重新编号，随机生成未被使用的虚拟机实例的类型：步骤A2.6.1：令变量i＝1、变量δ＝1；令标记值flg1＝...＝flgI＝0；

步骤A2.6.2：如果flgi＝0，则转到步骤A2.6.3，否则转到步骤A2.6.4步骤A2.6.3：对所有满足分配的虚拟机实例编号为k＝gsi′的任务i′，令gsi′＝δ、flgi′＝1；令gtδ＝gtk′；令δ＝δ+1；

步骤A2.6.4：令i＝i+1，如果i≤I，则转到步骤A2.6.2，否则转到步骤A2.6.5；

步骤A2.6.5：如果δ≤I，那么生成I‑δ+1个1到J之间的随机整数，不妨设为：πδ，…，πI；

令：gtδ＝πδ，…，gtI＝πI；

步骤A2.7：获得一个个体{gr1,…,grI；gs1,…,gsI；gt1,…,gtI}；

所述基于层次的随机方法生成1个个体包括如下步骤：步骤B1：随机生成I个1到J之间的整数：π1,…,πI；

步骤B2：随机生成虚拟机分配列表和类型列表：

步骤B2.1：随机生成I个1到I之间的整数：σ1,…,σI；令gs1＝…＝gsI＝0，令变量i＝1、变量q＝1；

步骤B2.2：如果i≤I转到步骤B2.3，否则转到步骤B2.6；

步骤B2.3：如果gsi＝0，则转到步骤B2.4，否则转到步骤B2.5；

步骤B2.4：找出所有σi′＝σi的i′，令gsi′＝q、 令q＝q+1；

步骤B2.5：令i＝i+1，转到步骤B2.2；

步骤B2.6：如果q≤I则生成I‑q+1个1到J之间的整数πq′,…,πI，令gtq＝πq′,…,gtI＝πI′；转到步骤B3；

步骤B3：根据任务层次值从小到大随机排列任务，即层次值小的排在大的前面，具有相同层次值的则随机排列，形成个体的任务调度顺序列表{gr1,…,grI}；

步骤B4：输出一个个体{gr1,…,grI；gs1,…,gsI；gt1,…,gtI}，操作结束；步骤4：对当代种群中的所有个体采用FBI&D进行解码与改进，获得所有个体的工作流响应时间和执行成本，然后计算所有不可行个体的相对适应度值和可行个体的绝对适应度值；

对于每个当代子种群中的每个个体chn，所述FBI&D包括如下步骤：步骤C1：令工作流反向响应时间

步骤C2：采用基于插入模式的串行个体解码方法对个体chn进行解码，获得所有任务的完成时间f1,…,fI及其工作流响应时间rsn；如果rsn小于rsn，则转到步骤C3，否则，转到步骤C6；

步骤C3：把个体chn中的任务调度顺序列表根据任务完成时间fi从大到小重新排列，即把chn中的基因gri设置为倒数第i个完成的任务，i＝1,…,I，形成反向个体步骤C4：采用基于插入模式的串行反向个体解码方法对反向个体 进行解码，获得所有任务反向完成时间 及其工作流反向响应时间 若 小于rsn，则转到步骤C5，否则，转到步骤C6；

步骤C5：把反向个体 中的任务调度顺序列表根据任务反向完成时间 从大到小重新排列，即把 中的基因gri设置为倒数第i个完成的任务，i＝1,…,I，形成个体chn，转到步骤C2；

步骤C6：输出个体chn及其工作流响应时间rsn，并计算其工作流执行成本ctn，操作结束；

所述基于插入模式的串行个体解码方法对个体chn进行解码包括如下步骤：步骤D1：令所有任务的就绪时间：rti＝…＝rtI＝0；令变量δ＝1；令所有虚拟机实例的可得时间段列表catlk＝{[0,∞]}，k＝1,…,max{gs1,…,gsI}；

步骤D2：选取编号为i＝grδ的任务；

步骤D3：基于插入模式把任务i分配给编号为k＝gsi的虚拟机实例；

步骤D3.1：计算任务i的执行时间

步骤D3.2：在vatlk中从早到晚找出一个空闲时段[νk,υk]，满足υk‑νk≥eti和υk‑eti≥rti；

步骤D3.3：计算任务i的开始时间si＝max{νk,rti}，完成时间fi＝si+eti；

步骤D3.4：更新任务i的子任务的就绪时间

步骤D3.5：在虚拟机可得时间段列表vatlk中删除[νk,υk]，插入区间长度大于0的[νk,si]和[fi,υk]；

步骤D4：令δ＝δ+1，如果δ≤I，则转到步骤D2，否则转到步骤D5；

步骤D5：获得任务的开始时间和结束时间：si，fi，i＝1,…,I，计算工作流响应时间rsn，操作结束；

所述基于插入模式的串行反向个体解码方法对反向个体 进行解码包括如下步骤：步骤E1：令所有任务的反向就绪时间 其中，

SFLi是任务i输出给共享数据库的输出文件集，即 i＝1,…,I；令变量δ＝1；令虚拟机可得时间段列表vatlk＝{[0,∞]}，k＝1,…,max{gs1,…,gsI}；

步骤E2：选取编号为i＝grδ的任务；

步骤E3：基于插入模式把任务i分配给编号为k＝gsi的虚拟机实例：步骤E3.1：计算任务i的执行时间

步骤E3.2：在vatlk中从早到晚找出一个空闲时段[νk,υk]，满足υk‑νk≥eti和步骤E3.3：计算任务i的反向开始时间 反向完成时间步骤E3.4：更新任务i的父任务的反向就绪时间步骤E3.5：在虚拟机可得时间段列表vatlk中删除[νk,υk]，插入区间长度大于0的和步骤E4：令δ＝δ+1，如果δ≤I，则转到步骤E2，否则转到步骤E5；

步骤E5：获得任务的反向开始时间 和反向完成时间 i＝1,…,I，及工作流反向响应时间 操作结束；

步骤5：判断是否满足终止条件，如满足，则进化结束转到步骤9，否则转到步骤6；

所述终止条件为迭代到指定的代数TG或连续迭代GG代都没有出现可行个体或最优可行个体没有改进；

步骤6：判断是否满足进行子种群间交流的条件；如果满足则转到步骤7，否则直接转到步骤8；

所述进行子种群间交流的条件为每迭代EFG代或自上次交流后连续迭代EVG代最优个体没有改进；

步骤7：进行子种群间的交流；

步骤7.1：令精英个体集 从每个当代子种群s即CPs中选出当前TPS中尚不存在的1个最优个体，不妨设其为 把 放到TPS中，s＝1,…,S；

步骤7.2：对每个CPs，s＝1,…,S，用TPS中的不同优质个体替换CPs中的劣质个体；

步骤8：每个子种群进行独立进化；

步骤8.1：对每个当代子种群进行交叉操作形成新子种群；

步骤8.2：对每个新子种群进行变异操作；

步骤8.3：对每个新子种群中的所有个体采用FBI&D进行解码与改进，获得所有个体的执行成本和响应时间，然后计算所有不可行个体的相对适应度值和可行个体的绝对适应度值；

步骤8.4：对于每个子种群，从优到劣依次从当代子种群和新子种群中选出N个不同的个体形成新的当代子种群，转到步骤5；

对每个当代子种群，所述交叉操作包括如下步骤：

步骤F1：令变量n＝1，新子种群为空；

步骤F2：采用基于排序的轮赌法从当代种群中随机选择两个不同个体作为父体1和父体2，不妨设为通过交叉生成的子体1和子体2为：

步骤F3：随机产生一个1到I‑1的正整数α；随机产生一个小数λ∈[0,1)，如果λ＜0.5则转到步骤F4，否则转到步骤F5；

步骤F4：如果n为奇数，则转到步骤F4.1；否则转到步骤F4.2；

c1

步骤F4.1：进行基于拓扑排序的任务列表后交叉操作：ch 的任务调度顺序列表的前αc1 p1个基因、虚拟机实例列表、虚拟机类型列表来自于父体1，即：gri ＝gri ，1≤i≤α，c1ch 的任务调度顺序列表的

后I‑α个基因来自于父体2的任务调度顺序列表 中删除父体1的任务调度顺c2

序列表的前α个基因 后的基因列表；ch 的任务调度顺序列表的前α个基因、虚c2 p2拟机实例列表、虚拟机类型列表来自于父体2，即：gri ＝gri ，1≤i≤α，c2ch 的任务调度顺序列表的

后I‑α个基因来自于父体1的任务调度顺序列表 中删除父体2的任务调度顺序列表的前α个基因 后的基因列表；转到步骤F6；

c1

步骤F4.2：进行基于拓扑排序的任务列表前交叉操作：ch 的任务调度顺序列表的后αc1 p1个基因、虚拟机实例列表、虚拟机类型列表来自于父体1，即：gri ＝gri ，I‑α+1≤i≤I，c1ch 的任务调度顺序列表的

前I‑α个基因来自于父体2的任务调度顺序列表 中删除父体1的任务调度顺c2

序列表的后α个基因 后的基因列表；ch 的任务调度顺序列表的后α个基因、c2 p2虚拟机实例列表、虚拟机类型列表来自于父体2，即：gri ＝gri ，I‑α+1≤i≤I，c2ch 的任务调度顺序列表的

前I‑α个基因来自于父体1的任务调度顺序列表 中删除父体2的任务调度顺序列表的后α个基因 后的基因列表；转到步骤F6；

步骤F5：进行虚拟机实例和类型的一体化交叉操作：c1

步骤F5.1：子体ch 的任务调度顺序列表，虚拟机实例列表的前α基因，虚拟机类型列表p1来自于ch ，即： 1≤i≤α，

c2 p2

子体ch 的任务调度顺序列表，虚拟机实例列表的前α基因，虚拟机类型列表来自于ch ，即： 1≤i≤α， 令标记值ffi＝0、标记值mfi＝0，α+1≤i≤I；令变量k＝α+1；

步骤F5.2：如果mfk＝0，则转到步骤F5.3，否则转到步骤F5.4；

步骤F5.3：如果 则 在 和 中随机选择一个值替换 否则，令 并对所有满足 的

k′∈(k,I]，令 mfk′＝1；

步骤F5.4：如果ffk＝0，则转到步骤F5.5，否则转到步骤F5.6；

步骤F5.5：如果 则 在 和 中随机选择一个值替换 否则，令 对所有满足 的k′

∈(k,I]，令 ffk′＝1；

步骤F5.6：令k＝k+1，如果k≤I转到步骤F5.2；否则转到步骤F6；

c1 c2

步骤F6：获得子体ch 和ch ，并把它们放到新子种群中；令n＝n+1，如果n≤N/2，那么转到步骤F2；否则新子种群生成完毕，输出新子种群，子种群交叉操作结束；

对每个子种群，所述变异操作包括如下步骤：

步骤G1：令变量n＝1；

步骤G2：对新子种群中的第n个个体，生成一个随机数λ∈[0,1)，如果λ＜pm，则转到步骤G3，否则转到步骤G7；

步骤G3：在任务调度顺序列表、虚拟机实例列表、虚拟机类型列表中随机选择一个，如果是任务调度顺序列表，则转到步骤G4，如果是虚拟机实例列表，则转到步骤G5，另外则转到步骤G6；

步骤G4：进行任务调度顺序列表变异，即：从任务调度顺序列表中随机选择一个基因，不妨设为gri；如果任务gri存在父任务，则向前找到第一个父任务gri′，令位置值pos1＝i′+

1，否则令pos1＝1；如果任务gi存在子任务，则向后找到第一个子任务gri″，令位置值pos2＝i″‑1，否则令pos2＝I；在[pos1,pos2]之间重新随机选择一个位置插入gri；转到步骤G7；

步骤G5：进行虚拟机实例列表变异，即：

步骤G5.1：从虚拟机实例列表中随机选择一个基因，不妨设为gsi，令变量 在1到max{gs1,…,gsi‑1}+1之间重新随机选择一个值α；

步骤G5.2：如果α＜max{gs1,…,gsi‑1}+1且gsi＝max{gs1,…,gsi‑1}+1，则转到步骤G5.3，否则转到步骤G5.7；

步骤G5.3：在gsi+1,…,gsI中从前向后寻找第一个等于gsi的基因，如果存在，不妨设其为gsi′，转到步骤G5.4，否则转到步骤G5.6；

步骤G5.4：在gsi和gsi′之间找出值最大的基因，不妨设为gsi″，如果gsi″＞gsi，转到步骤G5.5，否则转到步骤G5.7；

步骤G5.5：把满足大于gsi小于等于gsi″之间的实例编号值减1，把除gsi外等于gsi的实例编号更新为gsi″，同时调整对应的虚拟机类型列表的编码，即：令其中

转到步骤G5.7；

步骤G5.6：把满足大于gsi的实例编号值减1，同时调整对应的虚拟机类型列表的编码，即：令 其中步骤G5.7：令gsi＝α；转到步骤G7；

步骤G6：进行虚拟机类型列表变异，即：从虚拟机类型列表的有效范围内随机选择一个基因，不妨设为gti，i∈[1,max{gs1,…,gsI}]；为编号为i的实例重新随机选择一个虚拟机类型，不妨设为j，则令gti＝j，转到步骤G7；

步骤G7：令n＝n+1，如果n≤N，转到步骤G2；否则，新子种群变异操作结束；

其中，pm∈[0,1)是变异率；

步骤9：如果当代种群中存在可行个体，那么输出当代种群中绝对适应度值最小的个体，其对应的执行方案为优化方案，否则无可行执行方案。

2.根据权利要求1所述的一种云工作流虚拟机配置和任务调度协同优化方法，其特征在于：所述MBV和MDV的一种具体计算方法如下：其中： 为ti的最大执行时间。

3.根据权利要求1所述的一种云工作流虚拟机配置和任务调度协同优化方法，其特征在于：对于每个子种群中的每个个体chn，所述工作流响应时间rsn和执行成本ctn的具体计算方法如下：其中：rfi是任务i的响应时间，

其中： 是编号为k的虚拟机实例的固定起租成本， 是编号为k的虚拟机实例的单位时间成本， 是编号为k的虚拟机实例的最小计费时间单位， 是编号为k的虚拟机实例的最小起租时间， 是编号为k的虚拟机实例的带宽，ltk＝Rntk‑Hrtk是编号为k的虚拟机实例的租用时间，Hrtk为编号为k的虚拟机实例的开始租用时间；Rntk为编号为k的虚拟机实例的归还时间； tfi是完成OFLi中的文件输出给相应接收者的最大时刻，如果ti没有文件输出给共享数据库即 那么相应接收者为处理ti的子任务的虚拟机，如果ti没有子任务即 那么相应接收者为共享数据库，另外如果ti即有文件输出给共享数据库又有子任务即 那么相应接收者为处理ti的子任务的虚拟机和共享数据库，

4.根据权利要求1所述的一种云工作流虚拟机配置和任务调度协同优化方法，其特征在于：对于每个子种群中的每个个体chn，n＝1,2…,N，如果ctn≤Budget∨rsn≤Deadline，则chn为可行个体，否则chn为不可行个体；

所述不可行个体的相对适应度值的具体计算方法如下：所述可行个体的绝对适应度值的具体计算方法如下：afitn＝θ×μ×ctn+(1‑θ)×rsn；

其中：θ∈[0,1]是权重系数，μ＞0是成本与时间的协调系数；

进行个体优劣比较时，可行个体优于不可行个体；对于都是可行个体，则绝对适应度值越小，个体越优；对于都是不可行个体，则相对适应度值越小，个体越优。

5.根据权利要求1所述的一种云工作流虚拟机配置和任务调度协同优化方法，其特征在于：所述步骤F2中基于排序的轮赌法从当代子种群中随机选择两个不同个体作为父体1和父体2的具体步骤如下：步骤F2.1：对当子代种群中的个体从优到劣进行排序，获得个体n的排序值rkn，n＝

1,…,N，其中最优的其取1，次优的其取2，以此类推，最劣的其取N；

步骤F2.2：计算个体n被选中的概率 n＝1,…,N，R＞1为区分度系数；

步骤F2.3：计算累计概率 n＝1,…,N；

步骤F2.4：产生一个随机数λ1∈[0,1)，如果 那么选择个体n作为父体

1；

步骤F2.5：产生一个随机数λ2∈[0,1)，如果 并且n′≠n，那么选择个体n′作为父体2，转到步骤F2.6，否则转到步骤F2.5；

步骤F2.6：个体选择操作结束。

6.根据权利要求1所述的一种云工作流虚拟机配置和任务调度协同优化方法，其特征在于：所述步骤7.2中用TPS中的不同优质个体替换CPs中的劣质个体的具体步骤如下：步骤7.2.1：在TPS中取出CPs中不存在的个体集TPSCs＝TPS‑CPs；

步骤7.2.2：如果TPSCs不为空，则转到步骤7.2.3，否则转到步骤7.2.6；

步骤7.2.3：从TPSCs中取出一个最优的个体，不妨设为chbt；如果chbt优于CPs中的最劣个体，则转到步骤7.2.4，否则转到步骤7.2.5；

步骤7.2.4：用chbt替换CPs中的最劣个体；

步骤7.2.5：在TPSCs中删除chbt，转到步骤7.2.2；

步骤7.2.6：替换操作结束。