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

资源受限项目调度问题综述 摘要 针对资源受限项目调度问题，总结国内外项目调度的发展过程及研究成果。在对问题的类型进行分类的基础上，结合大量文献对常见的算法进行描述并重点介绍了关键技术的研究状况。进一步地，将资源受限项目调度问题做进一步的拓展，简略介绍多目标、多项目、任务可拆分的项目调度问题。最后对问题进行总结，并提出自己的看法。 0 引言 现代项目越来越趋于大型化、复杂化，要求工期更短、成本更低。再加上行业细分越来越发达这种新情况给项目管理带来了更高的要求。如何在更短时间内、在保证质量的前提下，以更低的成本完成项目，成为项目管理人员关心的问题。在项目运作过程中，资源受限项目调度问题RCPSP(resource-constrained project scheduling problem)是一个重要的优化问题，它是最常见的生产调度问题，是项目管理中最为经典和核心的问题之一 项目调度发展过程 项目调度问题自20世纪中期被提出来，传统的计划技术有甘特图（又称横道图，Gant Chart,Gc）、关键活动图、网络计划技术。几种典型的网络计划技术有：关键路径发（Critical Path Method,CPM）、项目计划评审技术（Program Evaluation and Review Technique,PERT）、优先图方法（PDM）、图解评审技术（Graphical Evaluation and Review,GERT）、风险评审技术（Venture Evaluation and Review Technique,VERT）. 最初被广泛应用于项目进度计划的工具是甘特图技术，它用二维坐标的形式，用线条在二维空间中表似乎出整个项目期间计划和实际的活动完成情况，直观表明项目中所含各项活动的执行顺序，以及每项活动的开始/结束时间和持续时间。该方法形象直观，易于掌握，但是不能体现工作间的相互依赖关系，不能体现工作过早开始或者过完开始所造成的后果。 20世纪50年代中期发展起来的网络计划技术迅速渗透到项目调度领域，以网络图的形式来表示项目进度计划。它能明确反映各活动时间的先后顺序和相互制约的逻辑关系，通过计算时间参数，可找出计划中的关键活动及关键路线，反映出各活动的时差。其思想是通过压缩关键工作路线的持续时间，从而使工程的工期、费用实现优化。 具有代表性的是关键路径法与计划评审技术。两种方法都是采用平面网络结构表示项目的工作细分结构，很好的反映了项目组成各工作之间的时序依赖关系。二者的却别在于对项目各工作的执行时间的估计方法。关键路径发采用一点估计法，直接根据历史数据和以往经验给出唯一的估计值，不考虑不确定性因素。这种方法可能会造成与项目实际情况的较大偏差。评审技术进行了一定的改进，采用三点估计法，即以经验丰富的项目管理者所掌握的完成一项工作所需要的可能最少时间、可能最多时间及最大可能时间为基础，来得到估计执行时间。通过数理统计的基本理论，对项目进度进行了定量分析，能够得到较高的计划。但是这两种方法有一个共同的缺点，就是没有考虑资源约束，这与实际情况不符合，由此便产生了资源受限项目调度问题。 资源受限项目调度问题研究现状 2.1资源受限项目调度问题描述 任何项目的策划和执行都包含大量不同的活动及各种人力、物力资源。在项目活动的组织安排总，有些活动是可以同时进行的，有些活动则是必须在其他若干活动完成之后才能进行的。同时，每项活动本身还需要一定的持续时间，且使用不同类、不同数量的资源如机器设备、物资材料、劳动力等。资源是项目执行过程中不可缺少的重要组成部分，而这些资源的有效可用量往往具有局限。如何以最佳方式安排执行项目中的各个活动，以使其顺利完成，就构成了资源受限项目调度问题的基本概念。 黄敏镁、江涛将这一概念描述为：“项目由一系列相互关联的活动构成，整个项目的结构由一张AON（activity-on-node）有向网络图表述。RCPSP的调度决策需要同时满足项目活动之间的时序约束和资源约束。RCPSP的解是在满足时序约束和资源约束条件下产生的一种使某些管理目标最优化的调度，即每个活动何时开始及采用何资源或执行模式。 刘秋莲将一般的资源受限的工程调度问题描述如下:在一个(或多个)工程中，包含 着很多相互关联(满足紧前关系)的工作，每项工作的完成需要一定数量的资源并 有一定的工期，在工程的每一个阶段都可能有多个工作竞争同一种有限的资源， 问题是如何分配这些资源才能实现最优的管理目标?这些目标可能是:工程的工 期最短，工程拖期最少，工程拖期惩罚最小，工程的净收益最大等。 总而言之， RCPSP问题是研究具有优先关系约束活动的项目在资源受限的条件下使某些管理目标最优的调度问题 2.2资源受限项目调度问题研究内容 2.2.1RCPSP 的