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

获取项目任务集T＝{t0,t1,…,tJ,tJ+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：计算任务的层次值：

对于没有父任务的开始任务0，其层次值为：lvl0＝0 (1)

其它任务的层次值采用如下递归公式进行计算：步骤5：初始化当代种群；

基于层次和任务最早完成时间的个体生成方法生成N个不同个体，形成初始当代种群，N为种群规模，且为正偶数；

个体ch采用2J位整数编码，其方法如下：ch＝{g1,…,gJ；gJ+1,…,g2J}，基因gj是一个正整数，其中，{g1,…,gJ}是执行模式列表，gj表示任务j采用的模式，gj＝1,...,Mj，j＝1,…,J；{gJ+1,…,g2J}是调度顺序列表，gJ+1,…,g2J是1,…,J的一个排列，且满足任务的时序约束，即任何任务都不能排在其父任务的前面，gJ+j表示第j个被调度的任务，即任务gJ+j是第j个被调度的；

所述基于层次和任务最早完成时间的个体生成方法包括如下步骤：步骤A1：根据任务层次值从小到大随机排列除t0与tJ+1以外的任务，即层次值小的排在大的前面，具有相同层次值的则随机排列，形成个体的调度顺序列表即基因{gJ+1,…,g2J}；

步骤A2：基于任务最早完成时间的个体串行解码方法生成个体执行模式列表即基因{g1,…,gJ}，获得其适应度值fit；

步骤A3：输出一个个体ch＝{g1,…,gJ,gJ+1,…,g2J}，操作结束；

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

步骤B2：取出任务j＝gJ+δ，令模式m＝1；

步骤B3：计算任务j的完成时间fj，即：步骤B3.1：令任务j的开始时间 令标记值flag＝1；

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

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

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

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

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

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

步骤B3.8：令m＝m+1；如果m≤Mj则转到步骤B3.1，否则从 中取出完成时间最小的，该最小完成时间对应的模式为 其值为 令任务j的完成时间 任务j的开始时间 转到步骤B4；

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

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

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

步骤B7：获得执行模式列表{g1,…,gJ}，计算个体的适应度值fit，操作结束；

其中： 表示τ时刻资源k的剩余可用量， 表示任务j的就绪时间；步骤6：对当代种群进行N/2次基于层次的调度顺序交叉操作生成新种群，对新种群中的每个个体采用基于层次的调度顺序变异操作；

所述基于层次的调度顺序交叉操作包括如下步骤：步骤C1：基于排序的轮赌法从当代种群中随机选择两个不同个体作为父体1和父体2；

步骤C2：随机选择一个层次，不妨设为l；

步骤C3：交换父体1的调度顺序列表和父体2的调度顺序列表中层次l的任务的调度顺序，并清空执行模式列表，生成两个子体1和子体2，操作结束；

所述基于层次的调度顺序变异操作包括如下步骤：步骤D1：产生一个随机数λ∈[0,1)，如果λ＜pm，则转到步骤D2，否则转到步骤D4；

步骤D2：如果存在层内任务数量大于1的层次，那么从中随机选择一个，不妨设为l，转到步骤D3；否则转到步骤D4；

步骤D3：从l层中随机选择两个任务，在调度顺序列表中交换这两个任务；

步骤D4：基于层次的调度顺序列表变异操作结束；

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

步骤7：对新种群中的每个个体采用基于任务最早完成时间的个体串行解码方法生成个体执行模式列表并计算其适应度值；

步骤8：从当代种群和新种群中从优到劣选出N个不同的个体形成新的当代种群；

步骤9：判断是否满足第一阶段迭代终止条件，如满足，则第一阶段进化结束转到步骤

10，否则转到步骤6；

第一阶段终止条件为迭代到指定的代数TG1或连续迭代GG1代最优个体没有改进；步骤

10：对当代种群进行N/2次执行模式列表和调度顺序列表交叉操作生成新种群，对新种群中的每个个体进行执行模式列表和调度顺序列表变异操作；

所述执行模式列表和调度顺序列表交叉操作包括如下步骤：步骤E1：基于排序的轮赌法从当代种群中随机选择两个不同的个体作为父体1和父体

2，不妨设为： 不妨设生成的子体1和子体2为：分别表示父体1和父体2中任务j采用的

模式， 分别表示父体1和父体2中第j个调度的任务；  分别表示子体1和子体2中任务j采用的模式， 分别表示子体1和子体2中第j个调度的任务；

步骤E2：如果 与 不同，那么转到步骤E3，否则

1≤j≤J，转到步骤E8；

步骤E3：从前向后找出 与 的第1个不同基因的位置δ1，从后向前找出 与 的第1个不同基因的位置δ2；如果δ1≠δ2，则转到步骤E4，否则 1≤j≤J，转到步骤E7；

步骤E4：随机产生一个δ1到δ2‑1的正整数α；

c1 p1

步骤E5：ch 的执行模式列表部分的前α个基因来自于ch 的执行模式列表部分的前α个p2基因，即 1≤j≤α；执行模式列表部分的后J‑α个基因来自于ch 的执行模式列表部分的后J‑α个基因，即 α＜j≤J；

c2 p2

步骤E6：ch 的执行模式列表部分的前α个基因来自于ch 的执行模式列表部分的前α个p1基因，即 1≤j≤α；执行模式列表部分的后J‑α个基因来自于ch 的执行模式列表部分的后J‑α个基因，即 α＜j≤J；

步骤E7：如果 和 不同，则转到步骤E8；否则J+1≤j≤2J，转到步骤E12；

步骤E8：从前向后找出 和 的第1个不同基因的位置δ3，从后开始向前找出 和 的第1个不同基因的位置δ4；

步骤E9：随机产生一个δ3到δ4‑1的正整数β；

c1 p1

步骤E10：ch 的调度顺序列表的前β个基因来自于ch 的调度顺序列表的前β个基因，即p2 p1

1≤j≤β；后J‑β个基因来自于ch 的调度顺序列表 中删除ch 的调度顺序列表的前β个基因 后的基因列表；

c2 p2

步骤E11：ch 的调度顺序列表的前β个基因来自于ch 的调度顺序列表的前β个基因，即p1 p2

1≤j≤β；后J‑β个基因来自于ch 的调度顺序列表 中删除ch 的调度顺序列表的前β个基因 后的基因列表；

步骤E12：获得 交叉操作结束；

所述执行模式列表和调度顺序列表变异操作包括如下步骤：步骤F1：产生一个随机数λ1∈[0,1)，如果λ1＜pm，则转到步骤F2；否则转到步骤F3；

步骤F2：从执行模式列表{g1,…,gJ}中随机选择一位基因，不妨设为gj，j＝1,…,J，为任务j重新随机选择一个执行模式，不妨设为m，则gj＝m；

步骤F3：产生一个随机数λ2∈[0,1)，如果λ2＜pm，则转到步骤F4；否则转到步骤F5；

步骤F4：从调度顺序列表{gJ+1,…,g2J}中随机选择一位基因，不妨设为gj，j＝J+1,…,

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

步骤F5：变异操作结束；

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

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

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

步骤G2：把任务0变成任务J+1，任务J+1变成任务0，颠倒任务间的时序关系，即把任务的父任务集变成子任务集，子任务集变成父任务集，把个体ch中的调度顺序列表根据任务完成时间fj从大到小重新排列，即把个体中的基因gJ+j设置为倒数第j个完成的任务，j＝

1,…,J，形成个体

步骤G3：令θ＝θ+1，对个体 进行基于插入模式的串行个体解码获得所有任务的完成时间 j＝1,…,J，及其适应度值步骤G4：若 那么 j＝1,…,J，转到步骤G2，否则转到步骤G5；

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

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

步骤H2：取出任务j＝gJ+δ，及其采用的模式m＝gj；

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

即：

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

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

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

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

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

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

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

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

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

步骤H7：获得所有任务完成时间fj；计算其适应度值fit，操作结束；

步骤12：从当代种群和新种群中从优到劣选出N个不同的个体形成新的当代种群；

步骤13：判断是否满足第二阶段进化终止条件，如满足，则转到步骤14，否则转到步骤

10；

第二阶段终止条件为迭代到指定的代数TG2或连续迭代GG2代最优个体没有改进；

步骤14：如果当代种群中的最优个体为可行个体，那么输出最优个体对应的调度方案，及其项目执行时间 否则该问题无可行调度方案。

2.根据权利要求1所述的一种采用两阶段遗传算法的多模资源受限项目调度优化方法，其特征在于：所述适应度值fit的具体计算方法如下：如果个体为不可行个体，即存在一个不可更新资源l满足 那么令个体的适应度值fit＝lf+ms，否则令个体适应度值fit＝ms，其中：nj,gj,l表示任务j在模式gj下执行时需要的不可更新资源l的数量，为项目执行时间，PRJ+1是任务J+1的父任务集；

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

3.根据权利要求1所述的一种采用两阶段遗传算法的多模资源受限项目调度优化方法，其特征在于：所述步骤C1、E1中基于排序的轮赌法从当代种群中随机选择两个不同个体作为父体1和父体2的具体步骤如下：步骤I1：对当代种群中的个体按优到劣进行排序，获得个体n的排序值rkn，n＝1,…,N，其中排第一的其取1，排第二的其取2，以此类推，排最后一名的其取N；

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

步骤I3：计算累计概率： n＝1,…,N；

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

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

步骤I6：个体选择操作结束。