基于网络计划的资源受限项目调度优化问题研究文献综述

1.资源受限项目调度优化问题

资源受限项目问题(ResourceConstrainedProjectSchedulingProblem,简称RCPSP)最早可追溯到4500年前埃及金字塔和美洲玛雅神庙的建造，涉及领域甚广。项目调度则是企业生产计划和控制之间的重要环节，是实现企业生产运行高效率、低成本和高可靠性的关键，研究具有较大的学术价值和交叉性，有助于推动各学科的发展与相互融合。自RCPSP提出以来，便成为了著名的NP-hard问题。所以，关于RCPSP的优化问题，各界学者和从业人员争相研究。

Leus, Herroelen设计了资源流网络模型, 并采用分支定界法解决了该问题。Artigues等提出了一个按活动分配资源的资源流网络算法, 该算法优点是计算简单, 但生成的附加约束较多，Policella等通过在基准计划中生成偏序调度计划, 提出了通过对活动分配链从而生成资源流网络的算法。Deblaere等提出了资源流网络优化算法MABO，通过对比分析结果表明MABO算法构建的调度计划鲁棒性较强, 但算法的准确性不髙, 会造成多资源分配方案的存在。

资源项目调度优化问题研究主要分为两方面:一方面是从实际生活出发,为了更好地优化现实中的调度问题,将企业的实际项目特点纳入研究范围,如MRCPSP(多模式资源受限项目调度问题)、DRCPSP(动态资源受限项目调度问题)等。如2001年沈阳工业大学刘艳秋等人研究资源受限项目调度问题 (RCPSP) 中网络现金流的优化问题。提出以网络净现值最大作为网络现金流优化的目标 , 建立了带有贴现率的非线性整数规划模型 , 采用遗传算法与模拟退火算法相结合的混合式遗传算法进行求解。该研究结论表明了方法的合理性和有效性。

2013年合肥工业大学付磊基于关键链的复杂产品研发项目和任务绩效评估问题，考虑复杂产品研发调度过程中的主管不确定性、模糊性、定量和定性指标共存性等，提出将模糊层次分析法与论据理论相结合的评估方法。该方法从企业整体绩效出发，提出基于关键链的两层决策模型，以解决任务占用多种类型资源情况下资源受限的多项目调度问题。

2019年施应玲等人对鲁棒性资源分配提出了基于“稳定性成本贡献值”与“后向子网络复杂度”的NSM资源流网络生成算法, 在接受资源和分配资源的活动优先顺序上设定规则, 使得资源分配有序进行, 尽可能减少附加资源约束, 计划的稳定性成本。

另一方面则是研究新的求解算法来优化调度问题的优化结果，提高求解速率,如遗传算法、粒子群算法和蚁群算法等智能算法不断被应用到RCPSP中。吉林大学王如雪建立项目多目标模糊优化模型，并在求解时采用基于模式和任务的双链表进行编码，利用给予快速非支配性排序的遗传算法（NSGA-）进行求解，最后用实例证明该文章算法的有效性。

2011年徐进等人研究RCPSP，改进基本PSO方法以求解全局或局部搜索能力问题。并提出了不变位交叉法，保证更新后任务序列的可行性，提高了算法的效率。2017年王海鑫等采用具有动态变惯性权重的自适应粒子群法（DCWPSO）对（RCMPSP）模型机型求解，通过GA、PSO算法求解结果与DCWPSO算法求解结果进行对比，表明了DCWPSO算法在问题求街上具有一定的优势能够有效地指导多项目优化问题，为实施过程的任务调度与资源配置提供参考。

辽宁省金凤研究分析了蚂蚁如何在项目网络图上巡游并动态生成最优解, 以及蚁群信息素的更新方式和多种启发式信息的定义方法, 验算了算法在不同的参数组合下对测试案例的求解效果。2019年安晓亭和张梓琪提出一种带局部搜索的改进蚁群优化算法，用于求解多目标资源受限项目调度问题。其采用改进的蚁群优化算法获取Pareto阶级，并通过基于带逻辑约束的Insert和Swap邻域搜索法对已获得的非支配解进行局部搜索，进一步提高算法的性能。

