基于PuLP库的MS-RCPSP模型优化：单资源多技能分配需求

我正在开发基于PuLP库的MS-RCPSP（多技能资源约束项目调度问题）Python代码，需针对特定场景优化：当某活动需要1名具备技能1的资源和1名具备技能2的资源时，若存在同时掌握这两种技能的单一资源，应优先分配该资源而非两名独立资源。我尝试移除约束x[i][j][k] ≤1（对应约束图4），但未达到预期效果。现有代码运行正常，需为其添加该新功能。

当前代码 #

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] * B[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:
        model += s[i] + p[i] - M * (1 - z[i][i_prime]) * (1 - Prec[i][i_prime]) <= s[i_prime], f"Precedence_{i}_{i_prime}"
        if 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}")

相关约束图示 #

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