如何在 Google OR-Tools 中添加约束来限制（在作业车间问题的示例中）可以同时活动的作业数量？

Question

在作业车间问题的示例中（https://developers.google.com/optimization/scheduling/job_shop），优化结果表明要优化的所有三个作业从时间 3 到时间同时处于活动状态8. 我要解决的问题是，同时激活的作业数量不能超过一定数量。

我尝试将这些约束添加到作业车间代码中：

for job_id1, job1 in enumerate(jobs_data):
        model.Add(
            sum(
                [
                    model.NewBoolVar(f"""{
                        all_tasks[job_id1, len(job1)-1].end} > {all_tasks[job_id2, 0].start
                    }""") 
                    for job_id2, job2 in enumerate(jobs_data)
                ]
                +
                [
                    model.NewBoolVar(f"""{
                        all_tasks[job_id1, 0].start} < {all_tasks[job_id2, len(job2)-1].end
                    }""") 
                    for job_id2, job2 in enumerate(jobs_data)
                ]                
            ) <= 2
        )

从语法的角度来看，它们是正确的（因此它们不会返回任何错误消息），但对模拟结果没有影响，模拟结果仍然保持不变，也就是说（我得到的解决方案与存在于工作车间帖子中的一个）：

    Solution:
    Optimal Schedule Length: 11.0
    Machine 0: job_1_task_0   job_0_task_0   
               [0,2]          [2,5]          
    Machine 1: job_2_task_0   job_0_task_1   job_1_task_2   
               [0,4]          [5,7]          [7,11]         
    Machine 2: job_1_task_1   job_2_task_1   job_0_task_2   
               [2,3]          [4,7]          [7,9]

虽然我想要这样的解决方案：

    Solution:
    Optimal Schedule Length: 14.0
    Machine 0: job_1_task_0   job_0_task_0   
               [0,2]          [7,10]          
    Machine 1: job_2_task_0   job_1_task_2   job_0_task_1      
               [0,4]          [4,8]          [10,12]         
    Machine 2: job_1_task_1   job_2_task_1   job_0_task_2   
               [2,3]          [4,7]          [12,14]

其中作业 0 仅在作业 2 完成后才开始，从而确保同时活动的作业不超过两个（显然这意味着总时间从 11 增加到 14，但在我的实际问题中，我必须决定我有义务这样做）。

我的想法是将每个作业与所有其他作业进行比较，对于每个作业（我们称之为“job_id1”），如果最后一个任务的结束时间大于另一个作业的第一个任务的开始时间或他的开始时间第一个任务大于同一其他作业的最后一个任务的结束时间，因此我在列表中以布尔变量的形式添加 1（我必须使用 NewBoolVar 的原因在这篇文章如何使用 CpModel 使 1D 数组中出现三个 1？（或工具））。当列表已满时，我对列表中所有 1 进行求和，这可以衡量作业“job_id1”上叠加了多少个作业，并且我强制要求该总和必须小于或等于某个值，例如 2。理论上为所有作业添加此约束应该确保同时活动的作业数量永远不会超过 N 个。

任何建议都非常感谢，谢谢大家。

====================================================== ================

更新：

感谢@sascha和Hakan Kjellerstrand (http://www.hakank.org/google_or_tools/)，特别是示例http://hakank.org/or_tools/furniture_moving_add_cumulative_sat.py，我替换了前一种方法与以下基于 AddCumulative 约束的方法

n = 3
duration = [7, 7, 7]
demand = [1, 1, 1]
upper_limit = 14

start_times = [
    model.NewIntVar(0, upper_limit, "start_times[%i]" % i) for i in range(n)
]
end_times = [
    model.NewIntVar(0, upper_limit * 2, "end_times[%i]" % i) for i in range(n)
]
end_time = model.NewIntVar(0, upper_limit * 2, "end_time")

intervals = [model.NewIntervalVar(start_times[i],duration[i],end_times[i],f"interval[{i}]")  for i in range(n)]

# number of needed resources, to be minimized
num_resources = model.NewIntVar(1, 2, "num_resources")

model.AddCumulative(intervals, demand, num_resources)

model.Add(num_resources <= 2)

model.Minimize(num_resources)

这应该更好，并稍微修改一下这个输出结果：

Solution:
Optimal Schedule Length: 1.0
Machine 0: job_1_task_0   job_0_task_0   
           [0,2]          [2,5]          
Machine 1: job_2_task_0   job_1_task_2   job_0_task_1   
           [0,4]          [4,8]          [8,10]         
Machine 2: job_1_task_1   job_2_task_1   job_0_task_2   
           [2,3]          [4,7]          [10,12] 

其中 job_0_task_1、job_1_task_2 和 job_0_task_2 现在具有不同的 start_time 和 end_time。

不幸的是，这还不是我希望达到的结果，因为在即时 2 和即时 7 之间有超过 2 个作业同时处于活动状态，尽管我已经指出了小于或等于 2 的资源数量（在我必须解决的问题中，每个资源只与一项工作相关联），所以我再次询问是否有人可以帮助我理解原因，谢谢。

Answer 1

这是一个较老的问题，所以我不知道你是否能够找到满意的答案。

参考您使用的 ortools 文档中的示例，只需添加累积约束，同时保持其他所有内容相同（因为每个和任何其他约束仍然有效）：

capacity = 2  # Maximum capacity of 2 machines in use at any time 
model.add_cumulative(
    [all_tasks[job_id, task_id].interval for job_id, job in enumerate(jobs_data) for task_id, task in enumerate(job)],
    [1] * len(all_tasks),  # Demand of 1 for every interval
    capacity
)

…基本上，Sascha 解释的 CP-SAT 语法