Google或工具中的最大轮班序列-员工日程安排

Question

我正在为我在Python工作的医院的一个科室开发一个护士调度程序。这类程序的各种例子已经存在，并在网上共享。其中之一是：https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py

到目前为止，我已经成功地修改了上述链接中的代码，以包括各种类型的劳动法规以及护士的个人偏好。然而，我一直在努力执行以下规则：

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

该代码本机支持同一移位类型(例如，禁止连续的n个早班或夜班)的序列长度的界限。然而，如果连续轮班不是同一类型的(例如夜间/晚上/早晨/夜晚/早晨)，则无法限制连续轮班的长度。

我通过添加以下代码来实现这个规则：

    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

我们就不能在连续的off班次上添加一个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)])

我不知道这会不会有助于加速解决问题。