OR工具-护士用二进制约束防止轮班间隙

Question

我正在使用OR工具来解决类似于护士调度问题的问题。在我的情况下的不同之处在于；护士；对于轮班，他们必须连续工作几天(即，工作日之间不能有间隔)。

大多数类似的问题都指向这个代码。我已尝试执行从中改编的答案。然而，我得到的输出解决方案不尊重约束。

我试图遵循的逻辑是，我想禁止有间隙的模式。例如：

[1,0,1]
[1,0,0,1]
[1,0,0,0,1]

下面是我的代码示例，其中

# Modified from the code linked above:
def negated_bounded_span(works, start, length):
sequence = []
# Left border
sequence.append(works[start].Not())
# Middle
for i in range(1,length+1):
sequence.append(works[start + i])
# Right border
sequence.append(works[start + length + 1].Not())
return sequence
for n in range(num_nurses):
# nurse_days[(n,d)] is 1 if nurse n works on day d
nrses = [nurse_days[(n, d)] for d in range(5)]

for length in range(1, 4):
for start in range(5 - length - 1):
model.AddBoolOr(negated_bounded_span(nrses, start, length))

以上输出的修改摘录如下：

['Not(nurse_days_n0d0)', nurse_days_n0d1(0..1), 'Not(nurse_days_n0d2)']
['Not(nurse_days_n0d1)', nurse_days_n0d2(0..1), 'Not(nurse_days_n0d3)']
['Not(nurse_days_n0d2)', nurse_days_n0d3(0..1), 'Not(nurse_days_n0d4)']
['Not(nurse_days_n0d0)', nurse_days_n0d1(0..1), nurse_days_n0d2(0..1), 'Not(nurse_days_n0d3)']
['Not(nurse_days_n0d1)', nurse_days_n0d2(0..1), nurse_days_n0d3(0..1), 'Not(nurse_days_n0d4)']
['Not(nurse_days_n0d0)', nurse_days_n0d1(0..1), nurse_days_n0d2(0..1), nurse_days_n0d3(0..1), 'Not(nurse_days_n0d4)']

感谢您提前提供的帮助。

回顾了类似的问题：[1]，[2]，[3]。

Answer 1

我不使用/不知道或工具的语法，但您可能可以构造一个带有约束的布尔逻辑来实现这一点。

假设我们引入一个二进制变量来注释护理n开始工作的d天：

s[n, d] ∈ {0, 1}

为了只强制执行一个工作日序列，我们需要限制为一个开始，对于所有护士

∑ s[n, d] over all d <= 1    for all n ∈ N 

然后我们知道，对于任何特定的一天，d，为了让n护士工作，他们要么必须在当天开始工作，要么在前一天开始工作，对吧？就是这样…

所以，

working[n, d] <= s[n, d] + working[n, d-1]    for all n ∈ N, d ∈ {d: d ≠ d_0}

d_0的约束留给感兴趣的编码器。)

Answer 2

这可以按如下方式实现：

为每位员工和每一天引入变量：

如果员工e在第d天轮班，则worksOnDay[e, d]=true。

如果员工e在第d天或更早开始工作，则workStarted[e, d]=true。

如果员工e在第d天可以工作，则okToWork[e, d]=true。

如果当天进行任何轮班，则将worksOnDay[e, d]约束为true，即当天轮班的布尔OR，使用OR Tools中的AddMaxEquality()表示。CCD_ 11有效地将目标变量约束为操作数的OR。

如果workStarted[e, d]在前一天d-1为true或当天已工作，则将其约束为true。(只有在工作日的第一天)。

如果前一天尚未开始工作，或者前一天已工作，则将okToWork[e, d]约束为true。(头两天，工作总是可以的，因为不可能有任何间隙)。换句话说，如果工作已经开始，那么只有前一天也工作了，才可以工作。伪代码中的表达式是(not workStarted[e, d - 1]) or (worksOnDay[e, d - 1])，但由于OR Tools不直接允许使用此类布尔运算符，因此在代码中我们必须引入一个约束为workStarted[e, d - 1].Not()的帮助变量，并在析取中使用它。

最后，通过添加以下含义来防止在不允许的日子工作CCD_ 16表示CCD_。该约束将在两个方向上起作用，并确保如果okToWork[e, d]为假，则worksOnDay[e, d]也将为假，因为否则将违反该约束。

很抱歉，我在c#中工作，没有可用的Python安装，但在Python中编写等效约束应该足够容易。这是代码：

var model = new CpModel();
IntVar[,,] work = new IntVar[numEmployees, numShifts, numDays];
IntVar[,] worksOnDay = new IntVar[numEmployees, numDays];
IntVar[,] workStarted = new IntVar[numEmployees, numDays];
IntVar[,] okToWork = new IntVar[numEmployees, numDays];
foreach (int e in Range(numEmployees))
{
foreach (int s in Range(numShifts))
{
foreach (int d in Range(numDays))
{
work[e, s, d] = model.NewBoolVar($"work{e}_{s}_{d}");
}
}
}
for (int e = 0; e < numEmployees; e++)
{
for (int d = 0; d < numDays; d++)
{
worksOnDay[e, d] = model.NewBoolVar($"WorksOnDay{e}_{d}");
workStarted[e, d] = model.NewBoolVar($"WorkStarted{e}_{d}");
okToWork[e, d] = model.NewBoolVar($"OkToWork{e}_{d}");
}
}
// WorksOnDay is true if any shift is taken on that day
for (int e = 0; e < numEmployees; e++)
{
for (int d = 0; d < numDays; d++)
{
IEnumerable<IntVar> shiftsOnDay = (from int s in Range(numShifts) select work[e, s, d]);
model.AddMaxEquality(worksOnDay[e, d], shiftsOnDay);
}
}
// On the first day, WorkStarted is true if that day is worked
for (int e = 0; e < numEmployees; e++)
{
model.Add(workStarted[e, 0] == worksOnDay[e, 0]);
}
// On subsequent days, WorkStarted is true if the day is worked, or if the work had been started on the day before
for (int e = 0; e < numEmployees; e++)
{
for (int d = 1; d < numDays; d++)
{
model.AddMaxEquality(workStarted[e, d], new List<IntVar>() { workStarted[e, d - 1], worksOnDay[e, d] });
}
}
// On the first and second days, there cannot have been a gap, work is always OK
for (int e = 0; e < numEmployees; e++)
{
model.Add(okToWork[e, 0] == 1);
model.Add(okToWork[e, 1] == 1);
}
// For the third day and beyond, work is OK if the work had not been started by the previous day, or if the previous day is worked.
for (int e = 0; e < numEmployees; e++)
{
for (int d = 2; d < numDays; d++)
{
IntVar workNotStartedYesterday = model.NewBoolVar("WorkNotStarted");
model.Add(workNotStartedYesterday == (LinearExpr)workStarted[e, d - 1].Not());
model.AddMaxEquality(okToWork[e, d], new List<IntVar>() { workNotStartedYesterday, worksOnDay[e, d - 1] });
}
}
// Prevent work on days that it is not allowed
for (int e = 0; e < numEmployees; e++)
{
for (int d = 0; d < numDays; d++)
{
// Working on a day implies that it is OK to work on that day.
// Stated otherwise, either it is ok to work on the day, or it is not worked on the day.
model.AddImplication(worksOnDay[e, d], okToWork[e, d]);
}
}