如何在OR-Tools灵活作业车间中添加机器-作业时段约束？

针对灵活作业车间调度场景，要给特定作业在指定机器上添加可执行时段限制，核心思路是通过布尔变量+条件约束，将作业的执行区间绑定到允许的时段内。以下是分步实现方案：

一、单机器基线场景实现 #

核心逻辑 #

1. 为每个作业-机器对定义是否选择该机器执行的布尔变量。
2. 为每个允许的时段创建布尔变量，控制作业是否落在该时段内。
3. 通过OnlyEnforceIf关联变量，确保只有选择该机器时，时段约束才生效。

代码示例（Python） #

from ortools.sat.python import cp_model

def main():
    model = cp_model.CpModel()
    
    # 基础调度数据：每个作业的可选机器及对应加工时长
    jobs_data = [
        [(0, 5)],  # 作业0：仅可选机器0，时长5
        [(0, 4)],  # 作业1：仅可选机器0，时长4
    ]
    
    # 作业-机器专属时段限制：{作业ID: {机器ID: [(允许开始时间, 允许结束时间), ...]}}
    allowed_time_windows = {
        0: {0: [(0, 10), (15, 20)]},  # 作业0在机器0上只能在0-10或15-20执行
        1: {0: [(2, 8)]}               # 作业1在机器0上只能在2-8执行
    }
    
    machines_count = 1
    all_machines = range(machines_count)
    
    # 创建调度变量：开始时间、结束时间、是否选择该机器
    job_starts = {}
    job_ends = {}
    job_machine_selected = {}
    
    for job_id, job in enumerate(jobs_data):
        for machine_id, duration in job:
            suffix = f"job_{job_id}_machine_{machine_id}"
            start_var = model.NewIntVar(0, 100, f"start_{suffix}")
            end_var = model.NewIntVar(0, 100, f"end_{suffix}")
            selected_var = model.NewBoolVar(f"selected_{suffix}")
            
            job_starts[(job_id, machine_id)] = start_var
            job_ends[(job_id, machine_id)] = end_var
            job_machine_selected[(job_id, machine_id)] = selected_var
            
            # 基础时长约束：结束时间 = 开始时间 + 加工时长（仅选择该机器时生效）
            model.Add(end_var == start_var + duration).OnlyEnforceIf(selected_var)
    
    # 约束1：每个作业必须选择一台机器执行（单机器场景下必选唯一机器）
    for job_id in range(len(jobs_data)):
        model.Add(sum(job_machine_selected[(job_id, m)] for m in all_machines) == 1)
    
    # 约束2：机器上的作业不能重叠
    for machine_id in all_machines:
        machine_jobs = []
        for job_id in range(len(jobs_data)):
            for (m, _) in jobs_data[job_id]:
                if m == machine_id:
                    machine_jobs.append((job_starts[(job_id, m)], job_ends[(job_id, m)], job_machine_selected[(job_id, m)]))
        model.AddNoOverlap([(s, e, sel) for s, e, sel in machine_jobs])
    
    # 约束3：添加作业-机器的时段限制
    for job_id in allowed_time_windows:
        for machine_id in allowed_time_windows[job_id]:
            time_windows = allowed_time_windows[job_id][machine_id]
            selected_var = job_machine_selected[(job_id, machine_id)]
            start_var = job_starts[(job_id, machine_id)]
            end_var = job_ends[(job_id, machine_id)]
            
            # 为每个允许时段创建布尔变量
            window_flags = []
            for idx, (win_start, win_end) in enumerate(time_windows):
                flag = model.NewBoolVar(f"window_{job_id}_{machine_id}_{idx}")
                window_flags.append(flag)
                
                # 作业完全落在该时段内的约束（仅当前时段被选中时生效）
                model.Add(start_var >= win_start).OnlyEnforceIf(flag)
                model.Add(end_var <= win_end).OnlyEnforceIf(flag)
            
            # 选择该机器时，必须选中一个允许时段；不选择时，所有时段 flag 置0
            model.Add(sum(window_flags) == 1).OnlyEnforceIf(selected_var)
            model.Add(sum(window_flags) == 0).OnlyEnforceIf(selected_var.Not())
    
    # 目标：最小化最大完工时间
    makespan_var = model.NewIntVar(0, 100, "makespan")
    model.AddMaxEquality(makespan_var, [job_ends[(j, m)] for j, m in job_ends])
    model.Minimize(makespan_var)
    
    # 求解并输出结果
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        print(f"最小完工时间: {solver.Value(makespan_var)}")
        for job_id in range(len(jobs_data)):
            for machine_id in all_machines:
                if solver.Value(job_machine_selected[(job_id, machine_id)]) == 1:
                    print(f"作业{job_id} 在机器{machine_id}上执行：开始={solver.Value(job_starts[(job_id, machine_id)])}, 结束={solver.Value(job_ends[(job_id, machine_id)])}")

if __name__ == "__main__":
    main()

关键说明 #

• OnlyEnforceIf是核心：它让约束仅在布尔变量为真时生效，完美适配“选了该机器才需要遵守时段限制”的逻辑。
• 时段约束确保作业完全落在允许区间内，避免跨时段执行。
• 如果作业在某台机器上无时段限制，只需不在allowed_time_windows中配置即可，代码会自动跳过该约束。

二、多机器场景拓展 #

多机器场景不需要修改核心约束逻辑，只需调整基础数据即可：

1. 在jobs_data中为作业添加更多可选机器及对应时长。
2. 在allowed_time_windows中补充新增机器的时段限制。
3. 代码中的机器无重叠约束会自动遍历所有机器，处理多机器的作业冲突问题。

例如，修改jobs_data和allowed_time_windows为：

jobs_data = [
    [(0, 5), (1, 6)],  # 作业0：可选机器0（时长5）、机器1（时长6）
    [(0, 4), (1, 3)],  # 作业1：可选机器0（时长4）、机器1（时长3）
]

allowed_time_windows = {
    0: {
        0: [(0, 10), (15, 20)],
        1: [(5, 15)]
    },
    1: {
        0: [(2, 8)],
        1: [(0, 5), (10, 18)]
    }
}

其余代码无需修改，即可实现多机器下的作业时段约束。

注意事项 #

• 确保允许时段的长度≥作业在该机器上的加工时长，否则会导致模型无解。
• 若时段数量较多，布尔变量的增加会提升模型复杂度，可根据实际情况调整求解器参数（如 solver.parameters.max_time_in_seconds = 60）来控制求解时间。

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