2017年倪倩云基于改进遗传算法的多模式资源受限项目调度问题（MRCPSP），构建工期最优的数学模型，并为求解该模型设计了全新的遗传算法——LPSGA（Level Project Scheduling Optimization based on Genetic Algorithm）,将LPSGA与另外四种传统启发式算法进行对比测试，结果表明该算法能够有效且准确地求解MRCPSP，最后用实例验证了该算法具有实际应用价值。林丹等人研究了以排序健壮性最大为优化目标的具有模糊加工时间和模糊交货期的资源受限项目调度问题, 采用六点模糊数表示模糊加工时间和模糊交货期, 引入了两种模糊数的弱比较方法, 即重心距离法和积分值法.针对这一优化问题设计了一种基于任务链表编码形式的遗传算法。

2.关键链法

关键连法是一种网络技术，也是一项全新的工程项目进度管理方法。其可以对资源受限项目问题进行有效优化。

姜海莹通过对已有文献进行的总结与梳理，从关键链的识别与调度、缓冲设置影响因素、缓冲尺寸与设置、缓冲监控四个方面对关键链项目管理法研究的核心内容进行阐述与分类，并提出了下一步的研究方向。

谭泽涛对进度管理和关键路径法内涵和原理的剖析，深入探索进度管理实践过程。针对进度计划的制定和更新维护过程，以关键路径的确定及动态管理为核心，从多方面分析影响进度计划可靠性的各类因素，阐述其影响机制并分别给出实践指导，为实现精细化项目管理提供支撑。

李永宁、秦拥军等人基于对乌鲁木齐地铁二道桥车站深基坑施工进度管理应用隶属度函数对工期进行预估, 考虑缓冲系数、工序资源紧张度、风险偏好水平、工序复杂度等, 确定缓冲区的大小, 应用关键链技术进行进度优化。并表明了关键链优化技术在地铁车站深基坑施工进度管理中的应用合理可靠。

王电超运用关键链技术，有重点地对项目进行精细化结构分解、职责分工、资源分配，运用三点时间估算法提出项目活动时间的冗余，得出初始进度计划。其研究表明了关键链技术通过高质量需求分析准确定位项目目标任务，细分工作结构重排顺序，优化各项资源配置来巴托资源限制，有效地解决资源项目受限的优化问题。

研究关键链的论文涉及领域较广，但其适用范围比较狭窄。论文研究侧重点不同，导致其作用也不尽相同。参考文献还存在研究不够深入的问题，一些论文浅尝辄止，留给后人较大的研究空间。

右移动，然后向左移动，以便获得更好的调度。为了证明其功能性和通用性，将其添加到各种采样方法和元启发式方法以及新方法进行测试。Artigues等人设计了一种基于并行SGS和最坏情况松弛（WCS）优先级规则的插入技术，其他优先级规则对于并行SGS亦有可能。Sprecher提出了一种将精确的方法结合到启发式搜索中的网络分解技术。在每一次迭代中，利用最新的完成时间优先规则，通过偏随机抽样产生初始调度。

3.时间-成本控制法

时间-成本控制法是对于网络计划进行优化的方法，它从项目的正常时间、正常成本

应急事件以及应急成本的控制优化网络计划，从而实现受限资源项目的优化。

李迁等人建立项目调度的工期-成本双目标优化模型，并基于此模型优化采用NSGA-II算法求解模型。但该模型对于提高工期和减低成本方面有待加强。黄深利用时间成本优化模型进行分析，结合问题分析和定量研究，给出了实例项目管理的对策建议。但存在针对性过强，研究学者若想采用该研究结果需分析一番。沈俊鑫和沈冰亮通过构建基于着色成本时间约束Petri网的项目仿真模型，分析模型变迁激发规则以及时间、成本的累加性，并提出基于时间成本状态的项目时间-成本分析方法。论文不足之处是没有对模型变迁序列进行优化，导致模型仿真效率较低。鲁玉军提出一种使用网络计划技术建立时间-成本优化模型来缩短工程时间和降低人工成本的方法，以找出节省成本的生产安排方案。但该方法因工厂问题复杂，存在执行困难的问题。

