抢占式资源受限项目调度问题（PRCPSP）是项目调度的一个重要子问题，是在传统RCPSP基础上，放弃了任务“非抢占”假设而形成的（刘寅斌等，2019）。它允许项目任务在进行过程中暂时释放其所占有的资源，进入暂停状态，以满足其他任务提前执行的需要，从而给项目调度带来一定的灵活性（Creemers，2019）。在实际项目中，抢占是经常发生的，因此PRCPSP是一类特别值得研究的RCPSP问题。
虽然PRCPSP放宽了非抢占的假设，但为了使建模及求解可行，仍然需要对该问题做出一些合理的规定。
（1）关于抢占点的假设。PRCPSP的一个基本假设，就是抢占只能发生在整数时间点上。如果一项任务的工期为d∈Z+，那么该任务最多可以被抢占d−1次；换句话说，最多可以分成d部分执行，每部分的工期为1。
（2）关于抢占成本的假设。PRCPSP的另一个基本假设，是当抢占发生后，该项任务在重新启动时并不会产生额外的成本。这意味着，对于项目中的任意一项任务，不管它在执行过程中有没有被抢占，也不管被抢占的次数是1次或多次，当这项任务完成时，围绕该项任务的执行而产生的总成本、该项任务曾经占用的每一类资源的数量，均为常数。当然，在现实的项目管理中，任务重启往往需要额外的时间或成本，因此这个假设是对现实项目的简化，如果考虑重启成本，则PRCPSP会更加复杂。
Lino（1997）总结了PRCPSP中“抢占”的三种模式，即：（1）无抢占；（2）每项任务最多在整数时间点发生一次抢占；（3）在整数时间点发生任意次抢占。Ballestín等（2008）在Lino（1997）的基础上将PRCPSP进一步描述为m_PRCPSP问题，其中m为非负整数，表示所有任务允许最多被抢占m次，抢占发生在任意的整数时刻上（称之为“离散的任务抢占”），且对于具体一项任务，其允许被抢占的次数在数值上不大于其工期（整数）的值。显然，0_PRCPSP等同于RCPSP，即Lino（1997）的模式1；而1_PRCPSP则对应Lino（1997）的模式2；m_PRCPSP是最一般化的RCPSP，对应Lino（1997）的模式3。Ballestín等（2008）发现，1_PRCPSP在项目实践中比较常见，具有重要的实际意义，而且在理论上也有其特殊的研究价值。
在本章中，我们专注于研究1_PRCPSP问题。经典的1_PRCPSP可以表示为{m，1|1_pmtn，cpm|Cmax}。与RCPSP一样，用Pj表示任务j的紧前任务集合，t表示时间点，T表示项目截止日期；除任务j=0和j=n+1外的任务可被拆分为两部分ja和jb，其开始时间分别表示为sja和sjb，工期分别为非负整数dja和djb，且dja+djb=dj；此外，用At表示t时刻正在进行中的任务的集合。1_PRCPSP的数学模型可以表示为（Brucker et al.，1999；Demeulemeester and Herroelen，1996）：
目标函数（9.7）是最小化项目工期。式（9.8）与（9.9）确保项目任务满足紧前约束。式（9.10）是PRCPSP的特别要求，在不考虑任务重启成本的情况下，两个子任务的工期和等于原任务工期。式（9.11）设定了初始时间，式（9.12）是资源约束，式（9.13）限定抢占仅发生于非负整数时间。
满足上述约束要求的解即为1_PRCPSP的可行进度计划，可以表示为S=（s0，s1a，s1b，…，sna，snb，sn+1），其中sja是任务j的第一部分的开始时间，sjb是任务j的第二部分的开始时间。(www.xing528.com)
PRCPSP也可以用网络图进行描述。Ballestín等（2008）提出了将G=（V，A）转换为允许一次抢占的项目网络图G′=（V′，A′）的步骤。具体做法是，将非虚拟任务j=1，2，…，n看作两项子任务ja和jb，构造弧（ja，jb）；将G中的弧（i，j），i≠0且j≠n+1转化为弧（ib，ja）；将弧（0，i）转化为弧（0，ia），弧（i，n+1）转化为弧（ib，n+1）。
考虑如图9.1所示的RCPSP项目，其对应的1_PRCPSP项目网络图如图9.2所示。
图9.1 RCPSP项目网络图
图9.2 1_PRCPSP项目网络图
图9.3则是该项目1_PRCPSP问题的一个最优进度计划，其中任务5在时间点11被抢占，然后在时间点15继续执行。项目的最优工期为17，比RCPSP问题最优解节约一个单位时间。
图9.3 1_PRCPSP最优进度计划
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
