本文档旨在解决使用 Google OR-Tools 求解护士排班问题时，如何约束护士只能排连续班次。通过引入辅助变量来追踪每个护士每天的第一个和最后一个班次，并确保实际排班数等于班次差加一，从而实现连续排班的约束。
连续排班约束的实现
在护士排班问题中，一个常见的需求是确保护士的班次是连续的，即如果护士在某一天工作，则他们必须工作连续的班次。例如，护士可以工作班次 1 和 2，但不能工作班次 1 和 3，而不工作班次 2。 以下介绍一种使用 Google OR-Tools 实现此约束的方法。
核心思路
核心思想是找到每个人每天的第一个班次和最后一个班次，然后约束实际排班的班次数量等于这两个班次的差值加一。
具体步骤
-
定义变量：
- first_shifts[(n, d)]: 护士 n 在第 d 天的第一个班次。
- last_shifts[(n, d)]: 护士 n 在第 d 天的最后一个班次。
- shift_differences[(n, d)]: 护士 n 在第 d 天的班次差，即 last_shifts[(n, d)] - first_shifts[(n, d)]。
- shifts[(n, d, s)]: 布尔变量，表示护士 n 在第 d 天是否工作班次 s。
-
添加约束：
- model.Add(shift_differences[(n, d)] == last_shifts[(n, d)] - first_shifts[(n, d)]): 确保班次差等于最后一个班次减去第一个班次。
- model.Add(first_shifts[(n, d)] <= s).OnlyEnforceIf(shifts[(n, d, s)]): 如果护士 n 在第 d 天工作班次 s，则 first_shifts[(n, d)] 必须小于等于 s。
- model.Add(last_shifts[(n, d)] >= s).OnlyEnforceIf(shifts[(n, d, s)]): 如果护士 n 在第 d 天工作班次 s，则 last_shifts[(n, d)] 必须大于等于 s。
- model.Add(sum(shifts[(n, d, s)] for s in all_shifts) == (shift_differences[(n, d)]+1)): 确保护士 n 在第 d 天工作的班次数量等于班次差加一。
代码示例
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))注意事项
- 确保正确定义 all_nurses, all_days, all_shifts 和 num_shifts 等变量。
- 可以根据实际需求调整护士每天工作的最小和最大班次数量。
- 此方法假设班次是从 0 开始编号的。如果班次从 1 开始编号，则需要进行相应的调整。
总结
通过引入辅助变量来追踪每个护士每天的第一个和最后一个班次，并确保实际排班数等于班次差加一，可以有效地实现连续排班的约束。此方法简单易懂，并且可以灵活地应用于不同的排班场景。