参考文献

[1]方晨,王凌.资源约束项目调度研究综述[J].控制与决策,2010,25(05):641-650 656.

[2]王如雪. 项目多目标模糊调度优化模型及算法研究[D].吉林大学,2016.

[3]付磊. 基于关键链的复杂产品研发多项目调度问题研究[D].合肥工业大学,2013

[4]施应玲,宿慧芳,庞南生.鲁棒项目调度问题中资源流网络生成算法研究[J].山西建筑,2018,44(22):234-236.

[5]王海鑫,王祖和,温国锋,李海霞.自适应粒子群算法求解资源受限多项目调度问题[J].管理工程学报,2017,31(04):220-225.

[6]徐进,费少梅,张树有,施岳定.自适应粒子群求解资源动态分配项目调度问题[J].计算机集成制造系统,2011,17(08):1790-1797

[7]安晓亭,张梓琪.基于改进蚁群优化的多目标资源受限项目调度方法[J].系统工程理论与实践,2019,39(02):509-519.

[8]金凤.蚁群算法在资源受限项目调度中的应用[J].电脑知识与技术,2008,4(S2):44 63

[9]倪倩芸. 基于改进遗传算法的多模式资源受限项目调度问题研究[D].浙江工商大学,2018.

[10]王宏,林丹,李敏强.求解模糊资源受限项目调度问题的遗传算法[J].系统工程学报,2006(03):323-327

[11]LeusR.Thegeneration of stable project plans:Complexity and exact algorithms[J].K.u.leuven Department of Applied Economics Sept, 2003; 2 (3) :251-254.

[12]Herroelen W, LeusR.The construction of stable project baseline schedules[J] .European Journal of Operational Research,2004, 156 (3) :550-565.

[13]Artigues C, Michelon P, ReusserS.Insertion techniques for static and dynamic resource-constrained project scheduling[J].European Journal of Operational Research, 2003, 149 (2) :249-267.

[14]olicella N. Scheduling with uncertainty:A proactive approach using Partial Order Schedules[J]_Ai Communications, 2005,18 (2) :165-167.

[15]Policella N, Cesta A. Oddi A, et al. Solve and-robustify[J]. Journal of Scheduling, 2009, 12 (3) :299.

[16]Deblaere F, Demeulemeester E, Herroelen W, et al.Robust Resource Allocation Decisions in Resource-Constrained Projects[J]. Decision Sciences, 2010, 38 (1) :5-37.

[17]张沙清,陈新度,陈庆新,等基于优化资源流约束的模具多项目反应调度算法[J]系统工程理论与实践，2011, 31 (8) :1571-1580.

[18]姜海莹.关键链项目管理法（CCPM）研究综述与展望[J].建筑施工,2019,41(09):1764-1769

[19]谭泽涛.基于关键路径法的项目进度管理研究[J].建筑经济,2019,40(09):67-71.

[20]李永宁,秦拥军,于广明,康晓丹.基于关键链技术的地铁车站深基坑施工进度优化[J].项目管理技术,2019,17(07):101-104

[21]王电超. 基于关键链技术的CJ软件开发项目进度管理研究[D].山东大学,2019.

[22]李迁,陶莎,周晓园,盛昭瀚.考虑作业空间干涉的工程项目时间-成本均衡优化研究[J].中国管理科学,2019,27(10):170-178.

[23]黄深. H市国际城房地产开发项目时间—成本优化管理研究[D].哈尔滨工业大学,2019

[24]沈俊鑫,沈冰亮.资源约束项目时间-成本均衡优化仿真模型[J].昆明理工大学学报(自然科学版),2015,40(02):130-137.

[25]李立,翟所霞,鲁玉军.基于网络计划技术的制造型企业时间—成本优化研究[J].浙江理工大学学报,2013,30(05):733-737.