资源受限项目调度问题文献综述

1、资源受限项目调度问题综述摘要针对资源受限项目调度问题，总结国内外项目调度的发展过程及研究成果。在对问题的类型进行分类的基础上，结合大量文献对常见的算法进行描述并重点介绍了关键技术的研究状况。进一步地，将资源受限项目调度问题做进一步的拓展，简略介绍多目标、多项目、任务可拆分的项目调度问题。最后对问题进行总结，并提出自己的看法。0 引言现代项目越来越趋于大型化、复杂化，要求工期更短、成本更低。再加上行业细分越来越发达这种新情况给项目管理带来了更高的要求。如何在更短时间内、在保证质量的前提下，以更低的成本完成项目，成为项目管理人员关心的问题。在项目运作过程中，资源受限项目调度问题RCPSP(reso

2、urce-constrained project scheduling problem)是一个重要的优化问题，它是最常见的生产调度问题，是项目管理中最为经典和核心的问题之一1 项目调度发展过程项目调度问题自20世纪中期被提出来，传统的计划技术有甘特图（又称横道图，Gant Chart,Gc）、关键活动图、网络计划技术。几种典型的网络计划技术有：关键路径发（Critical Path Method,CPM）、项目计划评审技术（Program Evaluation and Review Technique,PERT）、优先图方法（PDM）、图解评审技术（Graphical Evaluation a

3、nd Review,GERT）、风险评审技术（Venture Evaluation and Review Technique,VERT）.最初被广泛应用于项目进度计划的工具是甘特图技术，它用二维坐标的形式，用线条在二维空间中表似乎出整个项目期间计划和实际的活动完成情况，直观表明项目中所含各项活动的执行顺序，以及每项活动的开始/结束时间和持续时间。该方法形象直观，易于掌握，但是不能体现工作间的相互依赖关系，不能体现工作过早开始或者过完开始所造成的后果。 20世纪50年代中期发展起来的网络计划技术迅速渗透到项目调度领域，以网络图的形式来表示项目进度计划。它能明确反映各活动时间的先后顺序和相互制约的

4、逻辑关系，通过计算时间参数，可找出计划中的关键活动及关键路线，反映出各活动的时差。其思想是通过压缩关键工作路线的持续时间，从而使工程的工期、费用实现优化。具有代表性的是关键路径法与计划评审技术。两种方法都是采用平面网络结构表示项目的工作细分结构，很好的反映了项目组成各工作之间的时序依赖关系。二者的却别在于对项目各工作的执行时间的估计方法。关键路径发采用一点估计法，直接根据历史数据和以往经验给出唯一的估计值，不考虑不确定性因素。这种方法可能会造成与项目实际情况的较大偏差。评审技术进行了一定的改进，采用三点估计法，即以经验丰富的项目管理者所掌握的完成一项工作所需要的可能最少时间、可能最多时间及最大

5、可能时间为基础，来得到估计执行时间。通过数理统计的基本理论，对项目进度进行了定量分析，能够得到较高的计划。但是这两种方法有一个共同的缺点，就是没有考虑资源约束，这与实际情况不符合，由此便产生了资源受限项目调度问题。2 资源受限项目调度问题研究现状2.1资源受限项目调度问题描述 任何项目的策划和执行都包含大量不同的活动及各种人力、物力资源。在项目活动的组织安排总，有些活动是可以同时进行的，有些活动则是必须在其他若干活动完成之后才能进行的。同时，每项活动本身还需要一定的持续时间，且使用不同类、不同数量的资源如机器设备、物资材料、劳动力等。资源是项目执行过程中不可缺少的重要组成部分，而这些资源的有效

