公平转移分配

Question

我有一个稍微修改过的版本 nurse_sat
https://github.com/google/or-tools/blob/master/examples/python/nurses_sat.py
我有一个字典的键值 - (day, nurse, shift) = BoolVar 我想让所有护士每次轮班的时间都一样。

E.G：假设我们有 30 天，每天有 3 个班次 {0, 1, 2} 并且我们有 3 个护士 {a, b, c}
我想让所有护士在第 0 班做 10 次，在第 2 班做 10 次，在第 3 班做 10 次。

我尝试实现的方法是：

fairshift = {}
for j in range(num_nurses):
 for k in range(num_shifts):
  fairshift[(j,k)] = sum(shifts[(i, j, k)] for i in range(num_days))

理论上，这应该可以告诉我护士轮班的次数。例如：fairshift[(0, 0)] 应该是护士 A 整个星期的 0 轮班次数。然后为了使它们相等，我做了这样的事情：

for k in range(num_shifts):
 solver.Add(min([fairshift[(j, k)] for j in range(num_nurses)]) == max([fairshift[(j,k)] for j in range(num_nurses)]))

因此护士的最大轮班次数 k 等于最小班次，如果 num_days 是 30，他们都应该有 10 个班次 k。

但是，我无法让它工作，我也不确定为什么。为了使用 IntVar 而不是 _SumArray，我做了这样的事情：

for j in range(num_nurses):
 for k in range(num_shifts):
  fairshift[(j,k)] = solver.NewIntVar(0, num_days, "%i,%i" % (j,k))
  solver.Add(fairshift[(j,k)] == sum(shifts[(i, j, k)] for i in range(num_days)))

在 min .== max 的情况下，它有效但给出了错误的结果。我想我总结出了一些错误，但我不确定是什么。

Answer 1

fairshift = {}
for n in range(num_nurses):
  for s in range(num_shifts):
    sum_of_shifts[(n, s)] = model.NewIntVar(0, num_days, 'sum_of_shifts_%i_%i' % (n, s))
    model.Add(sum_of_shifts[(n, s)] == sum(shifts[(d, n, s)] for d in range(num_days)))


for s in range(num_shifts):
  min_fair_shift = model.NewIntVar(0, num_days, 'min_fair_shift_%i' % s)
  max_fair_shift = model.NewIntVar(0, num_days, 'max_fair_shift_%i' % s)
  model.AddMinEquality(min_fair_shift, [sum_of_shifts[(n, s)] for n in range(num_nurses)])
  model.AddMaxEquality(max_fair_shift, [sum_of_shifts[(n, s)] for n in range(num_nurses)]) 

  model.Add(max_fair_shift - min_fair_shift <= 1)

公平转移分配

Fair Shift Distribution

python

or-tools