1.一种基于二维多种群遗传算法的多模资源受限项目调度方法，其特征在于：包括以下步骤：步骤1：形式化多模资源受限项目调度问题，获取调度优化所需的信息；

获取项目任务集T＝{tj|j＝0,1,...,J,J+1}；其中tj表示任务j，即编号为j的任务，t0与tJ+1是人为增加的虚拟任务，即不占用项目工期也不占用资源，J是需要调度的实际任务数量；

‑

获取任务间的时序关系，即任务j的父任务集PRj和子任务集SCj，任务j在其父任务j ∈PRj全部完工之前不能开始执行，j＝0,1,…,J+1，t0没有父任务即 tJ+1没有子任务即获取可更新资源k在任意时刻的可使用量Rk，k＝1,…,K，K是可更新资源种类数量；获取不可更新资源l在整个项目工期中的可使用量Nl，l＝1,…,L，L是不可更新资源种类数量；

获取任务j在模式m下执行时需要的时间即工期dj,m和占用的可更新资源k的数量rj,m,k、不可更新资源l的数量nj,m,l；j＝1,…,J，m＝1,…,Mj，k＝1,…,K，l＝1,…,L，其中Mj是可供任务j选择采用的模式数量；

步骤2：如果存在不可更新资源l满足 或存在一个任务j和可更新资源k满足 那么该问题不存在可行的调度方案，求解结束，否则转到步骤

3；

步骤3：进行预处理：对模式和资源进行冗余和无效检查，去除冗余模式、无效模式和冗余资源；

步骤3.1：令模式标记值mflg＝0、资源标记值rflg＝0；如果存在rj,m,k＞Rk或nj,m,l＞Nl，那么对于任务j模式m是无效的，在任务j中去除模式m：令其中： k＝1,…,K，l＝1,…,L；令Mj＝Mj‑1；

步骤3.2：如果mflg＝0，那么令mflg＝1，转到步骤3.3；否则转到步骤3.4；

步骤3.3：如果存在任务j，模式m和m′满足：dj,m′≤dj,m，rj,m′,k≤rj,m,k，nj,m′,l≤nj,m,l，m′≠m，k＝1,…,K，l＝1,…,L；那么对于任务j模式m是冗余的，在任务j中去除模式m：令其中： k＝1,…,K，l＝1,…,L；

令Mj＝Mj‑1，rflg＝0；

步骤3.4：如果rflg＝0，那么令rflg＝1，转到步骤3.5；否则转到步骤3.7；

步骤3.5：如果可更新资源k满足： 那么该可更新资源是冗余的，去除可更新资源k：令 其中：j＝1,…,J， 令K＝K‑1，mflg＝0；

步骤3.6：如果不可更新资源l满足： 那么该不可更新资源是冗余的，去除不可更新资源l：令 其中：j＝1,…,J， 令L＝L‑1，mflg＝0；

步骤3.7：如果mflg＝1∧rflg＝1，那么转到步骤3.8，否则转到步骤3.2；

步骤3.8：预处理结束；

步骤4：计算任务的排序值rank和层次值lvl；

首先，计算任务j的平均执行时间

然后，计算任务的排序值rank：

对于没有子任务的结束任务J+1：

rankJ+1＝0                                                   (2)其它任务的rank采用如下递归公式进行计算：最后，计算任务的层次值lvl：

对于没有父任务的开始任务0，其层次值为：lvl0＝0                                                          (4)其它任务的层次值采用如下递归公式进行计算：其中：j＝1,…,J

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

当代种群中包含S个子种群，每个子种群又包含N个个体，N＞S，其初始化过程如下：对每个当代子种群采用基于rank和任务最早完成时间的个体生成方法生成一个个体，然后采用基于层次的个体随机生成方法生成剩余的N‑1个不同的个体；

个体ch采用2×J的二维整数编码，其方法如下：ch＝{(g1,1,g1,2),…,(gJ,1,gJ,2)}，基因对(gj,1,gj,2)是一对任务和执行模式编号，其中gj,1是任务编号，gj,2是执行模式编号，即任务gj,1采用执行模式gj,2，g1,1,g2,1,…,gJ,1是1,…,J的一个排列，为任务调度顺序，且满足任务的时序约束；

所述基于rank和任务最早完成时间的个体生成方法包括如下步骤：步骤A1：系统状态初始化：令任务0的完成时间f0＝0、任务完成时间集F＝{f0,lf}，lf表示项目的最晚完成时间： F中的元素从小到大排列；令对应于F中各完成时间可更新资源的剩余可用量： k＝1,…,K；令循环控制变量δ＝1；令待处理任务集UT＝{t1,t2,…,tJ}；

步骤A2：从UT中取出rank最大的任务，不妨设为tj，gδ,1＝j，令模式m＝1；