6、可用量往往具有局限。如何以最佳方式安排执行项目中的各个活动，以使其顺利完成，就构成了资源受限项目调度问题的基本概念。黄敏镁、江涛将这一概念描述为：“项目由一系列相互关联的活动构成，整个项目的结构由一张AON（activity-on-node）有向网络图表述。RCPSP的调度决策需要同时满足项目活动之间的时序约束和资源约束。RCPSP的解是在满足时序约束和资源约束条件下产生的一种使某些管理目标最优化的调度，即每个活动何时开始及采用何资源或执行模式。刘秋莲将一般的资源受限的工程调度问题描述如下:在一个(或多个)工程中，包含 着很多相互关联(满足紧前关系)的工作，每项工作的完成需要一定数量的资源并

7、有一定的工期，在工程的每一个阶段都可能有多个工作竞争同一种有限的资源， 问题是如何分配这些资源才能实现最优的管理目标?这些目标可能是:工程的工 期最短，工程拖期最少，工程拖期惩罚最小，工程的净收益最大等。总而言之， RCPSP问题是研究具有优先关系约束活动的项目在资源受限的条件下使某些管理目标最优的调度问题2.2资源受限项目调度问题研究内容2.2.1RCPSP 的类型自从资源首先项目调度问题提出以来，已经出现了种类繁多的RCPSP问题。辛润勤按照以下几个方面对资源受限项目调度问题进行分类2.2.1.1根据项目调度目标分类（1）最小化项目工期：（3）最大化项目净现值（4）资源均衡问题2.2.1.

8、2根据资源类型分类3 非可再生资源：资源的可使用量在整个项目工期内具有约束，一旦消耗完就不能再生。（2）可再生资源：资源的可使用量在项目中每一阶段内受到约束，某阶段的数量有限，但使用之后被释放可以再生。（3）双重资源约束：资源的可使用量既在整个项目工期内具有约束，而且在项目工期中的每个时间段内受到约束。2.2.1.3按照模型的不同分类（1）单执行模式资源约束项目调度问题：每项活动只有一种执行模式，消耗一定的资源在一个给定的加工时间内完成。（2）多执行模式资源约束项目调度问题： 运行活动可以以多种执行模式之一进行操作，每种执行模式对应一种资源组合和相应的活动执行时间。2.2.2资源受限项目调度问

9、题求解方法研究资源受限的工程调度问题在现代企业中显示出越来越重要的研究价值。随着最优化技术的不断发展，国内外学者陆续提出了一系列性能优良的优化算法，并将这些算法应用于解决项目调度问题。刘士新等根据收集到的资料，对这些算法进行归纳并概述。2.2.2.1算法概述解决资源受限项目调度这类问题的方法可以分为两类，一是致力于取得最优解的精确算法，另一类就是启发式算法。常用于求解RCPSP 的主要精确算法有线性规划（linear programming）和分枝限界法(branch and bound).精确算法的研究主要是集中在利用数学规划问题来对项目调度进行公式化的求解，这类算法虽然在某些程度上能够得到

10、精确解甚至是最优解，但它只能解决中小项目的调度。随着问题规模的扩大，确定性算法的求解时间将以指数级的速度增加。因此启发式算法求解RCPSP。何正文等在“求解资源约束项目调度问题的启发式算法综述”一文中，阐述了求解RCPSP的启发式算法。首先在对各种优先权规则进行归纳的基础上 ,概述基于优先权规则的RCPSP 启发式算法研究现状;其次,综述项目进度的表述方式及常用超启发式策略,汇总求解 RCPSP 的 超启发式的研究成果。l 基于优先权规则的启发式算法基于不同的优先权规则从可安排活动集合中选择活动 ,从而将部分进度扩展为满意的完全进度。常用的优先权规则主要有以下几种：最大分级位置权重规则、最迟完

11、成时间规则、最多紧后活动规则、最迟开始时间规则、最小松弛规则。同时还扩展出多通道算法，如：多重优先权规则启发式算法、前向-后向进度安排启发式算法、抽样性启发式算法、适应性启发式算法等等。l 超启发式算法该类算法将项目进度表述为一组编码，利用超启发式策略对编码进行搜索优选后，再转化为进度安排。进度安排常用的表述方式有活动列表、随机键、转移向量、进度设计、直接表述。文中总结出求解RCPSP常用的启发式策略有模拟退火、禁忌搜索、遗传算法和等等。模拟退火：从某个初始解开始 ,一个邻点通过对当前解的扩展来生成。如果邻 点好于当前解则被接受;否则,它以一定的概率被接受 ,接受概率依赖于该解变坏的程度以及当

