多技能资源受限项目调度问题(Multi-Skill Resource Constrained Project Scheduling Problem,MS-RCPSPS)作为资源受限项目调度这一NP-hard问题的一个重要分支,项目调度方案除了满足资源约束及时序约束之外,对资源任务间的匹配关系也有严格要求。对该调度问题的研究旨在满足约束的前提下,对任务的开始时间及处理该任务的资源进行合理安排,从而实现完工时间最小化、延误时间最短、成本最低等目标。在经典项目调度问题中,任务处理时间通常被假设为固定不变的常数。然而,在制造系统及服务系统中,任务加工时间存在不确定性,它同时也是会对调度结果产生关键影响的因素,而恶化效应是其中一种十分重要且普遍的不确定性主观因素。带有恶化效应的调度问题中,任务的处理时间会随任务开始时间、处理顺序的变化而有所不同。就理论研究而言,具有恶化效应的多技能资源受限项目调度问题绝大多数属于NP-hard问题,并广泛存在于软件开发、建筑、飞机制造等各个领域。因此,为此类运用广泛、求解复杂的具有恶化效应的多技能资源受限项目调度问题设计求解质量高、运行速度快的优化算法具有重要的理论价值和现实意义。本文对一般线性恶化和阶跃恶化这两种恶化效应作用下的多技能资源受限项目调度问题进行了研究,并分析了问题的复杂性。由于问题的NP-hard特性,无法在多项式时间内获得问题的最优解。因此,在对问题及解结构特征进行分析的基础上,为问题的高效、高质量求解设计了启发式算法和智能优化算法。论文的主要工作及获得的主要结论如下:1.资源有限前提下具有一般线性恶化效应的单机调度问题最大任务完工时间的优化此单机问题作为其它加工环境的特例,对该模型的分析可帮助我们加深对问题内在性质及最优调度解的结构特征的认知。针对有限资源下具有一般线性恶化效应的单机调度问题,以最小化最大完工时间为优化方向,建立0-1混合整数规划模型,并证明该问题是NP-hard的。在对问题相关性质进行分析的基础上,基于调度解结构特征和对模型的特性分析提出了比率比较启发式方法RCA以及基于比率比较法的邻域搜索算法RCA-LS。通过对计算机产生的随机算例进行仿真分析以评估算法性能,结合LINGO精确求解器对小规模算例进行求解。算例仿真结果表明,所提出的RCA-LS算法能够匹配所有精确求解器求得的小规模算例最优解,并以极少的的时间成本获得明显优于RCA的调度结果。2.阶跃恶化效应作用下多技能资源受限项目调度问题项目工期与项目成本的优化作为有限资源下具有恶化效应的单机调度问题的更一般性问题,以项目成本及项目工期为优化目标,为阶跃恶化下的多技能资源受限项目调度问题建立0-1混合整数规划模型,同时证明了该问题属于NP-hard问题。在问题模型基础上,分析最优解结构及相关性质,设计了一种集成了四种邻域结构和一个扰动步骤的改进禁忌搜索算法ITS进行求解,算法初始解的生成手段为基于SLS优先调度规则的简单启发式算法。为了检验算法的有效性,通过两组算例进行了计算机仿真分析。其中一组为MS-RCPSP领域已有的标准算例,通过对比目前已有的一些前沿算法,证明了ITS在多技能资源受限项目调度相关问题求解时寻优的能力;另一组算例则是通过修改标准案例,使算例中的任务处理时间具有阶跃恶化效应,随机算例仿真结果同样证明了ITS算法相较于其他算法的优越性。3.交货期约束下具有阶跃恶化效应的多技能资源受限项目调度问题任务总延误时间的优化在安排任务资源的调度过程中,加入对各任务交货期的要求,以总延误时间为优化方向,针对所研究问题,建立其0-1混合整数规划模型,同时证明相关问题的NPhard性质。基于调度问题最优解的结构特征,设计了基于任务优先级别PL和修正交货期MDD的启发式算法PL-MDD,同时还提出一种结合局部搜索阶段的路径重连算法PR对问题进行求解。在标准算例基础上生成随机算例进行仿真试验,对算法性能进行评估,实验结果表明PR能够对交货期下考虑阶跃恶化效应的多技能资源受限项目调度问题进行有效求解。4.一般线性恶化效应作用下多技能资源受限项目调度问题项目工期的优化以最小化完工工期为调度目标,对一般线性恶化效应下的多技能资源受限项目调度问题进行讨论,建立其对应的0-1混合整数规划模型。为求解该NP-hard问题,提出了一种集成了探寻新的解空间的重组算子与加强搜索当前解空间的局部搜索算子的基于一般变邻域搜素的模因算法(GVNS-MA)。在算法设计过程中,为节省算法运行时间,在算法寻优搜寻过程中加入能够对解质量进行快速评估的REM机制。同样,通过两组数值算例对算法求解性能进行分析。此外,设计对照试验以分析构成算法的两个重要组成部分对算法总体性能所起的作用。实验结果表明,算法GVNS-MA求解已有标准算例的结果相较于目前文献中已有的其它算法性能表现十分卓越,针对所生成的考虑了一般线性恶化的随机算例而言,GVNS-MA依旧是极其高效且稳定的,其求解能力对惩罚时间取值范围并不敏感。本论文针对具有一般线性恶化和阶跃恶化效应的任务处理时间,结合多技能资源受限项目调度问题,分别考虑了以最小化项目工期、总延误时间和项目成本为优化方向的多种调度模型,分析调度最优解的相关性质,并针对各个具体问题分别设计了对应的调度算法。本文创新性地提出在多技能资源受限项目调度问题中集成任务处理时间的恶化效应,该研究拓展了调度领域的研究内容,为求解该类问题提供了更为丰富的求解思路及方法,有利于项目实际生产缩短工期、节约资源、提高经济效益,具有重要的实际意义。