使用 PuLP 库的数学模型问题

Question

我使用 PuLP 库创建了一个 Python 脚本来解决多技能资源受限的项目调度问题 (MS-RCPSP)，但我遇到了任务分配问题。我得到的输出与图 1 中所示的预期结果不匹配。你能帮我理解出了什么问题吗？

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}")

Answer 1

我认为您没有正确编码资源需求约束（等式 2）。

当我阅读代码时，它并没有强制要求资源

k

具有技能

j

，因此您在活动 4 的结果中得到了非法分配。

所以有两种方法可以做到这一点......

一：将变量乘以来自

B

的二进制参数，如下所示：

# 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}"

这是线性的，并且通过检查，只有当

B[j][k]

为 1 时才能记入资源需求。

第二种方法是使用不同的技能创建

x

变量的子集，并从适当的子集中提取以进行等式约束。或者在带有条件的求和中执行此操作，以便仅考虑适当的

x

。净效应是一样的。制作子集可能会产生稍微更紧凑的模型。

当我执行上述操作时，我注意到资源分配有重叠...我注意到，在您的优先级约束中，我认为您缩短了主要部分等式 3 的迭代，这应该为所有人完成

i, i' 

。将条件下移，使其仅适用于第二个方程：

# 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}"

这似乎有效并产生了高质量的答案。似乎存在多个最佳解决方案（因为资源 3 和 4 可以互换，所以一定存在），因为这略有不同，但似乎合法。请注意，我还打印了

z

矩阵，以便使用此附录对您的代码进行验证：

# 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}")
    for ii in Nr:
        print(pl.value(z[i][ii]), end = ' ')
    print()
    print()

输出：

Status: Optimal
Maximum completion time: 15.0
Activity 1 starts at time 0.0 and finishes at time 5.0.
Resource 4 is assigned to skill 1 for activity 1
Resource 1 is assigned to skill 2 for activity 1
Resource 2 is assigned to skill 2 for activity 1
0.0 0.0 1.0 1.0 1.0 

Activity 2 starts at time 0.0 and finishes at time 10.0.
Resource 3 is assigned to skill 1 for activity 2
0.0 0.0 0.0 0.0 1.0 

Activity 3 starts at time 5.0 and finishes at time 10.0.
Resource 4 is assigned to skill 1 for activity 3
Resource 1 is assigned to skill 2 for activity 3
0.0 0.0 0.0 0.0 1.0 

Activity 4 starts at time 5.0 and finishes at time 15.0.
Resource 2 is assigned to skill 2 for activity 4
0.0 0.0 0.0 0.0 0.0 

Activity 5 starts at time 10.0 and finishes at time 15.0.
Resource 4 is assigned to skill 1 for activity 5
Resource 1 is assigned to skill 2 for activity 5
0.0 0.0 0.0 0.0 0.0