12、前的温度参数。随着算法的进行 ,温度被逐步降低以减小接受坏的邻点的概率。达到规定的温度后算法终止 ,最后 固定下来的解即为满意解。 禁忌搜索：对于所有邻点解进行评价并选择其中最好的一个进行进一步的搜索。为了避免搜索返回刚刚离开的局部最优点而形成循环, 通过建立一个禁忌列表来限制向某些邻点的移动。这种禁忌状态在某种特定的条件下也可以被重新激活。 遗传算法：并行地考虑解的一个集合或群体, 在已生成的初始群体的基础上, 新的解通过交叉和/ 或变异操作来获得。在新解生成后, 适应度 通常用所求解问题的目标函数来表示最高的解“生存”下来构成下一代, 而其余的解通过所谓的选择机制被淘汰, 从而使解的质量不

13、断得 到改善。 同时还提出了其他类型的启发式算法如蚁群算法、可变邻点搜索技术等等。结合其他学者的观点，超启发式算法被普遍认为是在性能、可扩展性和易于实现性等方面权衡后的最佳方法。是目前学者们研究资源受限项目调度问题最常用的方法另外，以色列学者高德拉特将约束理论（Theory of Constraint,TOC）应用于项目管理领域，提出了基于关键链的项目管理理论，从中发展出一种新的项目调度理论：基于关键链的项目调度理论2.2.2.2启发式算法在RCPSP问题中的应用下面首先基于一些比较典型的超启发式算法（遗传算法、蚁群算法、模拟退火）模型以及关键链法结合一些文献进行整理和综述，并提出自己的看法。

14、2.2.2.2.1遗传算法遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。资源受限项目调度求解的是工期最小、净现值最大等一些最优解，所以可以运用遗传算法来求解。ü 基于遗传算法的资源约束型项目调度优化 杨利宏等基于遗传算法，着重讨论优化资源有限工期最短问题。该优化过程是在多资源约束下，通过检索随机生成的活动调度筛选出资源约束下最小工期的调度方式。最后通过某公司的电脑横机研发项目为研究对象，针对多资源约束的项目计划和调度问题，采用遗传算法优化项目的调度方法。整个遗传算法的流程

15、如下图所示。在进行优化计算前，首先完成从搜索空间到遗传空间的转换，进行两方面的工作：（1）将目标函数转换成适度函数，即将最小值问题通过比例运算转化成最大值问题。（2）染色体编码，通过基于随机优先权把实际的AON网络转换成项目活动的调度。根据适应度函数，计算适度值。接下去是在遗传空间上进行选择、交叉、变异，知道找到最优解。选择：在这基础上，根据计算出来的适度值，采用轮盘赌操作进行选择，选择出需要繁殖的父代群体。这个过程就是“选择操作”交叉：本文采用两点交叉的运算模式，为了不产生重码，文中提出了基于位置映射关系的两点交叉。既可以保证不重复，也可以很好地保证个体的继承性。变异：采用基于中心位置的变异

16、。分为四步：计算变异基因的个数U、生成U个随机数作为基因的变异、定位到相关的染色体、采用中心位置变异的方法，随机与本染色体内的其他等位基因调换数值，从而生成新的染色体。 作者将该方法实际应用到企业生产中，并取得了一定的成果，从而证明了运用遗传算法进行项目调度优化的可行性。他的优点在于采用启发式群体随机搜索的方法，在搜索的过程中不易陷入局部最优。但是其缺陷是局部搜索能力较差并容易早熟收敛。一种求解资源受限项目调度的遗传算法杜焱、彭武良在文中求解使用可更新资源的单模式资源受限项目调度问题的遗传算法。同样是求解最小化的项目工期。在继承了基于排列和基于优先级的编码方案的优点，提出了一种新的基于优先权排

