连续排班约束如何用 Google OR-Tools 实现

本文档旨在指导如何使用 Google OR-Tools 解决护士排班问题，并强制执行连续排班约束，即如果护士在某天工作，则必须连续工作。我们将介绍如何定义辅助变量来跟踪第一个和最后一个班次，并使用约束来确保护士工作班次的数量等于班次差异加 1。

连续排班约束的实现

在护士排班问题中，一个常见的需求是确保护士的班次是连续的。例如，如果一个护士在一天中工作，他们不能只工作第一班和第三班，而必须是连续的班次，如第二班和第三班。以下是如何使用 Google OR-Tools 实现此约束的方法。

1. 定义辅助变量

首先，我们需要定义一些辅助变量来跟踪每个护士每天的第一个和最后一个班次。这些变量将帮助我们确定护士是否连续工作。

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)])

在上面的代码中，我们为每个护士和每天创建了三个整数变量：

• 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)]。 此外，对于每个班次，如果护士在该班次工作，则更新 first_shifts 和 last_shifts。

2. 添加约束

接下来，我们需要添加约束来确保护士工作班次的数量等于班次差异加 1。这确保了护士的班次是连续的。

# 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))

在上面的代码中，我们添加了以下约束：

• 每个护士每天至少工作 1 个班次。
• 每个护士每天最多工作 8 个班次。
• 每个护士每天工作的班次数等于班次差异加 1。

3. 完整代码示例

以下是一个完整的代码示例，展示了如何使用 Google OR-Tools 强制执行连续排班约束：

from ortools.sat.python import cp_model

def solve_nurse_scheduling():
    model = cp_model.CpModel()

    # 定义数据
    num_nurses = 3
    num_days = 5
    num_shifts = 3

    all_nurses = range(num_nurses)
    all_days = range(num_days)
    all_shifts = range(num_shifts)

    # 创建变量
    shifts = {}
    for n in all_nurses:
        for d in all_days:
            for s in all_shifts:
                shifts[(n, d, s)] = model.NewBoolVar(f"shift_n{n}_d{d}_s{s}")

    # 定义辅助变量
    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))


    # 求解模型
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    # 打印结果
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        for d in all_days:
            print(f"Day {d}")
            for n in all_nurses:
                for s in all_shifts:
                    if solver.Value(shifts[(n, d, s)]):
                        print(f"Nurse {n} works shift {s}")
            print()
    else:
        print("No solution found.")

if __name__ == "__main__":
    solve_nurse_scheduling()

注意事项

• 确保 num_shifts 的值与实际班次数匹配。
• 可以根据实际需求调整每个护士每天工作的最小和最大班次数。
• 可以根据实际需求添加其他约束，例如护士的偏好、技能要求等。

总结

通过定义辅助变量并添加约束，我们可以使用 Google OR-Tools 轻松地强制执行连续排班约束。这可以帮助我们生成更现实和可行的护士排班表。