拓展模型：多模式资源受限项目调度问题及其最优解策略探析

在基本RCPSP的基础上，可以进一步对项目调度数学模型进行扩展。

首先，在基本RCPSP中，组成项目的任务被认为是不可抢占的（nonpreemptive），任务被要求一次性执行完毕，不允许出现中断后再次执行的情况。而事实上，很多项目在执行过程中，由于资源的限制，需要在不同任务之间合理调配资源以尽可能提高资源的利用率，所以中断执行中的任务是较为常见的做法。如果允许任务抢占，在很多情况下可以更有效地调配资源，从而提高资源利用效率，一般可以更有效地优化项目目标。因此，抢占式资源受限项目调度问题（preemptive resource-constrained project scheduling problem，PRCPSP）在近年来开始得到关注（Demeulemeester and Herroelen，1996；Van Peteghem and Vanhoucke，2010；寿涌毅等，2014a）。当然，这类问题的计算复杂性也相应急剧增加。如果允许任务中断，在某些情况下还需要考虑任务的重启成本或资源在不同任务间的转移时间（Suresh et al.，2015；Vanhoucke and Coelho，2019）。

针对PRCPSP，Lino（1997）总结了任务“抢占”的三种模式，即：（1）无抢占；（2）每项任务最多可被抢占一次；（3）每项任务允许抢占任意次。在此基础上，Ballestín等（2008）将PRCPSP问题进一步描述为m_PRCPSP问题，其中m为非负整数，表示所有任务最多允许被抢占m次，且如果发生抢占，则必须发生在整数时刻。另外，对于任意一项任务，允许被抢占的次数在数值上不大于任务工期的整数值。由此可以看出，0_PRCPSP等同于RCPSP，对应于Lino（1997）提到的模式1；而1_PRCPSP则对应Lino（1997）的模式2；m_PRCPSP是最一般化的PRCPSP，对应于Lino（1997）的模式3。显然，PRCPSP问题是RCPSP问题的扩展。由于RCPSP是一个NP-hard问题，因此PRCPSP也是一个NP-hard问题。

一项任务还可能存在多种执行模式，不同模式下任务执行所需的资源不同，工期和费用也会相应发生变化。因此，多模式资源受限项目调度问题（multi-mode resource-constrained project scheduling problem，MRCPSP）就成为基本RCPSP的一类重要扩展（Damak et al.，2009；Jarboui et al.，2008；Lova et al.，2009；Mori and Tseng，1997；Van Peteghem and Vanhoucke，2010）。(www.xing528.com)

在经典项目调度问题中，项目任务的工期都是确定的（deterministic），或者说，采用的是传统CPM方式的单一时间估计。但是，实际上很多情形下任务工期具有不确定性，其工期在一定程度上是随机的（stochastic）。近年来，随机性资源受限项目调度问题（stochastic resource-constrained project scheduling，SRCPSP）已经成为项目调度研究的热点（Herroelen and Leus，2004；Herroelen and Leus，2005；Van de Vonder et al.，2007）。

此外，还可以在任务之间的逻辑关系、资源约束及时间约束上进一步拓展RCPSP问题。例如，很多产品开发类项目是基于DSM进行规划的，其项目调度方式就有很大差别（Chen et al.，2003；Maheswari and Varghese，2005；褚春超等，2006）。作为一般紧前关系的拓展，搭接关系也增加了项目调度问题的复杂性。De Reyck和Herroelen（1998）分析了搭接关系项目网络的求解算法。之后，De Reyck和Herroelen（1999）进一步将其拓展到多模式RCPSP。Neumann和Schwindt（1997）分析了时间窗约束对项目调度的影响与应用。Chen等（1997）则分析了同时具有时间窗约束与时序约束下的项目调度问题。

很多研究关注到其他类型的项目调度目标函数。净现值最大化是其中最受关注的一类问题。目前对资源受限项目调度问题主要是从时间角度进行研究，即考虑如何合理分配资源并安排进度，使得项目在最短时间内完成。但对于相当多的大型工程项目而言，尤其当项目时间跨度较长时，对于项目执行过程中发生的现金流的管理就成为一个重要问题，因为资金的时间价值差异可能非常显著。因此，如何合理安排项目进度计划，从而最大化项目净现值就成为一个更合适的项目优化目标。目前，涉及现金流的资源受限项目调度问题（resource-constrained project scheduling problem with discounted cash flows，RCPSPDCF）已经成为一个重要的研究领域，但由于RCPSPDCF问题的复杂性，缺乏成功的最优化算法（Herroelen and Gallens，1993；Herroelen et al.，1997；Leyman and Vanhoucke，2015），主要采用各类启发式算法进行求解（Abbasi and Arabiat，2001；Icmeli and Erenguc，1994；Padman et al.，1997；Ulusoy and Ozdamar，1995）。