17、列的编码方案。采用了串行调度方法生成项目计划。文中解释了遗传算法的思想。把问题的解表示成“染色体”在执行进化之前，给出一群“染色体”，即种群。然后，按照适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代。这样一代一代进化，就会收敛到最适应环境的一个染色体。就是问题的最优解。较之于杨利宏等10在对于遗传算法在项目调度中的应用，本文的亮点在于提出了一种新的基于优先权的编码方案。染色体中包含两种信息：位置和值。这种方法保留了基于优先权编码的优点，同时这种方法可以达到搜索空间更小的目的。在解码方案中，采用了基于串行调度算法进行对染色体的解码并生产项目计

18、划。调度过程被分为n 个阶段，每个阶段只调度一个活动，并包含了已调度集和决策集。在解码过程中，需要从决策集中选择活动，优先权值较高的活动将优先被选择，并得到更早的调度。ü 运用遗传算法优化项目中现金流问题的研究 前面提到的算法的应用都是为了解决工期最小化问题。但是在实际生产过程，往往会伴随着现今的流入和流出，现金流的净现值很多时候都更能够真实地反映企业的盈利状况。徐柏群等将遗传算法运用到现金流的优化问题上。考虑到项目的间接费用与奖惩机制，给出了模型的形式化描述，还讨论了里程碑事件支付和相等事件间隔支付两种常见的支付模式。并通过数值进行不同支付模式的调度结果的比较。本文采用的遗传算法的

19、流程大体如下图所示：这个流程与杨利宏，杨东10利用遗传算法解决工期最小化问题的最主要区别在于不用进行从搜索空间到遗传空间的转换。这是由于现金流中解决的是最大值问题，而在遗传算法中能保持良好生存能力的个体是适应度大的个体，本身就是一个最大值问题文中交叉算子采用的是MCUOX,优点是染色体经过交叉后仍能保持优先关系的约束。变异操作包含了针对活动的变异和针对模式的变异。在调度方面，文中给出对于一个给定的可调度的基因序列，在计算该染色体的适应值之前，应该先对染色体上的活动进行调度，计算各活动的开始执行时间、结束时间以及AOA活动图中各事件的发生时间。从而由目标函数确定适度值函数：式中：当前种群中第i个

20、染色体的适应值；该染色体的目标函数值；当前种群最小的目标函数值。文中还通过实验算例得出了一些结论：（1）PEO和ETI两种支付模型的比较。二者的差别主要在于PEO模式下的支付在给定的一组里程碑事件上，而在ETI模式下则每相等时间间隔发生一次支付。由于现金具有时间价值，PEO模式下的调度方案往往会使支付时间提前。两种模式生成的最优调度一般都具有早期支付行为涉及的支付量较大，后期支付行为的支付量相对较小的特点。（2）奖惩机制的作用分析：算例中得出，由于奖惩机制的左右，项目的平均工期都比没有奖惩机制下的要短，很多还能提前完工获得奖励。（3）遗传算法的有效性分析：在对各个算例分别进行的50 次实验中，

21、遗传算法所得到的NPV最优值的平均值远大于随机搜索算法在所有测试中所能得到的最大NPV，并且性能差距随着实例规模的扩大而进一步增大。ü 遗传、模拟退火算法结合喻小光等提出：遗传算法是一种较易避免陷入局部最小的并行搜索，但是局部搜索能力较差并容易早熟收敛是其致命的弱点。相反的，模拟退火是一种具有很强的搜索能力并以稳定的速度收敛的局部搜索技术。基于此，在“应用遗传模拟退火算法实现资源受限项目调度”一文中，他们将模拟退火嵌入遗传算法中，提出了“遗传模拟退火算法（Genetic Simulated Annealing Algorithm,GSA ）.GSA继承了二者的优点，因此在文中提出了一

