RCPSP求解器

伪代码

RCPSP 就是 CPM 加上有限资源，而仅仅这一项追加就把它从线性推到了 NP 困难。务实的做法是由优先规则引导的串行排程启发式。

RCPSP(活动集, 依赖集, 资源容量):
    顺序 = 拓扑排序(活动集)
    按某条优先规则对该顺序重新排序
    // 例如最小时差优先，或最长工期优先

    对优先排序后的每项活动 a:
        t = max(结束[p]，p 为 a 的前驱)
        当区间 [t, t + 工期[a]) 上存在某资源 r 已满载:
            t = t + 1        // 后推直到放得下
        开始[a] = t; 结束[a] = t + 工期[a]
        在该区间上占用 a 所需的资源

    项目工期 = max(结束[a])

与 CPM 的差别在于：一项活动的开始时刻不再只由它的前驱决定，它可能因为另一项毫不相干的活动正占着机器而被往后推。这就摧毁了让 CPM 保持线性的那条性质，因为对某项活动的决策现在会影响与它没有任何依赖关系的活动。正因如此，在拓扑序上做多少动态规划都不够用。

分步示例演算

为四项争用同一种容量为 1 的资源的活动排期，并把结果与 CPM 的预测相对照。

示例图: 活动 A（3 天）、B（2 天）、C（4 天）和 D（2 天），其中 A 与 B 先于 C，C 先于 D。它们都需要同一台机器，而这台机器只有一台。

1. CPM 会怎么说. 在没有资源限制的情况下，A 与 B 从时刻 0 起并行，C 在 3 开始，D 在 9 结束。项目工期：9 天。
2. 施加资源限制. A 与 B 都需要那台机器，而机器只有一台。它们不能再重叠，必然有一个要等。由优先规则决定是哪一个。
3. 优先规则：最长工期优先. A 历时 3、B 历时 2，因此 A 先上，占用机器从 0 到 3。B 只能等待，从 3 运行到 5。
4. 为 C 排期. C 要求 A 与 B 都已完成，也就是时刻 5，而此时机器空闲。C 从 5 运行到 9。
5. 为 D 排期. D 紧随 C，从 9 运行到 11。项目工期为 11 天。

在资源无限时项目历时 9 天；只有一台机器时则是 11 天。多出来的这两天并非源于任何依赖关系，而纯粹来自资源争用。另外还要注意，关键路径这个概念在这里变得含混：决定完工日期的那条链现在包含了 B 等待机器的时间，而那根本不是一条前驱关系。这也正是资源紧张的项目上，CPM 排期会系统性偏乐观的原因。

复杂度及其来源

时间: NP 困难；串行启发式为 O(V^2 · R) · 空间: O(V · R)

串行排程启发式对 V 项活动各处理一次，而对每一项可能都要通过检查 R 种资源的可用性来把开始时刻往后推，若采用直接实现，最坏情况大致是 O(V 的平方乘以 R)。这很快，也能扩展到数千项活动。它做不到的是给出最优性保证。精确的 RCPSP 是 NP 困难的，而且被认为是运筹学中最棘手的排程问题之一：仅含 60 项活动的基准算例曾多年未被解开。精确的分支定界依结构不同大约能处理 30 到 60 项活动，超出之后就要转向遗传算法、禁忌搜索之类的元启发式方法。

何时使用资源受限项目调度 (RCPSP)，何时不宜

根据资源是否真的构成瓶颈，以及你是否需要最优性保证来选择。

常见陷阱

• 先用 CPM 排期再把资源补上去. CPM 排期假定并行不受限制。事后再把资源上限硬塞进去，几乎总会拉长项目，就像例子中 9 天变成 11 天那样。资源必须从一开始就进入模型，而不是当作事后的修补。
• 以为关键路径的含义依然不变. 在资源受限的情况下，决定完工日期的那条序列可能包含因争用而产生的等待，而它们并不是前驱关系。与之对应的概念是关键链，它同时把依赖关系与资源冲突纳入其中。
• 只用一条优先规则就此收工. 不同的规则，例如最小时差、最长工期优先、后继最多，会产生不同的排期，而且没有哪一条能压倒其余。多跑几条并保留最好的那个；这代价很低，通常还能明显改善结果。
• 忘记资源可能是不可再生的. 可再生资源比如机器或人员，会在活动结束时释放。不可再生资源比如预算或材料，则是被永久消耗掉的。把后者当作前者来建模，会产生把预算重复花好几遍的排期。
• 指望大规模算例能被精确求解. RCPSP 属于经典的难题之列。含 60 项活动的基准算例曾多年抵御住了各种精确方法。如果你的项目有数百项任务，请用启发式方法排期并借助仿真来验证，而不要去追逐最优解。

常见问题

什么是 RCPSP？

资源受限项目排程问题要求给出一份排期，既满足活动之间的前驱关系，又满足可再生资源的有限可用量，通常以最小化项目总工期为目标。它就是去掉了「资源无限」这一假设之后的 CPM。

既然 CPM 是线性的，为什么 RCPSP 会是 NP 困难的？

因为资源上限把彼此之间毫无依赖关系的活动耦合到了一起。在 CPM 中，一项活动的开始只取决于它的前驱，因此按拓扑序做两趟扫描就够了。有了资源之后，推迟一项活动可能会迫使另一项完全不相干的活动也跟着推迟，正是这种全局性的相互作用使搜索空间爆炸。

CPM 与 RCPSP 有什么区别？

CPM 假定任何一组彼此没有依赖的活动都可以同时进行。RCPSP 加入了阻止这种并行的资源容量。在上面的例子中，同一个项目在 CPM 下历时 9 天，在只有一台机器的 RCPSP 下历时 11 天，而这两天之差纯粹是资源争用。

RCPSP 中的优先规则是什么？

它是当多项活动都已就绪并争用同一资源时，决定先排哪一项的启发式。常见的规则有最小时差、最长工期优先、后继数量最多，或最晚完成时刻最早。没有哪一条永远最好，因此实践中通常多跑几条并保留最好的那份排期。

RCPSP 有什么用途？

用于在机器有限的情况下安排生产线、在建筑施工中分配班组与设备、规划共用专业人员的项目组合，以及一般而言任何任务需要争夺有限产能、无法自由并行的排程场景。