减少Google ORtools python脚本的运行时(使用Google云)

2024-03-29 12:33:54 发布

您现在位置:Python中文网/ 问答频道 /正文

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


Tags: andin脚本formodelshift时间员工
2条回答

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

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

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

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

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

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

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

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

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

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

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

您的代码中有一个bug:

.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变量一起使用

相关问题 更多 >