22、种基于GSA的混合元启发式方法RCPSPGSA用于解决以最小化项目工期为目标的RCPSP.该算法的大体框架如下：初始化算法参数产生初始种群评估初始种群，令Best=当前最优解，K=0如果终止条件满足，调入11（终止条件为：进化迭代次数达到预设值或最优解持续N次迭代没有发生改变）选择、交叉、变异操作产生具有种群个体数量个个体的临时下代种群，该种群中个体将作为SA的初始解。计算、更新Best.使用固定步长SA改进临时下代种群中的每个个体。更新Best令K=K+1,t=t,转入4（是退温速率） 本文通过数值实验分析，引入正交实验分析法解决参数组合选择问题。实验的结果证明该方法选择的参数组合具有突出的

23、性能。但是该方法的一个缺点是比较耗时，所以将来主要着眼于提高RCPSPGSA的时间性能。2.2.2.2.2蚁群算法(ACO)蚁群算法是超启发式算法中常用来解决RCPSP的一类算法。Ø 基于蚁群优化算法的资源受限项目调度的问题研究”焦超在文中对几种重要的求解RCPSP的方法进行了比较，总结概括蚁群算法的演技现状及应用领域，讨论了该算法用于资源受限项目调度问题的基本思路。在此基础上设计了一种基于蚁群优化算法的单执行模式资源受限项目调度问题优化算法。作者在阐述蚁群优化算法的基本思想之前，总结昆虫学家的一个发现：自然界的蚂蚁能在没有任何可见提示下找出从蚁穴出发到食物源的最短路径。在此过程中，

24、蚂蚁会分泌一种化学物质信息素。这种信息素遗留在蚂蚁走过的路径上，为其他蚂蚁指引移动方向。蚂蚁总是趋向于向信息素强度高的方向移动。从而经过蚂蚁多的路径对后来的蚂蚁越有吸引力。这一路径的过程被成为蚂蚁的自催化行为。 ACO的基本思想就是通过构造具有类似真是蚁群寻径特点的人工蚁群来实现对解空间的搜索，最终在正反馈的作用下集中到最优解上。文中就ACO指出其缺点在于信息素缺乏，进化速度慢，在解决较大规模时候很难在可接受的计算成本和时间内找到最优解。因此作者又介绍了几种改进算法如：a) 带精英策略的蚂蚁系统使蚂蚁系统在较短时间内找出优化解b) 蚁群系统采用了能反映问题特点的状态转移规则 采用了效率更高的全

25、局更新规则 引入新的信息素更新方式c) 最大最小蚂蚁系统d) 蚁群算法与其他优化算法的融合。比较有代表性的有ACO与GA的结合、ACO与免疫算法的结合等等。在前面有提到遗传算法与模拟退火结合来解决资源受限项目调度问题，算法的结合使用也是将来RCPSP研究的一个方面，可以结合多方面的优点提出更优的解法。在将蚁群算法应用到RCPSP问题中时，作者认为需要解决两个关键问题，一是构建既适合算法需要、又能反映问题特征的蚂蚁巡游路径；二是选择恰当的信息选策略。蚁群算法的流程如下：所有人工蚂蚁从工作1出发开始搜索过程。通过反复应用状态转移规则并在满足资源约束的最早时刻调度下一工作构建项目调度计划，知道项目收

26、尾工作。在搜索过程有两次信息更新，局部更新和全局更新。局部更新使路径上的信息素不断挥发，有利用探索新解，扩大对解空间的搜索。全局更新体现了最优路径保持策略。进一步的，文中根据正交法设计实验，并采用项目调度标准问题库中的基准问题进行试验，证明了算法的有效性，并通过对计算结果的分析得到了算法的优化解参数设置。综观全文，运用蚁群算法的优越性在于其不对问题的数学特性作具体的要求。求解的速度较快。但是文中并没有就信息素和启发式信息策略较好的联系起来。接下来的探索应该放提高在更能反映RCPSP特征的信息素和启发式信息策略的算法性能。Ø 蚁群算法应用到以现金流最大化为目标的项目调度问题，刘秋莲在文

