基于CPLEX的OPL实现RCPSP模型：请求错误修正指导

我正在尝试实现Pritsker等人（1969年）提出的RCPSP模型，恳请提供修正错误的指导。

原实现代码 #

// Example data
range J = 1..5;
range R = 1..3;
range T = 1..10;
int P[J] = [0,1,2,3,4]; 
int d[J] = [1, 1, 3, 5, 2];
int EF[J] = [1, 2, 1, 1, 1];
int LF[J] = [2, 3, 4, 6, 2];
int Tbar = sum(j in J) d[j];

// Resource usage matrix
int u[J][R] = [[1, 0, 2],
               [1, 1, 1], 
               [1, 1, 0],  
               [2, 0, 3],  
               [1, 1, 2]]; 

// Resource availability
int a[R]= [1,2,3];

// Decision Variables
dvar boolean x[J][T];

dexpr int CT = sum(j in J, t in EF[j]..LF[j])t*x[j][t];
minimize CT;

subject to {
  forall(j in J)
    sum (t in EF[j]..LF[j]) x[j][t] == 1;
  forall(j in J, i in J)
    sum (t in EF[j]..LF[j]) (t - d[j]) * x[j][t] - sum (t in EF[i]..LF[i]) t * x[i][t] >= 0;    
  forall(r in R, t in 1..Tbar) {
    sum(j in J) u[j][r] * sum(q in max(t, EF[j])..min(t + d[j] - 1, LF[j])) x[j][q] <= a[r];
  }
}

核心问题与修正方案 #

1. 紧前约束逻辑错误

原代码对所有任务对(j,i)施加紧前约束，不符合RCPSP规则——仅当i是j的紧前任务时，才需要保证j的开始时间晚于i的完成时间。

• 修正：根据P[J]数组（P[j]表示任务j的紧前任务），仅对存在紧前关系的任务对施加约束：

forall(j in J: P[j] != 0) {
  let i = P[j];
  sum(t in EF[j]..LF[j]) t * x[j][t] >= sum(t in EF[i]..LF[i]) (t + d[i] - 1) * x[i][t];
}

说明：任务j的开始时间需≥任务i的完成时间（i的开始时间+持续时间-1）。

2. 目标函数定义错误

原目标函数是所有任务开始时间的总和，而RCPSP的核心目标是最小化项目完工时间（即最后一个任务的完成时间）。

• 修正：重新定义完工时间为所有任务完成时间的最大值：

dexpr int project_completion_time = max(j in J) sum(t in EF[j]..LF[j]) (t + d[j] - 1) * x[j][t];
minimize project_completion_time;

3. 资源约束逻辑错误

原资源约束的时间范围判断颠倒，无法正确计算时间t时的资源占用量。任务j在时间t占用资源的前提是：任务j的开始时间q满足 q ≤ t ≤ q + d[j] - 1，即q ∈ [max(EF[j], t - d[j] + 1), min(LF[j], t)]。

• 修正资源约束：

forall(r in R, t in 1..Tbar) {
  sum(j in J) u[j][r] * sum(q in max(EF[j], t - d[j] + 1)..min(LF[j], t)) x[j][q] <= a[r];
}

修正后的完整代码 #

// Example data
range J = 1..5;
range R = 1..3;
range T = 1..10;
int P[J] = [0,1,2,3,4]; 
int d[J] = [1, 1, 3, 5, 2];
int EF[J] = [1, 2, 1, 1, 1];
int LF[J] = [2, 3, 4, 6, 2];
int Tbar = sum(j in J) d[j];

// Resource usage matrix
int u[J][R] = [[1, 0, 2],
               [1, 1, 1], 
               [1, 1, 0],  
               [2, 0, 3],  
               [1, 1, 2]]; 

// Resource availability
int a[R]= [1,2,3];

// Decision Variables: x[j][t] = 1 if task j starts at time t, else 0
dvar boolean x[J][T];

// Objective: Minimize project completion time (max of all task finish times)
dexpr int project_completion_time = max(j in J) sum(t in EF[j]..LF[j]) (t + d[j] - 1) * x[j][t];
minimize project_completion_time;

subject to {
  // Each task starts exactly once within its EF-LF window
  forall(j in J)
    sum(t in EF[j]..LF[j]) x[j][t] == 1;
  
  // Precedence constraints: j starts after its predecessor i finishes
  forall(j in J: P[j] != 0) {
    let i = P[j];
    sum(t in EF[j]..LF[j]) t * x[j][t] >= sum(t in EF[i]..LF[i]) (t + d[i] - 1) * x[i][t];
  }
  
  // Resource constraints: No resource is overused at any time t
  forall(r in R, t in 1..Tbar) {
    sum(j in J) u[j][r] * sum(q in max(EF[j], t - d[j] + 1)..min(LF[j], t)) x[j][q] <= a[r];
  }
}

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