资源受限项目调度

资源受限项目调度（resource-constrained project scheduling，RCPSP）在满足任务先后关系的同时，限制各时刻可用的人手、设备或资金等资源，并安排活动的开始时间。经典模型中活动工期已知、开始后不可中断，资源属于可再生资源：本时段用完的工人在下一时段仍可使用，而非像原材料那样被永久消耗。

设四项活动A、B、C、D的工期分别为三、二、二、一小时，每小时需资源二、二、一、一单位；C在A结束后才能开始，D在B结束后才能开始，总容量三。若只按先后关系把A和B都安排在零时开始，会同时占用四单位，实际无法执行。

时间区间上的容量

记活动 $i$ 的开始为 $s_i\ge 0$，工期 $p_i>0$，资源需求为 $r_i\ge 0$。先后边 $i\to j$ 要求 $$s_j\ge s_i+p_i.$$ 某时刻的资源占用为仍在进行的活动需求之和： $$\sum _{i:s_i\le t<s_i+p_i}{r}_i\le R(\text{所有 }t).$$ 半开区间约定表示结束时可以立即把资源交给下一活动。多种资源时，每一种都须有单独的容量行。目标通常为最小化总工期 $C_{max}=\underset{i}{max}(s_i+p_i)$，不是最小化工期相加；后者在工期固定时根本不会随安排变化。

六小时方案与不可改进的证明

安排A在零至三，B与C都在三至五，D在五至六。三至五的资源占用是二加一等于三，其余时段均未超限；先后约束也满足，总工期六小时。

同列重叠的活动可以同时执行，但必须把它们的资源需求相加。B与C并行只占三单位，A与B并行却会占四单位。

A与B各需二单位，容量只有三，因此二者不能有正时长重叠。若A先于B，B最早三时开始、五时结束，其后D至少再需一小时，总工期不小于六。若B先于A，A最早二时开始、五时结束，随后C还需两小时，总工期不小于七。非抢占性使这两种先后覆盖所有可能；已构造六小时方案，故全局最优。

另一个常用下界来自资源总工时。将容量约束在 $[0,C_{max})$ 上积分，得到 $$\sum _i{r}_i{p}_i\le R{C}_{max}.$$ 主例资源工时为 $6+4+2+1=13$，下界仅 $13/3$ 小时，弱于六小时证书。不同下界控制不同瓶颈；资源总量足够，不保证先后安排一定可行。

阶梯图直接核对每个事件区间的资源占用；面积为13单位小时，与各活动资源乘工期的总和一致。

按事件核验方案

只有开始或结束时刻会改变占用，因此不必把每个小时细分成网格。代码检查给定方案，返回工期；不负责寻找最优方案。它接受非负整数开始时刻、正整数工期、非负整数资源需求。

Python 3

from collections import defaultdict

def check_rcpsp(start, duration, requirement, capacity, edges):
    s, p, r = tuple(start), tuple(duration), tuple(requirement)
    n = len(s)
    if len(p) != n or len(r) != n or type(capacity) is not int or capacity < 0:
        raise ValueError("matching data and nonnegative integer capacity required")
    if any(type(v) is not int or v < 0 for v in s+r):
        raise ValueError("nonnegative integer starts and requirements required")
    if any(type(v) is not int or v <= 0 for v in p):
        raise ValueError("positive integer durations required")
    for a,b in edges:
        if type(a) is not int or type(b) is not int or not (0 <= a < n and 0 <= b < n):
            raise ValueError("invalid precedence index")
        if s[b] < s[a] + p[a]:
            raise ValueError("precedence violation")
    events = defaultdict(int)
    for a,b,c in zip(s,p,r):
        events[a] += c; events[a+b] -= c
    load = 0
    for t in sorted(events):
        load += events[t]
        if load > capacity:
            raise ValueError("resource capacity exceeded")
    return max((a+b for a,b in zip(s,p)), default=0)

print(check_rcpsp([0,3,3,5], [3,2,2,1], [2,2,1,1], 3, [(0,2),(1,3)]))
# 6

事件扫描保持当前载荷等于这一事件之后的区间占用；同一时刻的开始与结束合并，符合半开区间约定。至多 $2n$ 个事件，检查时间为 $O(n\log n+|E|)$，额外空间为 $O(n)$。

变式。 容量提高到四后，A、B可从零并行；C在三至五、D在二至三，五小时完成。路径A再C本来就需五小时，故新方案同样最优。只用关键路径法可得到忽略资源竞争的工期下界，不能把其最早开始时间直接当成资源受限问题的最终排程。