如何用Python Pulp实现无循环单机调度（含截止日期约束）

问题背景 #

我需要在不使用循环的前提下，用Python Pulp库实现单机调度（瓶颈优化），验证两个任务的可行调度方案：

• task1：时长1小时，截止日期1小时
• task2：时长3小时，截止日期4小时

已知存在两种调度方案：一种因task1违反截止日期不可行，另一种满足所有截止日期要求。但现有代码求解结果不符合预期，无法正确添加截止日期约束，且不想引入权重等额外参数。该问题属于总 tardiness 最小化问题，需指导添加合适的约束。

核心建模思路 #

针对两个任务的场景，直接显式定义变量和约束（无需循环）：

1. 用二进制变量控制任务执行顺序
2. 定义任务的开始/完成时间变量
3. 用大M法线性化顺序约束
4. 关联完成时间与截止日期，定义tardiness变量
5. 以最小化总tardiness为目标，让求解器自动找到可行方案

修正后的代码实现 #

import pulp

# 创建问题：最小化总 tardiness
prob = pulp.LpProblem("Single_Machine_Scheduling", pulp.LpMinimize)

# 变量定义
# x=1: task1在task2前执行；x=0: task2在task1前执行
x = pulp.LpVariable("x", cat='Binary')
# 任务开始时间（非负）
s1 = pulp.LpVariable("s1", lowBound=0, cat='Continuous')
s2 = pulp.LpVariable("s2", lowBound=0, cat='Continuous')
# 任务完成时间
c1 = pulp.LpVariable("c1", lowBound=0, cat='Continuous')
c2 = pulp.LpVariable("c2", lowBound=0, cat='Continuous')
# Tardiness变量（非负，完成时间超截止日期时为正）
t1 = pulp.LpVariable("t1", lowBound=0, cat='Continuous')
t2 = pulp.LpVariable("t2", lowBound=0, cat='Continuous')

# 目标函数：最小化总 tardiness
prob += t1 + t2, "Total_Tardiness"

# 1. 任务时长约束
prob += c1 == s1 + 1, "Task1_Duration"
prob += c2 == s2 + 3, "Task2_Duration"

# 2. 顺序约束（大M法线性化，M取足够大的数，这里总时长4，取10足够）
M = 10
# 若x=1（task1先），则s2 >= c1；否则约束自动失效
prob += s2 >= c1 - M*(1 - x), "Task1_Before_Task2"
# 若x=0（task2先），则s1 >= c2；否则约束自动失效
prob += s1 >= c2 - M*x, "Task2_Before_Task1"

# 3. 截止日期与Tardiness约束
prob += t1 >= c1 - 1, "Task1_Tardiness"
prob += t2 >= c2 - 4, "Task2_Tardiness"

# 求解（关闭日志输出）
prob.solve(pulp.PULP_CBC_CMD(msg=0))

# 输出结果
print("求解状态:", pulp.LpStatus[prob.status])
print("task1是否先执行？", "是" if pulp.value(x) == 1 else "否")
print("task1: 开始时间={:.1f}, 完成时间={:.1f}, tardiness={:.1f}".format(
    pulp.value(s1), pulp.value(c1), pulp.value(t1)
))
print("task2: 开始时间={:.1f}, 完成时间={:.1f}, tardiness={:.1f}".format(
    pulp.value(s2), pulp.value(c2), pulp.value(t2)
))

关键约束说明 #

• 顺序约束：通过大M法将逻辑判断转化为线性约束，避免循环，直接针对两个任务的顺序关系显式定义
• 截止日期约束：tardiness变量确保当任务完成时间超过截止日期时，目标函数会惩罚这种情况，求解器会优先选择tardiness为0的可行方案（即task1先执行：0-1完成，task2 1-4完成，刚好满足所有截止日期）
• 无循环实现：针对2个任务的场景，直接写出所有变量和约束，无需遍历任务列表

补充说明 #

• 若仅需验证可行解（不关心tardiness最小化），可将目标函数改为prob += 0，或添加约束t1 == 0和t2 == 0后求解可行性
• Moore/Hodgson算法是该问题的启发式求解方法，而用Pulp是通过整数规划建模直接精确求解，无需手动实现算法

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