减少 Google OR 工具 python 脚本的 运行 时间（使用 Google 云）
Reducing run-time of Google OR-tools python script (using Google Cloud)
我正在 Python 为我工作的医院的一个部门开发一个护士调度程序。此类程序的各种示例已经存在并在线共享。其中之一如下：https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py
到目前为止，我已经修改了上面 link 中的代码，以包括各种类型的劳动法规以及个别护士的偏好。现在我想使用这个量身定制的脚本在 7 周内为 25 名护士制作名册（5 种轮班类型，可以减少到 4 种）。
但是，实施特定类型的约束会导致 运行 时间显着增加。这些约束是：
对 morning/evening/night 班次序列长度的限制：
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 小时才能找到解决方案。因此我想知道是否可以减少 运行 时间？如果有帮助，我不一定需要最佳解决方案。由于我不怎么使用惩罚约束，任何满足指定约束的解决方案都可以。
您的代码中存在错误：
.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 变量一起使用
我终于设法解决了这个问题。下面我描述了我使用 Google Services Compute Engine 的方法。
在找到解决方案之前，我尝试了以下几件事：
- 首先，我根据 运行 时间优化了代码。例如，我删除了每月仅分配几次的轮班类型，以减少搜索 space。我还删除了个别特定的轮班轮换规则和系列长度限制，因为这些会导致 运行-time
的大幅增加
- 我尝试了“num_search_workers”参数的各种设置。请注意，在最新版本的脚本中，此参数已不再包含在代码中，必须手动添加。
但是，这些更改并没有导致所需的 运行 时间减少。很明显代码没问题，但我只是没有足够的计算能力。因此我考虑了如何 运行 脚本在更强大的设备上。我开始尝试在 Google Colab 中 运行 它，但这里 运行 的时间比我自己的设备
还要长
然后我决定在 Google 云服务上试用计算引擎。 GCS 允许设置专用于 CPU 密集型任务（具有自定义规格）的虚拟机，只需单击几下。此外，如果您以前从未使用过该服务，您将获得 300 美元的信用额度来租用服务器。如果您注册，默认情况下您会获得一个测试帐户，该帐户对 VM 的规格有一些限制。但是，如果您切换到付费帐户，信用会添加到您的帐户并取消限制。这样我就可以访问比我的笔记本电脑强大几个数量级的机器。
对于那些有兴趣将 GCS 用于 运行 python 脚本的人，我建议观看此视频作为介绍：
此外，Google 介绍了如何在此代码实验室中使用虚拟机：
这些视频介绍了如何在 Debian OS 上设置 python：
- https://www.youtube.com/watch?v=5OL7fu2R4M8&t=194s
- https://www.youtube.com/watch?v=nMY0qDg16y4&t=143s
如果您正在设置 Python，请不要忘记创建一个虚拟环境来安装包和 运行 脚本：
弄清楚如何在 VM 上 运行 脚本后，我尝试了 VM configurations/num-search worker 设置。不要忘记，如果你使用多核处理器，你可以增加搜索工作者的数量，从而降低 运行 倍。
我注意到，就 运行 时间而言，8 核（30 GB RAM）计算专用系统（在“试用帐户”中提供）已经比我的笔记本电脑快 20-30。但是，我决定使用更强大的 VM。使用 30 核设置（130 GB RAM），脚本 运行 在 20 秒内完成，而不是 48 小时。
我正在 Python 为我工作的医院的一个部门开发一个护士调度程序。此类程序的各种示例已经存在并在线共享。其中之一如下：https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py
到目前为止，我已经修改了上面 link 中的代码，以包括各种类型的劳动法规以及个别护士的偏好。现在我想使用这个量身定制的脚本在 7 周内为 25 名护士制作名册（5 种轮班类型，可以减少到 4 种）。
但是，实施特定类型的约束会导致 运行 时间显着增加。这些约束是：
对 morning/evening/night 班次序列长度的限制：
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 小时才能找到解决方案。因此我想知道是否可以减少 运行 时间？如果有帮助，我不一定需要最佳解决方案。由于我不怎么使用惩罚约束，任何满足指定约束的解决方案都可以。
您的代码中存在错误：
.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 变量一起使用
我终于设法解决了这个问题。下面我描述了我使用 Google Services Compute Engine 的方法。
在找到解决方案之前，我尝试了以下几件事：
- 首先，我根据 运行 时间优化了代码。例如，我删除了每月仅分配几次的轮班类型，以减少搜索 space。我还删除了个别特定的轮班轮换规则和系列长度限制，因为这些会导致 运行-time 的大幅增加
- 我尝试了“num_search_workers”参数的各种设置。请注意，在最新版本的脚本中，此参数已不再包含在代码中，必须手动添加。
但是，这些更改并没有导致所需的 运行 时间减少。很明显代码没问题，但我只是没有足够的计算能力。因此我考虑了如何 运行 脚本在更强大的设备上。我开始尝试在 Google Colab 中 运行 它，但这里 运行 的时间比我自己的设备
还要长然后我决定在 Google 云服务上试用计算引擎。 GCS 允许设置专用于 CPU 密集型任务（具有自定义规格）的虚拟机，只需单击几下。此外，如果您以前从未使用过该服务，您将获得 300 美元的信用额度来租用服务器。如果您注册，默认情况下您会获得一个测试帐户，该帐户对 VM 的规格有一些限制。但是，如果您切换到付费帐户，信用会添加到您的帐户并取消限制。这样我就可以访问比我的笔记本电脑强大几个数量级的机器。
对于那些有兴趣将 GCS 用于 运行 python 脚本的人，我建议观看此视频作为介绍：
此外，Google 介绍了如何在此代码实验室中使用虚拟机：
这些视频介绍了如何在 Debian OS 上设置 python：
- https://www.youtube.com/watch?v=5OL7fu2R4M8&t=194s
- https://www.youtube.com/watch?v=nMY0qDg16y4&t=143s
如果您正在设置 Python，请不要忘记创建一个虚拟环境来安装包和 运行 脚本：
弄清楚如何在 VM 上 运行 脚本后，我尝试了 VM configurations/num-search worker 设置。不要忘记，如果你使用多核处理器，你可以增加搜索工作者的数量，从而降低 运行 倍。
我注意到，就 运行 时间而言，8 核（30 GB RAM）计算专用系统（在“试用帐户”中提供）已经比我的笔记本电脑快 20-30。但是，我决定使用更强大的 VM。使用 30 核设置（130 GB RAM），脚本 运行 在 20 秒内完成，而不是 48 小时。