步骤A3：计算任务j的完成时间fj，即：步骤A3.1：令任务j在模式m下的开始时间 令标记值flag＝1；

步骤A3.2：在F中找出大于等于rtj的元素，并组成集合TF，即TF＝{f∈F|f≥rtj}；

步骤A3.3：从TF中取出一个值最小的元素，不妨设为fj′；

步骤A3.4：如果flag＝1并且fj′‑sj,m≥dj,m，那么转到步骤A3.7；否则转到步骤A3.5；

步骤A3.5：如果flag＝0，那么令sj,m＝fj′，flag＝1；

步骤A3.6：判断fj′时刻所有可更新资源的剩余可用量是否满足任务j的需求，即判断所有的k＝1,…,K是否满足 如果有不满足则flag＝0；转到步骤A3.3；

步骤A3.7：令fj,m＝sj,m+dj,m；

步骤A3.8：令m＝m+1；如果m≤Mj则转到步骤A3.1，否则从 中取出完成时间最小的，不妨设其为 对应的模式为 令任务j在模式为 情况下的完成时间 任务j的开始时间 转到步骤A4；

步骤A4：如果fj在F中不存在，则F＝F∪{fj}，增加fj时刻可更新资源的剩余可用量：其中：fj″是fj的前一个时刻；

步骤A5：更新[sj,fj)时段内可更新资源的剩余可用量：其中 为在[sj,fj)时段内其完成的任务的编号， 为任务j在模式 下执行时需要占用的可更新资源k的数量；

步骤A6：令δ＝δ+1，如果δ≤J则转到步骤A2，否则转到步骤A7；

步骤A7：获得一个个体ch＝{(g1,1,g1,2),…,(gJ,1,gJ,2)}，操作结束；

其中： 表示τ时刻可更新资源k的剩余可用量；

所述基于层次的个体随机生成方法包括如下步骤：步骤B1：令循环控制变量δ＝1；令待处理任务集UT＝{t1,t2,…,tJ}；

步骤B2：从UT中找出层次值最小的任务，从中随机取出一个，不妨设为tj，则对应基因对中的gδ,1＝j，其中δ为该次循环控制变量；

步骤B3：在tj的执行模式中随机选择一个，即在1,…,Mj中随机选择一个整数，不妨设为m；则对应基因对中的gδ,2＝m；

步骤B4：令δ＝δ+1，如果δ≤J则转到步骤B2，否则转到步骤B5；

步骤B5：获得一个个体ch＝{(g1,1,g1,2),…,(gJ,1,gJ,2)}，操作结束；

步骤6：采用FBI&D方法改进初始种群中的所有个体并计算其适应度值；

所述FBI&D方法包括如下步骤：

步骤C1：令计次变量θ＝1；对个体ch进行基于插入模式的串行个体解码获得所有任务的完成时间fj，j＝1,…,J，及适应度值fit；

步骤C2：把任务0变成任务J+1，任务J+1变成任务0，颠倒任务间的时序关系，即把任务的父任务集变成子任务集，子任务集变成父任务集，按任务完成时间从大到小对个体ch中的基因对(gj,1,gj,2)进行重新排列，即把个体中的基因gj,1设置为倒数第j个完成的任务，gj,2设置为倒数第j个完成的任务的执行模式，j＝1,…,J，形成个体步骤C3：令θ＝θ+1，对个体 进行基于插入模式的串行个体解码获得所有任务的完成时间 及适应度值步骤C4：若 那么 转到步骤C2，否则转到步骤C5；

步骤C5：如果θ为偶数那么输出个体ch，否则输出个体 适应度值为fit，操作结束；

所述基于插入模式的串行个体解码包括如下步骤：步骤D1：系统状态初始化：令任务0的完成时间f0＝0、任务完成时间集F＝{f0,lf}，F中的元素从小到大排列；令循环控制变量δ＝1；令对应于F中各完成时间的可更新资源的剩余可用量：步骤D2：取出任务j＝gδ,1，及其采用的模式m＝gδ,2；

步骤D3：计算任务j的完成时间

即：

步骤D3.1：令任务j的开始时间sj＝rtj，令标记值flag＝1；

步骤D3.2：在F中找出大于等于rtj的元素，并组成集合TF，即TF＝{f∈F|f≥rtj}；

步骤D3.3：从TF中取出一个值最小的元素，不妨设为fj′；

步骤D3.4：如果flag＝1并且fj′‑sj≥dj,m，那么转到步骤D3.7；否则转到步骤D3.5；

步骤D3.5：如果flag＝0，那么令sj＝fj′，flag＝1；

步骤D3.6：判断fj′时刻所有可更新资源的剩余可用量是否满足任务j的需求，即判断所有的k＝1,…,K是否满足 如果有不满足则flag＝0，转到步骤D3.3；

步骤D3.7：令fj＝sj+dj,m；

