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

资源受限项目调度问题综述摘要针对资源受限项目调度问题，总结国内外项目调度的发展过程及研究成果。在对问题的类型进行分类的基础上，结合大量文献对常见的算法进行描述并重点介绍了关键技术的研究状况。进一步地，将资源受限项目调度问题做进一步的拓展，简略介绍多目标、多项目、任务可拆分的项目调度问题。最后对问题进行总结，并提出自己的看法。0引言现代项目越来越趋于大型化、复杂化，要求工期更短、成本更低。再加上行业细分越来越发达这种新情况给项目管理带来了更高的要求。如何在更短时间内、在保证质量的前提下，以更低的成本完成项目，成为项目管理人员关心的问题。在项目运作过程中，资源受限项目调度问题RCPSP(resource-constrainedprojectschedulingproblem)是一个重要的优化问题，它是最常见的生产调度问题，是项目管理中最为经典和核心的问题之一1项目调度发展过程项目调度问题自20世纪中期被提出来，传统的计划技术有甘特图（又称横道图，GantChart,Gc）、关键活动图、网络计划技术。几种典型的网络计划技术有：关键路径发（CriticalPathMethod,CPM）、项目计划评审技术（ProgramEvaluationandReviewTechnique,PERT）、优先图方法（PDM）、图解评审技术（GraphicalEvaluationandReview,GERT）、风险评审技术（VentureEvaluationandReviewTechnique,VERT）.最初被广泛应用于项目进度计划的工具是甘特图技术，它用二维坐标的形式，用线条在二维空间中表似乎出整个项目期间计划和实际的活动完成情况，直观表明项目中所含各项活动的执行顺序，以及每项活动的开始/结束时间和持续时间。该方法形象直观，易于掌握，但是不能体现工作间的相互依赖关系，不能体现工作过早开始或者过完开始所造成的后果。20世纪50年代中期发展起来的网络计划技术迅速渗透到项目调度领域，以网络图的形式来表示项目进度计划。它能明确反映各活动时间的先后顺序和相互制约的逻辑关系，通过计算时间参数，可找出计划中的关键活动及关键路线，反映出各活动的时差。其思想是通过压缩关键工作路线的持续时间，从而使工程的工期、费用实现优化。具有代表性的是关键路径法与计划评审技术。两种方法都是采用平面网络结构表示项目的工作细分结构，很好的反映了项目组成各工作之间的时序依赖关系。二者的却别在于对项目各工作的执行时间的估计方法。关键路径发采用一点估计法，直接根据历史数据和以往经验给出唯一的估计值，不考虑不确定性因素。这种方法可能会造成与项目实际情况的较大偏差。评审技术进行了一定的改进，采用三点估计法，即以经验丰富的项目管理者所掌握的完成一项工作所需要的可能最少时间、可能最多时间及最大可能时间为基础，来得到估计执行时间。通过数理统计的基本理论，对项目进度进行了定量分析，能够得到较高的计划。但是这两种方法有一个共同的缺点，就是没有考虑资源约束，这与实际情况不符合，由此便产生了资源受限项目调度问题。2资源受限项目调度问题研究现状2.1资源受限项目调度问题描述任何项目的策划和执行都包含大量不同的活动及各种人力、物力资源。在项目活动的组织安排总，有些活动是可以同时进行的，有些活动则是必须在其他若干活动完成之后才能进行的。同时，每项活动本身还需要一定的持续时间，且使用不同类、不同数量的资源如机器设备、物资材料、劳动力等。资源是项目执行过程中不可缺少的重要组成部分，而这些资源的有效可用量往往具有局限。如何以最佳方式安排执行项目中的各个活动，以使其顺利完成，就构成了资源受限项目调度问题的基本概念。黄敏镁、江涛]1[将这一概念描述为：“项目由一系列相互关联的活动构成，整个项目的结构由一张AON（activity-on-node）有向网络图表述。RCPSP的调度决策需要同时满足项目活动之间的时序约束和资源约束。RCPSP的解是在满足时序约束和资源约束条件下产生的一种使某些管理目标最优化的调度，即每个活动何时开始及采用何资源或执行模式。刘秋莲[2]将一般的资源受限的工程调度问题描述如下:在一个(或多个)工程中，包含着很多相互关联(满足紧前关系)的工作，每项工作的完成需要一定数量的资源并有一定的工期，在工程的每一个阶段都可能有多个工作竞争同一种有限的资源，问题是如何分配这些资源才能实现最优的管理目标?这些目标可能是:工程的工期最短，工程拖期最少，工程拖期惩罚最小，工程的净收益最大等。总而言之，RCPSP问题是研究具有优先关系约束活动的项目在资源受限的条件下使某些管理目标最优的调度问题2.2资源受限项目调度问题研究内容2.2.1RCPSP的类型自从资源首先项目调度问题提出以来，已经出现了种类繁多的RCPSP问题。辛润勤[2]按照以下几个方面对资源受限项目调度问题进行分类2.2.1.1根据项目调度目标分类（1）最小化项目工期：（3）最大化项目净现值（4）资源均衡问题2.2.1.2根据资源类型分类（1）非可再生资源：资源的可使用量在整个项目工期内具有约束，一旦消耗完就不能再生。（2）可再生资源：资源的可使用量在项目中每一阶段内受到约束，某阶段的数量有限，但使用之后被释放可以再生。（3）双重资源约束：资源的可使用量既在整个项目工期内具有约束，而且在项目工期中的每个时间段内受到约束。2.2.1.3按照模型的不同分类（1）单执行模式资源约束项目调度问题：每项活动只有一种执行模式，消耗一定的资源在一个给定的加工时间内完成。（2）多执行模式资源约束项目调度问题：运行活动可以以多种执行模式之一进行操作，每种执行模式对应一种资源组合和相应的活动执行时间。2.2.2资源受限项目调度问题求解方法研究资源受限的工程调度问题在现代企业中显示出越来越重要的研究价值。随着最优化技术的不断发展，国内外学者陆续提出了一系列性能优良的优化算法，并将这些算法应用于解决项目调度问题。刘士新等]3[根据收集到的资料，对这些算法进行归纳并概述。2.2.2.1算法概述解决资源受限项目调度这类问题的方法可以分为两类，一是致力于取得最优解的精确算法，另一类就是启发式算法。常用于求解RCPSP的主要精确算法有线性规划（linearprogramming）和分枝限界法(branchandbound).精确算法的研究主要是集中在利用数学规划问题来对项目调度进行公式化的求解，这类算法虽然在某些程度上能够得到精确解甚至是最优解，但它只能解决中小项目的调度。随着问题规模的扩大，确定性算法的求解时间将以指数级的速度增加。因此启发式算法求解RCPSP。何正文等[4]在“求解资源约束项目调度问题的启发式算法综述”一文中，阐述了求解RCPSP的启发式算法。首先在对各种优先权规则进行归纳的基础上,概述基于优先权规则的RCPSP启发式算法研究现状;其次,综述项目进度的表述方式及常用超启发式策略,汇总求解RCPSP的超启发式的研究成果。基于优先权规则的启发式算法基于不同的优先权规则从可安排活动集合中选择活动,从而将部分进度扩展为满意的完全进度。常用的优先权规则主要有以下几种：最大分级位置权重规则、最迟完成时间规则、最多紧后活动规则、最迟开始时间规则、最小松弛规则。同时还扩展出多通道算法，如：多重优先权规则启发式算法、前向-后向进度安排启发式算法、抽样性启发式算法、适应性启发式算法等等。超启发式算法该类算法将项目进度表述为一组编码，利用超启发式策略对编码进行搜索优选后，再转化为进度安排。进度安排常用的表述方式有活动列表、随机键、转移向量、进度设计、直接表述。文中总结出求解RCPSP常用的启发式策略有模拟退火、禁忌搜索、遗传算法和等等。①模拟退火：从某个初始解开始,一个邻点通过对当前解的扩展来生成。如果邻点好于当前解则被接受;否则,它以一定的概率被接受,接受概率依赖于该解变坏的程度以及当前的温度参数。随着算法的进行,温度被逐步降低以减小接受坏的邻点的概率。达到规定的温度后算法终止,最后固定下来的解即为满意解。②禁忌搜索：对于所有邻点解进行评价并选择其中最好的一个进行进一步的搜索。为了避免搜索返回刚刚离开的局部最优点而形成循环,通过建立一个禁忌列表来限制向某些邻点的移动。这种禁忌状态在某种特定的条件下也可以被重新激活。③遗传算法：并行地考虑解的一个集合或群体,在已生成的初始群体的基础上,新的解通过交叉和/或变异操作来获得。在新解生成后,适应度通常用所求解问题的目标函数来表示最高的解“生存”下来构成下一代,而其余的解通过所谓的选择机制被淘汰,从而使解的质量不断得到改善。同时还提出了其他类型的启发式算法如蚁群算法、可变邻点搜索技术等等。结合其他学者的观点，超启发式算法被普遍认为是在性能、可扩展性和易于实现性等方面权衡后的最佳方法。是目前学者们研究资源受限项目调度问题最常用的方法另外，以色列学者高德拉特将约束理论（TheoryofConstraint,TOC）应用于项目管理领域，提出了基于关键链的项目管理理论，从中发展出一种新的项目调度理论：基于关键链的项目调度理论]5[2.2.2.2启发式算法在RCPSP问题中的应用下面首先基于一些比较典型的超启发式算法（遗传算法、蚁群算法、模拟退火）模型以及关键链法结合一些文献进行整理和综述，并提出自己的看法。2.2.2.2.1遗传算法遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。资源受限项目调度求解的是工期最小、净现值最大等一些最优解，所以可以运用遗传算法来求解。基于遗传算法的资源约束型项目调度优化]6[杨利宏等]6[基于遗传算法，着重讨论优化资源有限—工期最短问题。该优化过程是在多资源约束下，通过检索随机生成的活动调度筛选出资源约束下最小工期的调度方式。最后通过某公司的电脑横机研发项目为研究对象，针对多资源约束的项目计划和调度问题，采用遗传算法优化项目的调度方法。整个遗传算法的流程如下图所示。在进行优化计算前，首先完成从搜索空间到遗传空间的转换，进行两方面的工作：（1）将目标函数转换成适度函数，即将最小值问题通过比例运算转化成最大值问题。（2）染色体编码，通过基于随机优先权把实际的AON网络转换成项目活动的调度。根据适应度函数，计算适度值。接下去是在遗传空间上进行选择、交叉、变异，知道找到最优解。选择：在这基础上，根据计算出来的适度值，采用轮盘赌操作进行选择，选择出需要繁殖的父代群体。这个过程就是“选择操作”交叉：本文采用两点交叉的运算模式，为了不产生重码，文中提出了基于位置映射关系的两点交叉。既可以保证不重复，也可以很好地保证个体的继承性。变异：采用基于中心位置的变异。分为四步：计算变异基因的个数U、生成U个随机数作为基因的变异、定位到相关的染色体、采用中心位置变异的方法，随机与本染色体内的其他等位基因调换数值，从而生成新的染色体。作者将该方法实际应用到企业生产中，并取得了一定的成果，从而证明了运用遗传算法进行项目调度优化的可行性。他的优点在于采用启发式群体随机搜索的方法，在搜索的过程中不易陷入局部最优。但是其缺陷是局部搜索能力较差并容易早熟收敛。一种求解资源受限项目调度的遗传算法]7[杜焱、彭武良]7[在文中求解使用可更新资源的单模式资源受限项目调度问题的遗传算法。同样是求解最小化的项目工期。在继承了基于排列和基于优先级的编码方案的优点，提出了一种新的基于优先权排列的编码方案。采用了串行调度方法生成项目计划。文中解释了遗传算法的思想。把问题的解表示成“染色体”在执行进化之前，给出一群“染色体”，即种群。然后，按照适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代。这样一代一代进化，就会收敛到最适应环境的一个染色体。就是问题的最优解。较之于杨利宏等[10]在对于遗传算法在项目调度中的应用，本文的亮点在于提出了一种新的基于优先权的编码方案。染色体中包含两种信息：位置和值。这种方法