减少Google ORtools python脚本的运行时（使用Google云）

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小时以上才能找到解决方案。因此，我想知道是否有可能减少运行时间？如果有帮助的话，我不一定需要最佳解决方案。由于我不太使用惩罚约束，任何满足指定约束的解决方案都可以

Answer 1

我终于设法解决了这个问题。下面我将描述我使用谷歌服务计算引擎的方法

在我找到解决方案之前，我尝试了两件事：

• 首先，我在运行时方面对代码进行了优化。例如，我删除了一个每月只分配几次的轮班类型，以减少搜索空间。此外，我还删除了个别特定的移位旋转规则和序列长度约束，因为它们会导致运行时的大幅增加
• 我尝试了“num\u search\u workers”参数的各种设置。请注意，在最新版本的脚本中，此参数不再包含在代码中，必须手动添加

然而，这些更改并没有导致所需的运行时间减少。很明显代码很好，但我只是没有足够的计算能力。因此，我考虑了如何在更强大的设备上运行脚本。我开始尝试在Google Colab上运行它，但在这里运行时间甚至比在我自己的设备上还要长

然后我决定在谷歌云服务上试用计算引擎。GCS允许只需单击几下，即可设置一个专用于CPU密集型任务的虚拟机（具有自定义规范）。此外，如果您以前从未使用过该服务，您可以获得300美元的信用卡来租用服务器。如果您注册，默认情况下会分配一个测试帐户，该帐户对VM的规范有一些限制。但是，如果您切换到付费帐户，则信用将添加到您的帐户中，并且限制将取消。通过这种方式，我可以接触到比我的笔记本电脑强大几个数量级的机器

对于那些对使用GCS运行python脚本感兴趣的人，我建议观看以下视频作为介绍：

• https://www.youtube.com/watch?v=JtUIQz_EkUw

此外，谷歌还介绍了如何在本代码库中使用虚拟机：

• https://codelabs.developers.google.com/codelabs/cloud-compute-engine#0

这些视频介绍了如何在Debian操作系统上设置python：

• https://www.youtube.com/watch?v=5OL7fu2R4M8&t=194s
• https://www.youtube.com/watch?v=nMY0qDg16y4&t=143s

如果您正在设置Python，请不要忘记创建一个虚拟环境来安装软件包和运行脚本：

• https://www.youtube.com/watch?v=N5vscPTWKOk&t=445s

一旦我了解了如何在虚拟机上运行脚本，我就尝试了虚拟机配置/num搜索工作者设置。不要忘记，如果使用多核处理器，可以增加搜索工作者的数量，从而降低运行时间

我注意到8核（30GB RAM）计算专用系统（在“试用帐户”中提供）在运行时间上比我的笔记本电脑快20-30倍。然而，我决定使用更强大的虚拟机。使用30核设置（130 GB RAM），脚本在20秒内运行完成，而不是48小时