python - 减少 Google OR-tools python 脚本的运行时间（使用 Google Cloud）

Question

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

到目前为止，我已经修改了上面链接中的代码，以包括各种类型的劳动法规以及个别护士的偏好。现在，我想使用这个量身定制的脚本在 7 周内为 25 名护士的工作人员编制名册（5 种轮班类型，可以减少到 4 种）。

但是，实施特定类型的约束会导致运行时间显着增加。这些约束是：

• 对早/晚/夜班系列长度的限制：

   shift_constraints = [
  
        #Morning shifts
        (1, 2, 2, 0, 4, 4, 0),
        #Evening shifts
        (2, 2, 2, 0, 4, 4, 0),
        Night shifts
        (3, 1, 2, 2, 5, 5, 0)
  
  ]
  

• 限制休息日。我想通过添加到班次限制列表中来防止安排单日休假：

  (0, 1, 2, 2, 10, 10, 0)
  

• 强制周末，周六和周日，被安排关闭：

          for e in range(num_employees):
            for d in range(num_days):
                if ( ( d in weekend_day ) & ( ( d+1 ) in weekend_day) ):
                    model.Add(work[e, 0, d + 1] == 1 ).OnlyEnforceIf(work[e, 0, d])
  

• 强制员工连续 3 次上夜班后放 2 天假

          for e in range(num_employees):
            for d in range(num_days):
                if ((d > 3) and (d<45)):
                    model.Add(work[e, 0, d] == 1).OnlyEnforceIf(work[e, 3, d-3] and work[e, 3, d-2] and work[e, 3, d-1])
                    model.Add(work[e, 0, d + 1] == 1).OnlyEnforceIf(work[e, 3, d-3] and work[e, 3, d-2] and work[e, 3, d-1])
  

• 强制员工不能连续工作超过 7 天：

  max_seq_length = 7
    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))
        # model, works, hard_min, soft_min, min_cost, soft_max, hard_max, #max_cost, 'shift_constraint(employee %i, shift %i)' % (23 shift))
        obj_bool_vars.extend(variables)
        obj_bool_coeffs.extend(coeffs)
  

在没有任何这些限制的情况下运行脚本只需不到 1 分钟。但是，当同时将它们全部添加到脚本时，可能需要超过 48 小时才能找到解决方案。因此我想知道是否可以减少运行时间？如果有帮助，我不一定需要最佳解决方案。由于我很少使用惩罚约束，因此任何满足指定约束的解决方案都可以。

标签： pythongoogle-cloud-platformruntimeschedulingor-tools

Answer 1

您的代码中有一个错误：

.OnlyEnforceIf(work[e, 3, d-3] and work[e, 3, d-2] and work[e, 3, d-1])

应该：

.OnlyEnforceIf([work[e, 3, d-3], work[e, 3, d-2], work[e, 3, d-1]])

不要min(), max(), and, not, if与 ortools 变量一起使用