基于OPL与CPLEX的MS-RCPSP代码升级：支持多前置任务

我用OPL结合CPLEX开发的多技能资源受限项目调度（MS-RCPSP）求解代码，目前仅支持单个前置任务配置，现需改造为支持每个任务设置多个前置任务。以下是改造方案及完整代码：

关键修改点 #

• 前置任务数据结构调整：将原单个整数类型的前置任务数组int P[J]替换为集合类型数组setof(int) P[J]，允许每个任务关联多个前置任务。
• 前置约束逻辑更新：修改ct1约束，遍历当前任务的所有前置任务，取每个前置任务的完成时间（开始时间+持续时间）的最大值，确保当前任务在所有前置任务完成后才启动。

改造后的完整代码 #

// 示例数据
range J = 1..5;//任务集合 
range R = 1..3;//资源集合
range T = 1..6;//时间索引 
range S = 1..3;//技能索引 
range K = 1..3;//资源数量 

// 定义每个任务的前置任务集合，{0}表示无前置任务
setof(int) P[J] = [{0}, {0}, {0}, {2,3}, {0}];

int d[J] = [2,1,3,3,1]; //任务j的持续时间 
dvar int s[J] >= 0; //任务j的开始时间（改为决策变量，原固定值不符合调度逻辑）

// 资源使用矩阵
int L[J][K] = [[0,1,0], [2,0,0], [0,0,2], [1,0,0], [0,0,1]]; //任务Tj对技能Sk的要求熟练度
int Q[R][K] = [[0,1,2], [2,2,0], [1,0,1]]; //资源Rr掌握技能Sk的水平

// 决策变量
dvar boolean x[J][R]; //判断任务Tj是否分配给资源R的决策变量
dvar boolean y[J][R][T]; //判断任务Tj是否在时间t由资源Rr执行的决策变量

minimize max(j in J) (s[j] + d[j]);
 

subject to {
  // 前置约束：当前任务开始时间 >= 所有前置任务的完成时间最大值
  forall(i in J)
  ct1: s[i] >= (max(j in P[i] : j != 0) (s[j] + d[j])) ; 
  
  // 技能能力约束：任务分配的资源需满足技能熟练度要求
  forall(j in J, k in S)
  ct2: sum(r in R) x[j][r] * Q[r][k] >= L[j][k]; 
  
  // 任务分配唯一性约束：每个任务仅分配给一个资源
  forall(j in J)
  ct3: sum(r in R) x[j][r] == 1; 
  
  // 资源时间冲突约束：每个资源同一时间最多处理一个任务
  forall(r in R, t in T)
  ct4: sum(j in J) y[j][r][t] <= 1;
  
  // 补充任务执行时间与分配的关联约束（原代码缺失，确保变量逻辑一致）
  forall(j in J, r in R)
  ct5: sum(t in T) y[j][r][t] == x[j][r] * d[j];
  
  forall(j in J, r in R, t in T)
  ct6: y[j][r][t] <= x[j][r];
  
  forall(j in J, r in R, t in T)
  ct7: s[j] <= t <= s[j] + d[j] - 1 -> y[j][r][t] == x[j][r];
}

execute{
  writeln("项目最短完工时间: " + cplex.getObjValue());
  writeln("各任务开始时间:");
  for(var j in J) {
    writeln("任务" + j + ": " + s[j]);
  }
}

额外说明 #

• 原代码中s[J]被定义为固定值，不符合调度问题求解逻辑，已改为决策变量并添加>=0约束。
• 补充ct5、ct6、ct7三个约束，确保任务执行时间变量y与资源分配变量x、任务开始时间s、持续时间d之间的逻辑一致性，避免无意义解。

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