步骤D4：如果fj在F中不存在，则F＝F∪{fj}，增加fj时刻可更新资源的剩余可用量：其中：fj″是fj的前一个时刻；

步骤D5：更新[sj,fj)时段内可更新资源的剩余可用量：步骤D6：令δ＝δ+1，如果δ≤J则转到步骤D2，否则转到步骤D7；

步骤D7：获得所有任务完成时间fj，j＝1,…,J；计算适应度值fit，操作结束；

步骤7：判断是否满足终止条件，如满足则进化结束转到步骤11，否则转到步骤8；

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

步骤8：判断是否需要进行子种群间的交流；如果需要则转到步骤9，否则转到步骤10；

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

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

步骤9.1：令精英个体集 从每个当代子种群s即CPs中根据适应度值从优到劣选出当前TPS中尚不存在的1个个体，不妨设其为 把 放到TPS中，其中s＝1,…,S，S为当代种群中子种群的数量；

步骤9.2：对每个CPs，s＝1,…,S，依次从CPs和TPS中从优到劣选出N个不同的个体形成新的CPs；

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

步骤10.1：对每个当代子种群进行N次基于偏好和拓扑排序的参数化均匀交叉操作形成新子种群；

步骤10.2：对每个新子种群中的每个个体进行变异操作；

步骤10.3：采用FBI&D方法改进每个新子种群中的所有个体并计算其适应度值；

步骤10.4：对于每个子种群从当代子种群和新子种群中从优到劣选出N个不同的个体作为下一代子种群，形成下一代种群，令下一代种群为当代种群，转到步骤7；

所述基于偏好和拓扑排序的参数化均匀交叉操作包括如下步骤：步骤E1：采用基于排序的轮赌法从当代子种群中随机选择两个不同的个体作为父体，p1 p2 p1 p2不妨设为ch 、ch ，且ch 优于ch ；令循环控制变量δ＝1，子体步骤E2：如果δ≤J，则转到步骤E3，否则转到步骤E4；

p1 c

步骤E3：生成一个随机数λ∈[0,1)，如果λ＜pb，那么从ch 中取出首基因对放到ch的尾p2 p2 c部，并从ch 中删除具有相同任务编号的基因对，否则从ch 中取出首基因对放到ch的尾p1部，并从ch 中删除具有相同任务编号的基因对；令δ＝δ+1，转到步骤E2；

步骤E4：输出子体 操作结束；

其中pb∈(0.5,1)为偏好率；

所述变异操作包括如下步骤：

步骤F1：产生一个随机数λ1∈[0,1)，如果λ1≤pm则转步骤F2；否则转步骤F5；

步骤F2：随机选择一个基因对，不妨设为(gj,1,gj,2)，并产生一个随机数λ2∈[0,1)，如果λ2＜0.5则转步骤F3；否则转步骤F4；

步骤F3：从任务gj,1可以执行的模式中重新随机选择一个执行模式m，gj,2＝m，转到步骤F5；

步骤F4：如果在任务1到任务J中，存在任务gj,1的父任务那么从(gj,1,gj,2)开始向前找到第一个父任务gj′,1，令位置值pos1＝j′+1，否则令pos1＝1；如果在任务1到任务J中，存在任务gj,1的子任务那么从(gj,1,gj,2)开始向后找到第一个子任务gj″,1，令位置值pos2＝j″‑1，否则令pos2＝J；在[pos1,pos2]之间重新随机选择一个位置插入(gj,1,gj,2)；

步骤F5：操作结束；

其中：pm∈(0,1]是变异率；

步骤11：如果当代种群中的最优个体为可行个体，那么输出最优个体对应的调度方案，及其项目执行时间 否则该问题无可行调度方案，其中PRJ+1是任务J+1的父任务集。

2.根据权利要求1所述的一种基于二维多种群遗传算法的多模资源受限项目调度方法，其特征在于：所述适应度值fit的具体计算方法如下：如果个体为不可行个体，即存在一个不可更新资源l满足 那么令个体的适应度值fit＝lf+ms，否则令个体适应度值fit＝ms，其中： 为项目执行时间；

所述适应度值fit越小，个体越优。

3.根据权利要求1所述的一种基于二维多种群遗传算法的多模资源受限项目调度方法，其特征在于：所述步骤E1中基于排序的轮赌法从当代子种群中随机选择两个不同的个体作为父体的具体步骤如下：步骤E1.1：对当代子种群中的个体从优到劣进行排序，获得个体n的排序值rkn，n＝

1,…,N，其中排第一的其取1，排第二的其取2，以此类推，排最后一名的其取N；

步骤E1.2：计算个体n被选中的概率 R＞1为区分系数；

步骤E1.3：计算累计概率

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

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

步骤E1.6：获得两个不同的个体n和n′作为父体，个体选择操作结束。