Google OR 工具员工调度中的最大轮班序列

Question

我正在为我在 Python 工作的医院的一个部门开发护士调度程序。此类程序的各种示例已经存在并在线共享。其中之一如下：https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py

到目前为止，我已经成功地调整了上面 link 中的代码，以包括各种类型的劳动法规以及个别护士的偏好。但是我一直在努力实施以下规则：

员工不能连续工作超过 5 天。

该代码本身支持对相同班次类型的系列长度进行限制（例如禁止连续 n 个早班或夜班）。但是，如果它们不是同一类型（例如 night/night/morning/night/morning），则无法限制一系列背靠背轮班的长度。

我通过添加以下代码成功实现了这条规则：

    for e in range(num_employees):
            for d in range(num_days):                 
                   model.Add(work[e, 0, d] == 1).OnlyEnforceIf( (work[e, 1, d-5] or work[e, 2, d-5] or work[e, 3, d-5] or work[e, 4, d-5] )
                                                                and (work[e, 1, d-4] or work[e, 2, d-4] or work[e, 3, d-4] or work[e, 4, d-4] )
                                                                and (work[e, 1, d-3] or work[e, 2, d-3] or work[e, 3, d-3] or work[e, 4, d-3] )
                                                                and (work[e, 1, d-2] or work[e, 2, d-2] or work[e, 3, d-2] or work[e, 4, d-2] )
                                                                and (work[e, 1, d-1] or work[e, 2, d-1] or work[e, 3, d-1] or work[e, 4, d-1] ))

但是，此实现显着增加了程序的运行时间（从没有限制的 30 秒到包括它的大约 15 分钟）。因此，我正在寻找一种方法来禁止员工被安排连续 5 天或更多天，而不会增加运行时间。

Answer 1

您可以通过限制 off_shift.not() 文字的长度来调整代码。

Answer 2

回答

我使用以下代码行实施了@LaurentPerron 建议的更改：

max_seq_length = 5
for e in range(num_employees):
    works = [work[e, 0, d].Not() for d in range(num_days)]
    variables, coeffs = add_soft_sequence_constraint(
           model, works, 0, 0, 0, max_seq_length, max_seq_length, 0, 
           'shift_constraint(employee %i, shift %i)' % (e, 0))
    obj_bool_vars.extend(variables)
    obj_bool_coeffs.extend(coeffs)

Answer 3

我们不能只在连续的关闭班次上添加 AddBoolOr 约束，而不是 'add_soft_sequence_constraint' 函数和 .Not() 文字吗？即，我们强制要求没有长度为 hard_max 的序列中没有偏移。示例代码，修改自示例文件：

max_seq_length = 5
for e in range(num_employees):
    works = [work[e, 0, d] for d in range(num_days)]
    for start in range(len(works) - hard_max):
        model.AddBoolOr([works[i] for i in range(start, start + hard_max + 1)])

我想知道这是否有助于加快求解器的速度。

Google OR 工具员工调度中的最大轮班序列

Maximum length series of shifts in Google OR-tools employee scheduling

python

scheduling

runtime

or-tools