资源受限项目调度 (RCPSP)

资源受限项目调度问题（RCPSP）在既受先后约束、又受工人、机器或每期预算等有限可再生资源约束的条件下调度项目活动。与假设资源无限的 CPM 不同，RCPSP 是强 NP 难的。

工作原理

优先规则启发式用串行或并行的进度生成方案构建排程：活动被插入到先后关系与资源可用性同时满足的最早时刻，并按总后继最多或浮动最小等规则排序。精确方法使用带基于资源下界的分支定界，而元启发式，尤其是采用活动列表编码的遗传算法，在标准 PSPLIB 基准上占据主导。

应用场景

RCPSP 驱动施工班组与设备调度、人力受限下软件团队的冲刺规划、炼油厂检修停机排程以及按单制造的生产计划。它是图算法与工业运筹学之间的典范桥梁。