本文档旨在解决使用 Google OR-Tools 解决护士排班问题时，如何强制护士只能排连续班次的问题。通过引入辅助变量来追踪护士每天的第一个和最后一个班次，并约束实际排班数量等于班次差加一，从而实现连续排班的约束。
在护士排班问题中，一个常见的需求是确保护士的班次是连续的，即如果护士在某一天工作，他们必须工作连续的班次。本文将介绍如何使用 Google OR-Tools 来实现这一约束。
问题描述
假设我们有一个护士排班问题，需要满足以下条件：
- 有若干名护士。
- 有若干天需要排班。
- 每天有若干个班次。
- 每位护士每天可以工作一定数量的班次。
- 关键约束： 如果护士在某一天工作，他们必须工作连续的班次。
解决方案
为了实现连续排班的约束，我们可以采用以下步骤：
-
定义变量：
- shifts[(n, d, s)]: 布尔变量，表示护士 n 在第 d 天的班次 s 是否工作。
- first_shifts[(n, d)]: 整数变量，表示护士 n 在第 d 天的第一个班次。
- last_shifts[(n, d)]: 整数变量，表示护士 n 在第 d 天的最后一个班次。
- shift_differences[(n, d)]: 整数变量，表示护士 n 在第 d 天的最后一个班次和第一个班次的差值。
-
添加约束：
- 班次差约束： 确保 shift_differences[(n, d)] 等于 last_shifts[(n, d)] 减去 first_shifts[(n, d)]。
model.Add(shift_differences[(n, d)] == last_shifts[(n, d)] - first_shifts[(n, d)])
- 第一个班次和最后一个班次约束： 如果护士 n 在第 d 天的班次 s 工作，则 first_shifts[(n, d)] 必须小于等于 s，last_shifts[(n, d)] 必须大于等于 s。
for s in all_shifts: model.Add(first_shifts[(n, d)] <= s).OnlyEnforceIf(shifts[(n, d, s)]) model.Add(last_shifts[(n, d)] >= s).OnlyEnforceIf(shifts[(n, d, s)])- 排班数量约束： 护士 n 在第 d 天工作的班次数量必须等于 shift_differences[(n, d)] + 1。 这保证了班次的连续性。
model.Add(sum(shifts[(n, d, s)] for s in all_shifts) == (shift_differences[(n, d)]+1))
- 其他约束： 根据具体问题添加其他约束，例如每个护士每天工作的最大和最小班次数量。
model.Add(sum(shifts[(n, d, s)] for s in all_shifts) >= 1) # 至少工作一个班次 model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 8) # 最多工作八个班次
完整代码示例（片段）
first_shifts = {}
last_shifts = {}
shift_differences = {}
for n in all_nurses:
for d in all_days:
first_shifts[(n, d)] = model.NewIntVar(0, num_shifts - 1, f"first_shift_n{n}_d{d}")
last_shifts[(n, d)] = model.NewIntVar(0, num_shifts - 1, f"last_shift_n{n}_d{d}")
shift_differences[(n, d)] = model.NewIntVar(0, num_shifts - 1, f"shift_diff_n{n}_d{d}")
# Make shift difference the difference between the first and last shift
model.Add(shift_differences[(n, d)] == last_shifts[(n, d)] - first_shifts[(n, d)])
for s in all_shifts:
model.Add(first_shifts[(n, d)] <= s).OnlyEnforceIf(shifts[(n, d, s)])
model.Add(last_shifts[(n, d)] >= s).OnlyEnforceIf(shifts[(n, d, s)])
# Each nurse works at least and at most some number of shifts
for n in all_nurses:
for d in all_days:
model.Add(sum(shifts[(n, d, s)] for s in all_shifts) >= 1)
model.Add(sum(shifts[(n, d, s)] for s in all_shifts) <= 8)
# Make the number of shifts a nurse work for the day == to the shift difference
model.Add(sum(shifts[(n, d, s)] for s in all_shifts) == (shift_differences[(n, d)]+1))注意事项
- 确保正确定义了所有变量的范围。
- OnlyEnforceIf 的使用非常重要，它确保只有在护士实际工作时才应用第一个和最后一个班次的约束。
- 根据实际问题的需求，可能需要调整其他约束的参数。
总结
通过引入辅助变量来追踪护士每天的第一个和最后一个班次，并约束实际排班数量等于班次差加一，我们可以有效地使用 Google OR-Tools 来强制护士只能排连续班次。这种方法可以应用于各种排班问题，其中连续性是一个重要的约束条件。 在实际应用中，需要根据具体情况调整约束条件和参数，以获得最佳的排班结果.
