如何在OR-Tools的Job Shop模型中添加机器停机时间约束？

问题背景 #

正在学习Google OR-Tools的Job Shop调度教程，需要为任务添加额外约束：作业不得在机器停机时段内加工。例如机器2在时间单位3到5期间停机。使用版本：ortools 9.3.10497，Python 3.7.0。

无效尝试 #

最初尝试的写法逻辑矛盾，无法同时满足约束：

if machine == 2:
    model.Add(all_tasks[job_id, task_id].start > 0)
    model.Add(all_tasks[job_id, task_id].end < 3)
    model.Add(all_tasks[job_id, task_id].start > 5)

这段代码同时要求任务结束时间小于3且开始时间大于5，没有可行解。

想要实现“任务在停机前完成或停机后开始”的逻辑约束，但直接写逻辑表达式会报错（提示需要有界线性表达式）：

if machine == 2:
    model.Add((all_tasks[job_id, task_id].start > 0 and all_tasks[job_id, task_id].end < 3) or all_tasks[job_id, task_id].start > 5)

解决方案 #

CP-SAT求解器不支持直接的逻辑and/or约束，需要通过布尔变量将逻辑条件线性化。针对机器2的3-5停机时段，我们需要确保任务要么在停机前完成（end ≤ 2），要么在停机后开始（start ≥ 6），具体实现步骤如下：

1. 定义布尔变量：为每个分配到机器2的任务创建两个布尔变量，分别表示任务是否在停机前完成、是否在停机后开始。
2. 约束二选一：确保两个布尔变量至少有一个为真（即两种情况必选其一）。
3. 关联布尔变量与时间约束：用CP-SAT提供的便捷方法或大M法，将布尔变量和任务的开始/结束时间绑定，实现逻辑条件的线性转化。

代码示例 #

# 假设all_tasks是已定义的任务字典，model是CP-SAT模型
# 定义一个足够大的M值（可根据问题最大可能时间设置，比如1000）
M = 1000

for job_id in range(num_jobs):
    for task_id in range(num_tasks):
        machine = ...  # 获取当前任务分配的机器
        if machine == 2:
            task = all_tasks[job_id, task_id]
            # 创建布尔变量
            before_shutdown = model.NewBoolVar(f"before_shutdown_job{job_id}_task{task_id}")
            after_shutdown = model.NewBoolVar(f"after_shutdown_job{job_id}_task{task_id}")
            
            # 约束：必须满足其中一种情况
            model.Add(before_shutdown + after_shutdown == 1)
            
            # 约束1：如果before_shutdown为真，任务必须在停机前完成（end ≤ 2）
            model.Add(task.end <= 2).OnlyEnforceIf(before_shutdown)
            # 等价大M写法：
            # model.Add(task.end <= 2 + M * (1 - before_shutdown))
            
            # 约束2：如果after_shutdown为真，任务必须在停机后开始（start ≥ 6）
            model.Add(task.start >= 6).OnlyEnforceIf(after_shutdown)
            # 等价大M写法：
            # model.Add(task.start >= 6 - M * (1 - after_shutdown))

说明 #

• OnlyEnforceIf()是CP-SAT提供的便捷方法，用于实现“当布尔变量为真时才激活约束”的逻辑，比手动写大M更简洁易读。
• 大M值需要设置为足够大的常数，确保在布尔变量为假时，约束不会限制任务的正常调度。

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