如何在OR-Tools中实现最多N个约束？Job Shop多机调度需求

核心需求实现思路 #

针对多台相同型号机器（如2台Machine1），要确保任意时刻该类型机器的并发使用数量不超过机器总数，推荐使用OR-Tools的累积资源约束（Cumulative Constraint）——这是专门为调度场景中资源容量限制设计的高效约束，比遍历时间点加求和约束更优。

具体实现步骤及代码示例 #

1. 定义机器类型与容量
   先明确各机器类型的可用数量：

   # key是机器类型ID，value是该类型机器的总数
   machine_capacities = {1: 2}  # Machine1有2台可用
   

2. 收集对应机器类型的所有操作并添加约束
   遍历所有作业的操作，筛选出需要使用目标机器类型的任务，整理成(开始时间变量, 持续时间, 资源占用量)的元组列表（每个任务占用1台机器，所以资源占用量为1），再添加累积约束：

   # 假设已定义：
   # start_var[job][op]：每个操作的开始时间变量
   # duration[job][op]：每个操作的持续时间
   # machine_type[job][op]：标记该操作对应的机器类型ID
   # num_jobs：作业总数
   # num_ops_per_job：每个作业的操作数
   
   for machine_type_id, capacity in machine_capacities.items():
       operations = []
       for job in range(num_jobs):
           for op in range(num_ops_per_job):
               if machine_type[job][op] == machine_type_id:
                   operations.append(
                       (start_var[job][op], duration[job][op], 1)
                   )
       # 添加累积约束，限制并发使用数量不超过机器容量
       model.AddCumulative(operations, capacity)
   

3. 替代方案（不推荐）：时间点求和约束
   如果不想用累积约束，也可以遍历所有可能的时间点，对该时刻正在运行的任务数量求和并限制上限，但这种方式效率较低，仅适合小规模调度场景：

   max_time = sum(max(job_durations) for job_durations in duration)  # 估算最大可能调度时间
   for machine_type_id, capacity in machine_capacities.items():
       for t in range(max_time):
           active_ops = []
           for job in range(num_jobs):
               for op in range(num_ops_per_job):
                   if machine_type[job][op] == machine_type_id:
                       # 定义布尔变量标记操作是否在t时刻运行
                       is_active = model.NewBoolVar(f"active_job{job}_op{op}_t{t}")
                       # 添加逻辑约束：变量为真时，操作正在t时刻运行
                       model.Add(start_var[job][op] <= t).OnlyEnforceIf(is_active)
                       model.Add(t < start_var[job][op] + duration[job][op]).OnlyEnforceIf(is_active)
                       # 变量为假时，操作不在t时刻运行
                       model.Add(start_var[job][op] > t).OnlyEnforceIf(is_active.Not())
                       model.Add(t >= start_var[job][op] + duration[job][op]).OnlyEnforceIf(is_active.Not())
                       active_ops.append(is_active)
           # 限制t时刻活跃操作数不超过机器容量
           model.Add(sum(active_ops) <= capacity)
   

关键说明 #

• 累积约束AddCumulative会自动处理所有时间区间的资源占用情况，确保任意时刻资源使用量不超过设定的容量，是调度场景下的最优选择。
• 无需使用原教程中的AddExactlyOne约束，因为多台同类型机器允许同一时刻多个任务并行执行，只要总数不超过机器数量即可。

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