分支定界法求解RCPSP的树构造方法技术咨询（附实例）

先把问题的核心条件列清楚：

• 任务：T1-T4，持续时间 d=[2,3,1,4]，资源需求 resource_amount=[3,2,5,4]
• 资源总容量：6
• 硬约束：T3必须在T1开始前完成（S3+1 ≤ S1），T2必须在T4开始前完成（S2+3 ≤ S4）
• 目标：最小化项目完工时间（所有任务完成时间的最大值）

分支定界的核心思路很直接：用节点代表部分调度方案，每次从节点分支扩展未安排的任务，给每个节点算一个「下界」（这个节点能达到的最小可能完工时间），如果下界已经比当前找到的最优解大，直接砍掉这个节点（剪枝），直到找到最优解。

一、求解树构造过程 #

1. 根节点（Node 0） #

这是初始状态：还没安排任何任务，只满足给定的优先约束。

• 下界计算：忽略资源约束，只算优先约束下的关键路径长度：
  • T3→T1的总时长是1+2=3；T2→T4的总时长是3+4=7，取最大值7作为初始下界（LB0=7）
• 当前最优解（UB）初始设为无穷大，因为还没找到任何可行解。

2. 从根节点分支 #

根节点下，能先安排的任务只有T2和T3——因为T1必须等T3完成才能开始，T4必须等T2完成才能开始，这俩现在都没安排，所以T1、T4不能先上。

分支A：先安排T3（Node 1）

• 调度状态：T3从时间0开始，占用5单位资源，1时刻完成。已完成任务：T3；待安排：T1、T2、T4
• 下界计算：
  考虑资源约束的话，T3完成后（时刻1），T1和T2的资源需求加起来是3+2=5≤6，可以并行安排。T1完成时刻1+2=3，T2完成时刻1+3=4；之后T4要等T2完成再开始，4+4=8。所以这个节点的下界LB1=8。
• 因为LB1 < 无穷大，保留节点继续分支。

分支B：先安排T2（Node 2）

• 调度状态：T2从时间0开始，占用2单位资源，3时刻完成。已完成任务：T2；待安排：T1、T3、T4
• 下界计算：
  忽略资源约束的话，剩余任务的关键路径是T3→T1（1+2=3）和T4（4），取最大值4加上T2的完成时间3，得到LB2=7。实际资源约束下，T2完成后（时刻3），单个任务的资源需求都≤6，但任意两个任务的资源总和都超过6，只能串行，最早完工时间是7（T4从3开始到7完成，T3和T1后续串行到10，但下界取最理想的7）。
• LB2 < 无穷大，保留节点继续分支。

3. 优先处理下界更低的Node 2 #

Node 2的待安排任务里，T3和T4都可以先安排（T1要等T3完成），分两个分支：

分支B1：先安排T4（Node 3）

• 调度状态：T2在0-3完成，T4从3开始，占用4资源，7时刻完成。已完成任务：T2、T4；待安排：T3、T1
• 下界计算：剩余的T3→T1总时长3，加上当前最晚完成时间7，LB3=10。此时计算实际完工时间：T4完成后安排T3（7-8），再安排T1（8-10），项目完工时间10。更新UB为10。
• 因为LB3=10等于当前UB，后续分支不会得到更优解，直接剪枝。

分支B2：先安排T3（Node 4）

• 调度状态：T2在0-3完成，T3从3开始，占用5资源，4时刻完成。已完成任务：T2、T3；待安排：T1、T4
• 下界计算：剩余任务T1（2）和T4（4），最理想的情况是并行，但资源需求3+4=7>6，只能串行，最早完工时间是10（比如先T1后T4：4-6完成T1，6-10完成T4）。这个节点的可行解完工时间10，等于当前UB，剪枝。

4. 处理Node 1（LB=8 < UB=10） #

Node 1的待安排任务里，T1和T2都可以先安排（T4要等T2完成），分两个分支：

分支A1：先安排T1（Node 5）

• 调度状态：T3在0-1完成，T1从1开始，占用3资源，3时刻完成。已完成任务：T3、T1；待安排：T2、T4
• 下界计算：剩余的T2→T4总时长7，加上当前最晚完成时间3，LB5=10，等于当前UB=10，剪枝。

分支A2：先安排T2（Node 6）

• 调度状态：T3在0-1完成，T2从1开始，占用2资源，4时刻完成。这里注意：T1可以和T2并行安排（3+2=5≤6），所以T1从1开始，3时刻完成。已完成任务：T3、T1、T2；待安排：T4
• 实际完工时间：T4在T2完成后（4时刻）开始，占用4资源，8时刻完成。项目完工时间8，比当前UB=10更优，更新UB为8。
• 这个节点的下界LB6=8，等于新的UB，是最优解节点，无需继续分支。

5. 最终剪枝 #

现在UB=8，剩下的所有节点（Node3、Node4、Node5）的下界都≥8，且实际完工时间都≥8，全部剪枝，求解结束。

二、求解树结构（简化版） #

Node 0 (LB=7, UB=∞)
├─ Node1 (先安排T3, LB=8)
│  ├─ Node5 (先安排T1, LB=10 → 剪枝)
│  └─ Node6 (先安排T2, LB=8 → 最优解，完工时间8)
└─ Node2 (先安排T2, LB=7)
   ├─ Node3 (先安排T4, LB=10 → 剪枝)
   └─ Node4 (先安排T3, LB=7 → 完工时间10 → 剪枝)

三、最优调度方案 #

• T3：0-1（占用5资源）
• T1：1-3（占用3资源），与T2并行
• T2：1-4（占用2资源）
• T4：4-8（占用4资源）

所有约束都满足：T3完成时间1 ≤ T1开始时间1；T2完成时间4 ≤ T4开始时间4；各时段资源使用均不超过6。项目完工时间8，是最小可能值。

内容的提问来源于stack exchange，提问作者ellana_d