27、中以优化现金流为目标，对多模式资源约束型折现流时间-费用权衡项目问题进行调度（MRCTCTPDF），首次将蚁群算法成功用于工程项目的现金流优化。在设计了新的蚁群算法构建方法和基于现金流净现值的启发式，同时充分考虑了活动的优先关系、资源约束、项目执行过程中的各项资金流以及资金的时间价值因素，使项目的净现值最大化比较真是全面反映了工程项目进行过程中的现金流状况。 基于MRCTCTPDF的特点，建立出非线性整数规划模型，要求收益最大，从而确定目标函数。在此基础上，确定算法。算法主要由两个嵌套循环组成，内循环是让每只蚂蚁从一个活动移动到另外一个活动，外循环是让每只蚂蚁完成一趟遍历之后重新开始新的遍历。

28、框架如下： 当蚂蚁遍历完所有的活动后，根据目标函数，对这次遍历计算净现值，每次新的遍历得到新的NPV后都要与之前得到的最优解比较，保留大者。本文将蚁群算法应用到项目调度现金流最大化的问题中，是对蚁群算法应用领域的一个拓展。蚁群算法在工程项目现金流优化方面具有很强的优势。体现在：其全局收敛、并行性、不对问题的数学特性作具体要求、求解速度快，已经在以最短工期为目标的RCPSP中取得成功。同时蚁群算法属于构建性算法，算法的解是通过启发式逐步生成的，这与现金流贯穿整个项目过程的特性相同。本文的不足之处在于蚁群算法的表现对于参数设置十分敏感，但是文中并没有找到有效的方法来解决参数设置的问题。只是根据经验

29、和反复实验来获得参数。这方面也是将来研究中重点考虑的问题。2.2.2.2.3关键链法关键链方法是在约束理论基础上发展起来的一种项目进度计划技术，作为一种全新的项目管理哲学，已经引起众多学者的关注和探索。以下集中介绍各文献中从不同角度对关键链在项目计划调度方面的研究。ü 关键链项目计划调度方法研究张静文等首先介绍关键链近五年的研究概况，其次从多个角度阐述关键链对传统项目计划调度方法CPM/PERT的改进之处，最后提出确定输入缓冲量最小值的方法。文中总结关键链对CPM/PERT的改进之处在于以下几点：（1）对资源的看法不同。CPM/PERT假定资源供给无限，因而安排项目仅考虑活动时间的优

30、先关系约束。现实中资源总是稀缺的，关键链技术最大改进之处就是考虑到资源的有限性，活动的安排受到优先关系和资源约束的双重限制。（2） 对人行为特征的认识不同。CPM/PERT从纯技术性角度追求计划的科学性及完美性，忽视人心理因素对项目进度所产生的影响，体现为CPM估计的活动工期中包含大量安排富余时间，在“学生综合症”的影响下，又浪费了原本的富余时间。关键链方法考虑到上述人的行为特征，以活动50%的CPM时间作为其估计的执行时间来安排项目进度计划，有效避免“学生综合症”。（3）对风险的态度不同。CPM/PERT以90%甚至更大的概率估计活动工期，蕴含的风险极小，导致了收益小。关键链方法以50%的可

31、能完成时间作为估计的活动执行时间，同时通过设置项目缓冲、汇入缓冲以及资源缓冲将项目不确定因素在项目系统内部“消化”。所以关键链是站在全局角度考虑项目执行的风险，而非仅仅考虑单个活动的风险。（4）在网络图中的表现形式不同。关键路径是一条从起始节点到终止节点的通路，路径不止一条。而关键链是考虑活动逻辑关系和资源冲突后制约整个项目周期的一个工作序列，往往不是一条通路。（5）确定过程不同。CP一次即可确定，而确定关键链是一个循环往复，不断优化的过程。当资源限量变化时，关键链需要重新确定。 在关键链中缓冲区的确定，作者的见解独到。目前缓冲区尺寸的确定都可以认为是最大值，本文提出了存在缓冲区尺寸最小值的说

