基于PuLP库的MS-RCPSP模型任务分配异常排查求助

我使用PuLP库编写Python脚本求解多技能资源约束项目调度问题（MS-RCPSP），但任务分配输出结果与预期结果不一致，恳请协助排查问题原因。

预期结果说明 #

预期调度结果如下：

• 任务1（时长5）：需1个技能1资源、2个技能2资源，分配资源1（掌握技能1/2）、资源2（掌握技能2）、资源3（掌握技能1），开始时间0，结束时间5
• 任务2（时长10）：需1个技能1资源，分配资源3，开始时间0，结束时间10
• 任务3（时长5）：需1个技能1、1个技能2资源，分配资源1、资源2，开始时间5，结束时间10
• 任务4（时长10）：需1个技能2资源，分配资源4（掌握技能2），开始时间0，结束时间10
• 任务5（时长5）：需1个技能1、1个技能2资源，分配资源3、资源2，开始时间10，结束时间15
  整体最大完工时间为15。

求解代码 #

import pulp as pl

# Problem Setup
model = pl.LpProblem("Task_Scheduling", pl.LpMinimize)

# Sets
Nr = range(5)  # Tasks
Rr = range(4)  # Resources
Sr = range(2)  # Skills
Kr = range(4)  # Resources skill levels
Ir = range(5)  # Tasks
Jr = range(2)  # Task skills
M = 20

# Data
Prec = [
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

p = [5, 10, 5, 10, 5]  # Duration of each task

R = [
    [1, 2],
    [1, 0],
    [1, 1],
    [0, 1],
    [1, 1]
]

B = [
    [1, 0, 1, 1],
    [1, 1, 0, 0]
]

# Decision Variables
x = pl.LpVariable.dicts("x", (Ir, Jr, Kr), cat=pl.LpBinary)
z = pl.LpVariable.dicts("z", (Ir, Ir), cat=pl.LpBinary)
s = pl.LpVariable.dicts("s", Ir, cat=pl.LpContinuous, lowBound=0)
C_max = pl.LpVariable("C_max", lowBound=0, cat=pl.LpContinuous)

# Objective Function
model += C_max, "Minimize_Max_Completion_Time"

# Constraints for max completion time
for j in Nr:
    model += C_max >= s[j] + p[j], f"Max_Completion_Time_{j}"

# Skill requirements
for i in Nr:
    for j in Sr:
        model += pl.lpSum(x[i][j][k] for k in Rr) == R[i][j], f"Skill_Requirement_{i}_{j}"

# Precedence and non-overlap constraints
for i in Nr:
    for i_prime in Nr:
        if i < i_prime:
            model += s[i] + p[i] - M * (1 - z[i][i_prime]) * (1 - Prec[i][i_prime]) <= s[i_prime], f"Precedence_{i}_{i_prime}"
            model += z[i][i_prime] + z[i_prime][i] <= 1, f"Non_Overlap_{i}_{i_prime}"

# Resource constraints
for i in Nr:
    for k in Rr:
        model += pl.lpSum(x[i][j][k] for j in Sr) <= 1, f"One_Skill_Per_Resource_{i}_{k}"

# Resource sharing constraints
for i in Nr:
    for i_prime in Nr:
        if i < i_prime:
            for k in Rr:
                model += pl.lpSum(x[i][j][k] for j in Sr) + pl.lpSum(x[i_prime][j][k] for j in Sr) <= 1 + z[i][i_prime] + z[i_prime][i], f"No_Simultaneous_Assignment_{i}_{i_prime}_{k}"

# Skill level matching
for i in Nr:
    for j in Sr:
        for k in Rr:
            model += x[i][j][k] <= B[j][k], f"Skill_Level_Match_{i}_{j}_{k}"

# Solve the model
model.solve()
print("Status:", pl.LpStatus[model.status])
print("Maximum completion time:", pl.value(C_max))

# Display assignment results and timing for each task
for i in Nr:
    start_time = pl.value(s[i])
    finish_time = start_time + p[i]
    print(f"Activity {i+1} starts at time {start_time} and finishes at time {finish_time}.")
    for j in Sr:
        for k in Rr:
            if pl.value(x[i][j][k]) == 1:
                print(f"Resource {k+1} is assigned to skill {j+1} for activity {i+1}")

可能的问题点排查 #

• 集合定义冗余：代码中重复定义了任务集合（Nr和Ir）、技能集合（Sr和Jr），虽逻辑上不影响，但易引发变量引用混淆，建议统一集合命名，降低出错概率。
• 前驱与非重叠约束逻辑缺陷：当前将两类约束合并的写法存在问题：
  • 前驱约束部分：当Prec[i][i_prime] = 1时，能正确强制s[i]+p[i] <= s[i_prime]，但非重叠约束对所有i < i'生效，会导致无资源冲突的任务也被强制不能重叠，限制调度灵活性。
  • 正确做法：拆分两类约束，单独处理Prec[i][i_prime] == 1的前驱关系，仅当两个任务共享资源时，再添加非重叠约束。
• 资源共享约束逻辑错误：当前约束无法有效阻止同一资源被同时分配给两个任务。当同一资源k被分配给任务i和i'时，约束左边为2，右边最多为1 + 1 + 0 = 2（z变量最多一个为1），约束成立，无法限制冲突。正确的约束应通过大M法强制时间不重叠：

  for i in Nr:
      for i_prime in Nr:
          if i != i_prime:
              for k in Rr:
                  # 如果资源k同时分配给i和i'，则i必须在i'之前完成，或反之
                  model += s[i] + p[i] <= s[i_prime] + M * (2 - pl.lpSum(x[i][j][k] for j in Sr) - pl.lpSum(x[i_prime][j][k] for j in Sr))
                  model += s[i_prime] + p[i_prime] <= s[i] + M * (2 - pl.lpSum(x[i][j][k] for j in Sr) - pl.lpSum(x[i_prime][j][k] for j in Sr))
  

• 技能需求与资源匹配验证：需确认R矩阵（任务技能需求）和B矩阵（资源技能掌握情况）的数值是否完全符合预期，比如任务1的[1,2]是否确实对应1个技能1、2个技能2资源，B矩阵中资源的技能标记是否正确。

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