单机器加权延迟最小化调度：Gurobi模型结果劣于OpenSolver求助

你的Gurobi模型存在几个关键错误，导致结果次优，以下是问题分析和修正后的代码：

核心问题点 #

1. 权重变量定义错误：原代码中weight = {j: w[j] for j in range(N)}直接把原作业权重列表的第j个值赋值给序列j的权重，这完全错误——序列j的权重应该是分配到该序列的作业的权重，必须通过二进制变量x[i,j]关联，而非固定取值。
2. 目标函数冗余且错误：用额外的goal变量加<=约束完全没必要，直接以加权 tardiness 总和为目标即可，且原代码中用错误的weight[j]计算加权，导致目标值偏差。
3. 序列0的 tardiness 约束错误：单独添加T[0] >= C[0] - d[0]强制序列0的作业对应i=0的截止日期，忽略了x[i,0]的分配逻辑，导致约束冲突。

修正后的代码 #

import gurobipy as gp

N = 15  # number of jobs

# w: weights of jobs
w = [1, 10, 9, 10, 10, 4, 3, 2, 10, 3, 7, 3, 1, 3, 10]

# p: process time of jobs
p = [26, 24, 79, 46, 32, 35, 73, 74, 14, 67, 86, 46, 78, 40, 29]

# d: due dates of jobs
d = [397, 405, 433, 443, 424, 372, 392, 461, 432, 409, 400, 385, 464, 411, 427]

# Create a new model
m = gp.Model()
x = {}

# T: Tardiness of job in sequence j
T = m.addVars(N, lb=0, vtype=gp.GRB.CONTINUOUS)
# C: Completion time of sequence j (total time up to and including sequence j)
C = m.addVars(N, vtype=gp.GRB.CONTINUOUS)
# K: Processing time of job assigned to sequence j
K = m.addVars(N, vtype=gp.GRB.CONTINUOUS)
# W: Weight of job assigned to sequence j
W = m.addVars(N, vtype=gp.GRB.CONTINUOUS)

# x[i,j]: 1 if Job i is assigned to Sequence j, 0 otherwise
for i in range(N):
    for j in range(N):
        x[i,j] = m.addVar(vtype=gp.GRB.BINARY)

# Set objective function: Minimize total weighted tardiness
m.setObjective(gp.quicksum(W[j] * T[j] for j in range(N)), gp.GRB.MINIMIZE)

# Constraints
# 1. Each job is assigned to exactly one sequence
for i in range(N):
    m.addConstr(gp.quicksum(x[i,j] for j in range(N)) == 1)

# 2. Each sequence has exactly one job
for j in range(N):
    m.addConstr(gp.quicksum(x[i,j] for i in range(N)) == 1)

# 3. Processing time for sequence j is the processing time of the assigned job
for j in range(N):
    m.addConstr(gp.quicksum(p[i] * x[i,j] for i in range(N)) == K[j])

# 4. Weight for sequence j is the weight of the assigned job
for j in range(N):
    m.addConstr(gp.quicksum(w[i] * x[i,j] for i in range(N)) == W[j])

# 5. Completion time calculation: C[j] = C[j-1] + K[j]
m.addConstr(C[0] == K[0])
for j in range(1, N):
    m.addConstr(C[j] == C[j-1] + K[j])

# 6. Tardiness definition: T[j] >= completion time - due date of assigned job
for j in range(N):
    m.addConstr(T[j] >= C[j] - gp.quicksum(d[i] * x[i,j] for i in range(N)))

# Solve the problem
m.optimize()

# Print solution
print('Optimal objective value: %g' % m.objVal)
print('Job sequence (sequence index -> job index):')
for j in range(N):
    for i in range(N):
        if x[i,j].X > 0.5:
            print(f'Sequence {j}: Job {i} (p={p[i]}, w={w[i]}, d={d[i]})')

关键修正说明 #

• 新增W[j]变量存储序列j对应作业的权重，通过x[i,j]动态关联，而非固定取值。
• 直接以sum(W[j]*T[j])为目标函数，去掉冗余的goal变量。
• 删除错误的T[0] >= C[0] - d[0]约束，统一使用基于x[i,j]的截止日期关联逻辑。
• 优化输出格式，直接打印序列对应的作业信息，便于验证。

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