32、法。归结起来，即项目缓冲最小值可以是0，但是对于输入缓冲来说，即使所有非关键工序均无拖延，由于工序间逻辑关系及资源冲突，输入缓冲的最小值也不能为0.文中举例说明了这一点。得出的结论是最小输入缓冲由PB=0时项目的最优调度计划确定，各条非关键链的最小缓冲值在最优调度计划时整条非关键链的浮动时差。实际中，项目进度通常居于最大值和最小值之间。由此编制的项目进度计划不是一个确定的时间点计划，而是一个进度区间计划，保证了编制的进度计划具有应付不确定环境的柔性。如下图所示：ü 关键链技术在RCPSP问题中的应用研究韩文民，龚悄巧采用遗传算法，提出一种关键链的识别方法，得到一条近优的关键链。在项目

33、缓冲的设置方面，既考虑了关键链自身的因素，又考虑非关键链对其影响。通过对资源受限项目调度问题的典型案例求解，较为详尽地描述了方法的具体应用过程。 文中指出现有的识别关键链算法常为启发式算法，其缺点在于难以处理大规模问题而且效率低。所以本文采用了遗传算法进行关键链的识别。具体步骤可以用以下的流程图来表示。使用遗传算法来确定关键链，文中对比研究发现该方法能更好的降低项目周期，具有更好的实用性。在对于缓冲的数量确定，提到目前的缓冲量的设置方法都将汇入缓冲和、项目缓冲分别对待，但是作者认为二者是有密切的联系的。一旦某汇入缓冲不足以抵消该非关键链带来的延误影响，则此时这种影响最终还是由项目缓冲来消解。所

34、以根据中心极限定律，每条链路的实际执行时间可以视为服从正态分布：而缓冲量的大小设置于完工期望有关 ü 基于关键链的柔性资源受限项目调度问题研究罗荣桂等介绍了关键链法的基本思想。分别提到了约束理论、项目工期估计、缓冲区机制。接着在传统关键路径方法的基础上确定关键链。最后将关键链运用到柔性资源约束的项目调度中并通过实例求解。关于项目工期的估计，文中考虑到许多不确定性因素的存在，加入了大量的安全时间，采用低风险（90%概率完工）的估计时间。前面的阐述中，有提到采用90%完工率的估计时间其实会因为“学生综合征”的现象存在而浪费很多不必要的时间，这也是本文的一个缺点。对于缓冲区机制，按照风险聚

35、合原理引入的项目缓冲(PB)、汇入缓冲(FB)及资源缓冲(RB)。CCM将关键链活动的安全储备以PB的形式转移到关键链之后，在任何非关键链与关键链处加入汇入缓冲FB。RB是一种虚活动，插入在需要关键资源的关键链任务之前。作者以关键路径的时间长度为目标，提出了一种确定关键链的改进方法。a) 确定项目网络图的关键路径b) 确定初始可行集c) 从可行集中安排关键路径上的活动d) 调动初始可行集的其他活动（考虑资源的供应和需求）e) 以最早完成的活动时刻为下一个决策点，确定新的可行集合，根据最早开始和最晚结束时间确定关键链本文中将这一方法运用到柔性资源约束的项目调度，主要考虑人力资源的柔性。提出在一定

36、的资源柔性度下，如何合理分配柔性资源使项目既满足工序先后约束又满足项目活动对不同资源技能的需求，并通过优化方法使项目的总工期 文中用此方法来解决具有柔性资源受限的项目调度问题，确实达到了优化项目工期的目的。但是，项目管理的实施是一个非常复杂的过程，需要考虑到不同的环境，以及项目运行的成本，风险问题，如何平衡这些不确定因素进行资源配置来优化系统的绩效将是研究的重点。2.2.2.2.4项目调度问题的拓展研究前面提到对于RCPSP的分类中，按目标可以分为项目工期最小化、现金流最大化以及资源均衡的项目调度。按模式可以分为单模式和双模式。在前面的阐述中，只涉及到在单执行模式下，以项目工期最小化、现金流最

