护士排班示例：防止轮班重叠

Question

我仍然是约束编程的初学者，我目前正在尝试在 Python 中实现护士调度问题，这与 Google OR-Tools 上提供的示例类似。

但是，在我的排班问题中，有多个患者每天轮班次数相同，但在一天中的不同时间点。我试图实施的约束应确保给定的护士不会被分配到时间上相互重叠的班次。例如，如果患者 X 从上午 10 点到 12 点轮班，而患者 Y 从上午 9 点到 11 点轮班，则给定的护士只能分配到其中一个轮班。如何实现这一点？

我的方法是创建两个单独的列表（或组合它们的元组列表）：

(1) 一个用来定义每个班次的持续时间，shift_duration（一个元素列表，每个元素代表一个班次的持续时间，以小时为单位）

(2) 一个定义班次开始时间，shift_starting_point（一个从0到24的元素列表，每个元素代表一个班次）在另一个列表中（类型类似于shift_requests中的例如）。

我试图应用 Job Shop Problem 中的 AddNoOverlap 方法，但我不知道如何使用此方法将它们组合成硬约束规则。我也不知道这种方法是否有意义。如果有任何帮助，我将不胜感激 - 谢谢！

Answer 1

我将从简单的方法开始：

for each conflicting pair of shifts (a, b):
  for each nurse n:
    model.AddBoolOr([assign_a_n.Not(), assign_b_n.Not()])

我知道这是二次方程，但是很简单。

Nurse scheduling example: preventing overlapping shifts