Google OR-Tools 连续班次

Question

我正在学习 OR-Tools 并开始添加护士调度问题。我试图添加一个限制，即如果护士正在工作，他们只能连续轮班工作（即不能工作 1 和 3 班，但可以工作 2 和 3 班）。

我不完全确定我的代码有什么问题。当护士有能力每天至少工作 (num_of_shifts - 1) 个轮班时，它可以工作，但如果他们不能，则不能工作（例如，如果每天有 5 个轮班，则每个护士每天可以工作 4 个轮班）。

这是一个示例输出，有 3 个轮班，3 个护士，每个护士最多可以工作 2 个轮班（忽略未要求的部分，我删除了它的代码）：

第 0 天 护士 0 轮班 1（未要求）。 护士 0 轮班 2（未要求）。 护士 1 轮班 0（未要求）。 护士 1 轮班 1（未要求）。 护士 2 轮班 0（未要求）。

第一天 护士 0 轮班 1（未要求）。 护士 0 轮班 2（未要求）。 护士 2 轮班 0（未要求）。

第二天 护士 0 轮班 1（未要求）。 护士 0 轮班 2（未要求）。 护士 2 轮班 0（未要求）。 护士 2 轮班 1（未要求）。

第三天 护士 0 轮班 0（未要求）。 护士 0 轮班 1（未要求）。 护士 1 轮班 1（未要求）。 护士 1 轮班 2（未要求）。

第四天 护士 0 轮班 0（未要求）。 护士 1 轮班 1（未要求）。 护士 1 轮班 2（未要求）。 护士 2 轮班 1（未要求）。

这是不起作用的代码

    has_started_shifts = {}
    for n in all_nurses:
        for d in all_days:
            has_started_shifts[(n, d)] = model.NewBoolVar(f"has_started_shifts_n{n}_d{d}")

    # consecutive shifts constraint
    for n in all_nurses:
        for d in all_days:
            # If a nurse works a shift, mark that they have started shifts for the day
            for s in all_shifts:
                model.Add(has_started_shifts[(n, d)] == True).OnlyEnforceIf(shifts[(n, d, s)])

            # If a nurse works a shift, they can work any subsequent shift
                if s > 1:
                    model.Add(shifts[(n, d, s)] <= shifts[(n, d, s - 1)]).OnlyEnforceIf(has_started_shifts[(n, d)])

我尝试创建辅助变量来跟踪第一次转变是否已经发生，但这也不起作用。

我已经研究了https://github.com/google/or-tools/blob/stable/examples/python/shift_scheduling_sat.py但它没有实现我想要的。

感谢您提供的任何帮助。

Answer 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 differance the differnace betweent 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 shfit differance
        model.Add(sum(shifts[(n, d, s)] for s in all_shifts) == (shift_differences[(n, d)]+1))