37、大为目标的项目调度问题。实际上，很多学者在资源受限项目调度的更多方面都有不少的研究。下面就这些研究来对RCPSP问题进一步的阐述。RCPSP目标的研究单泪源等17在针对资源受限下的项目资源均衡问题的自身特点及其与传统资源受限项目调度问题的相似之处，设计了一种以优先值法作为粒子表达资源均衡问题的粒子群优化算法。在对资源受限的项目调度中资源均衡问题进行描述后，作者采用了资源需求量方差为指标，这一目标值越小，即均衡效果越好。基于此建立RLP的数学模型。 在将粒子群算法用来解决RLP 问题时，文中指出取优先值法来表达粒子的内容。粒子的每个维度代表一个活动的优先级大小。同时采用并行进度的生成机制。将RL

38、P转换成RCPSP的方式。算法可以在较少次数的迭代后找出最优解。 在一般的情况下，我们研究的都是实现单一目标的资源受限项目调度问题。那么，有可能对多目标资源受限项目进行调度吗？刘士新、宋健海19就设计了一种求解模糊多目标资源受限项目调度问题的遗传局域搜索(GLS)算法，目标就是生成近似有效解集，以便决策者在决策过程中有更多的选择。算法利用线性加权效用函数将多目标组合优化问题转换为单目标组合优化问题。通过系统的方法生成目标权系数向量，对于每次生成的权系数向量，调用GLS算法求解以极小化效用函数为单一目标的子问题，由此生成的近似有效解集更具有多样性。这是在考虑实际项目中，需要考虑的通常不仅仅是单一

39、的目标，应该要在工期、现金流、资源以及其他更多方面进行权衡，选择最佳的组合来完成项目。多目标的项目调度问题应该成为研究的重点。多项目的RCPSP问题研究 资源受限项目调度问题按照所研究的项目数目可以分为资源受限的单项目调度问题（rc-sPSP）和资源受限的多项目调度问题(rc-mPSP).对于单项目的研究，国内外学者已经取得很多的成果，相比之下，多项目的研究就较少。罗荣桂等19就国内外关于多项目调度问题的现状进行研究。这方面的研究中，有些学者试图用解决单项目的方法来求解多项目问题。成为“单项目” 方法。通过增加虚拟的源节点和尾节点来将多个单项目人工连接成一个大项目。求解多项目调度问题的启发式算

40、法大部分可以归结为基于优先规则的方法。而这些规则的效果则有很大的不同。文中举例说明了这点。在对于启发式进行改进后，提出了往复式的前向-后向调度算法，用于改进可行解。 遗传算法、模拟退火等元启发式算法在多项目调度中应用极少，有关学者提出帕累托模拟退火和日光束搜索方法来描述和量化资源受限的多个项目活动的交叉影 响,并取得了较好效果。 对于多项目的调度问题，作者认为有待深入研究的在于：单项目调度问题有一个公认的标准问题库 PSPL IB ( Kolisch and Sp recher , 1996 ) 和PSPL IB/ max ( Christop h Schwindt , 1998) , 因此各

41、类算法可以方便地进行相互比较 ,也可以与问题的最优解或已知最好解来进行比较 ,从而判断算法的优劣 1819 。对于 rcmPSP ,则缺乏这样公认的问题库 ,难以判断算法的优劣。rcmPSP 的问题库 ,将是今后的一个重要研究课。 RCPSP其他方面的研究此外，在单执行模式资源受限的工程调度问题的扩展下，刘士新等研究了多执行模式工程调度的优化算法。雒兴刚, 汪定伟 ,唐加福结合企业实际的项目调度，在任务不可拆分的经典资源受限项目调度问题的基础上针对任务可拆分的项目调度问题提出了总项目工期最短的数学模型。梁燕、金烨针对紧急事件调度的紧迫性特点，建立了一种基于资源约束的启发式项目调度方法，并将该方法与关键链法结合确定最终的调度方案。3、总结及展望3.1本文总结 作为项目管