回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我正在用Python为我所在医院的一个科室开发一个护士排班程序。此类计划的各种例子已经存在,并在网上共享。其中之一是:<a href="https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py" rel="nofollow noreferrer">https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py</a></p>
<p>到目前为止,我已经修改了上面链接中的代码,以包括各种类型的劳动法规以及个人护士偏好。现在,我想使用这个定制脚本在7周的时间内为25名护士的员工编制名册(5种轮班类型,可以减少到4种)</p>
<p>然而,实现特定类型的约束会导致运行时的显著增加。这些限制是:</p>
<ul>
<li><p>早班/晚班/夜班系列的长度限制:</p>
<pre><code> 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)
]
</code></pre>
</li>
<li><p>对休息日的限制。我想通过在轮班限制列表中添加以下内容来防止安排单日休假:</p>
<pre><code>(0, 1, 2, 2, 10, 10, 0)
</code></pre>
</li>
<li><p>强制周末,包括周六和周日;星期日、星期日和星期日的休息时间:</p>
<pre><code> 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])
</code></pre>
</li>
<li><p>强制员工在连续3个夜班后休息2天</p>
<pre><code> 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])
</code></pre>
</li>
<li><p>强制员工不能连续工作超过7天:</p>
<pre><code>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)
</code></pre>
</li>
</ul>
<p>在没有任何这些约束的情况下运行脚本需要不到1分钟的时间。但是,当同时将所有这些内容添加到脚本中时,可能需要48小时以上才能找到解决方案。因此,我想知道是否有可能减少运行时间?如果有帮助的话,我不一定需要最佳解决方案。由于我不太使用惩罚约束,任何满足指定约束的解决方案都可以</p>