2资源受限项目调度问题

在经典的DTCTP问题中，没有考虑到资源的约束，在实际项目调度问题中，活动的压缩执行是通过增加资源分配实现的，而资源并非没有限制，因此资源约束不可避免。资源受限项目调度问题从时间和资源上合理安排调度项目的活动，在资源限定情况下实现目标最优化[27]。资源受限项目调度问题(Resource-constrainedProjectSchedulingProblem，RCPSP)最早可追溯到4500年前埃及金字塔和非洲玛雅神庙的建造[28]。甘特图，关键路径法和计划评审技术都作为有效的工具广泛应用于各种项目调度问题。

对于RCPSP问题，资源是非常重要的，根据Blazewicz等[29]的研究，资源可分为三类：可持续使用的资源，消耗性的资源和双重限制资源。可持续使用的资源不随项目的进展而消耗，例如人力资源，设备等。消耗性的资源随着项目的进展而逐渐消耗，例如原材料，能源等。双重限制资源既在项目的每个阶段收到限制也在总量上受到限制，例如资金。近年来，也有学者提到了部分可更新资源的概念[30]，比如在工作日上班而在周末休息的人力资源。

RCPSP模型在项目调度中是最基础的模型，考虑到与实际问题相联系，研究人员们对此做了拓展，如多模式项目调度问题，Elmaghraby[31]提出了项目中的活动可以以多种模式来执行，例如加班等方式。Salewski等[32]在多模式资源受限项目调度问题(Multi-modeMultipleResource-constrainedProjectSchedulingProblem,MRCPSP)的基础上引入了模式一致性问题。彭武良等人[33]在经典的DTCTP问题中加入了可再生资源的约束，提出了一种多模式资源约束时间成本均衡问题模型。并且给出了改进的遗传算法来求解这个问题，与精确算法相比较而验证了这个方法的有效性。何正文[34]等概述了常用的启发式算法，可分为基于优先权规则的启发式算法和超启发式算法。前者主要有最大分级位置权重规则、最迟完成时间规则、最多紧后活动规则、最迟开始时间规则、最小松弛规则。同时还扩展出多通道算法，如：多重优先权规则启发式算法、前向-后向进度安排启发式算法、抽样性启发式算法、适应性启发式算法等等。后者主要有模拟退火，禁忌搜索和遗传算法。另外，还有蚁群算法，可变邻点搜索技术等其他类型算法。此外，以色列学者高德拉特将约束理论（TheoryofConstraint，TOC）应用于项目管理领域，提出了基于关键链的项目管理理论[35]。由于每个算法有其优缺点，因此算法之间的结合也可以更有效地解决问题。喻小光等[36]认为遗传算法能避免陷入局部最小的并行搜索，但也因此容易早熟收敛。相反的模拟退火是一种能以稳定速度收敛的局部搜索技术，因此将模拟退火嵌入遗传算法，提出了融合二者优点的遗传模拟退火算法（GeneticSimulatedAnnealing

Algorithm,GSA）。本文以上理论基础上，把资源受限项目调度理论和时间成本均衡问题结合，建立了优化

的资源受限时间成本均衡模型，并研究了一种改进的启发式算法来求解该模型。