基于CPLEX的OPL实现RCPSP：多前置任务适配问题

已完成支持单前置任务的RCPSP模型且运行正常，现在适配多前置版本时遇到问题，以下是原模型代码和修改后存在问题的版本：

原单前置任务RCPSP模型代码 #

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

// Resource usage matrix
int u[J][R] = [[2],[5],[5],[5]]; 

// Resource availability
int a[R]= [10];

// 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)
    ct1:sum (t in EF[j]..LF[j]) x[j][t] == 1;
  forall(j in J: P[j] != 0) // assuming 0 indicates no predecessor
    ct2:sum (t in EF[j]..LF[j]) x[j][t] * t >=
        sum (t in EF[P[j]]..LF[P[j]]) x[P[j]][t] * (t + d[P[j]]);
  forall(r in R, t in 1..Tbar) {
    ct3:sum(j in J) u[j][r] * sum(q in maxl(t, EF[j])..minl(t + d[j] - 1, LF[j])) x[j][q] <= a[r];
  }
}

修改后存在问题的多前置任务RCPSP模型代码 #

// Example data
range J = 1..10;
range R = 1..2;
range T = 1..10;
{int} Tasks =asSet(1..10);
setof(int) P[Tasks] = [{0}, {1}, {2}, {1}, {4,3}, {4,3}, {4,3}, {6}, {8}, {5,7,9}];

int d[J] = [7, 3, 1, 8, 2, 1, 1, 2, 2, 1];
int EF[J] = [0, 7, 10, 7, 15, 15, 15, 16, 18, 20];
int LF[J] = [0, 11, 14, 7, 18, 15, 19, 16, 18, 20];
int Tbar = sum(j in J) d[j];

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

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

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

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

subject to {
  forall(j in J)
    ct1:sum (t in EF[j]..LF[j]) x[j][t] == 1;
  forall(j in J: P[Tasks]!= 0) // assuming 0 indicates no predecessor
        ct2:sum (t in EF[j]..LF[j]) x[j][t] * t >=
             sum (t in EF[P[Tasks]]..LF[P[Tasks]]) x[P[Tasks]][t] * (t + d[P[Tasks]]); 
  forall(r in R, t in 1..Tbar) {
    ct3:sum(j in J) u[j][r] * sum(q in maxl(t, EF[j])..minl(t + d[j] - 1, LF[j])) x[j][q] <= a[r];
  }
}

问题分析与修正方案 #

核心问题点 #

1. 前置任务遍历逻辑错误：forall(j in J: P[Tasks]!= 0)无效，P[Tasks]返回所有任务的前置集合，而非当前任务j的前置集合，正确做法是针对每个任务j，遍历其自身的前置集合P[j]并排除代表无前置的0元素。
2. ct2约束逻辑错误：多前置任务要求任务j的开始时间必须晚于所有前置任务的完成时间，原代码的求和逻辑会错误累加前置任务时间，导致约束失效，需为每个前置任务单独添加约束。
3. 时间范围不匹配：修改后的T = 1..10，但部分任务EF[j]为0，会导致sum(t in EF[j]..LF[j]:t in T)漏掉t=0的合法时间点，需调整T范围或确保时间筛选逻辑正确。

修正后的代码 #

// Example data
range J = 1..10;
range R = 1..2;
// 调整T范围包含0，覆盖所有任务的时间窗口
range T = 0..20;
{int} Tasks = asSet(1..10);
setof(int) P[Tasks] = [{0}, {1}, {2}, {1}, {4,3}, {4,3}, {4,3}, {6}, {8}, {5,7,9}];

int d[J] = [7, 3, 1, 8, 2, 1, 1, 2, 2, 1];
int EF[J] = [0, 7, 10, 7, 15, 15, 15, 16, 18, 20];
int LF[J] = [0, 11, 14, 7, 18, 15, 19, 16, 18, 20];
int Tbar = sum(j in J) d[j];

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

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

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

// 计算项目完工时间，确保仅在定义的时间范围内统计
dexpr int CT = sum(j in J, t in EF[j]..LF[j]: t in T) t * x[j][t];
minimize CT;

subject to {
  // 每个任务必须在其时间窗口内选择一个开始时间
  forall(j in J)
    ct1: sum(t in EF[j]..LF[j]: t in T) x[j][t] == 1;
  
  // 多前置任务约束：每个非0前置任务完成后，当前任务才能开始
  forall(j in J, p in P[j]: p != 0)
    ct2: sum(t in EF[j]..LF[j]: t in T) t * x[j][t] >= 
         sum(t in EF[p]..LF[p]: t in T) (t + d[p]) * x[p][t];
  
  // 资源约束保持不变，添加时间范围筛选
  forall(r in R, t in 1..Tbar) {
    ct3: sum(j in J) u[j][r] * sum(q in maxl(t, EF[j])..minl(t + d[j] - 1, LF[j]): q in T) x[j][q] <= a[r];
  }
}

修正说明 #

• 调整T范围为0..20，覆盖所有任务的EF和LF时间点，避免筛选时漏掉合法时间。
• 重构ct2约束：遍历每个任务j的每个非0前置任务p，单独约束j的开始时间不早于p的完成时间（p的开始时间+p的持续时间），确保所有前置任务完成后j才能开始。
• 所有时间求和操作添加t in T筛选，确保仅在定义的时间范围内计算。

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