0

我对这个调度示例有一个概念性的问题：

https://github.com/google/or-tools/blob/master/examples/python/shift_scheduling_sat.py

它将域问题建模为布尔标志的 3 维张量 [employee, shift, day]，表示特定员工在特定日期分配到特定班次。

几乎没有传达关于轮班本身的信息（除了是休息日、上午、下午还是夜班）。

然后，它add_soft_sequence_constraint与 一起使用negated_bounded_span，例如，将连续休假的天数限制为最多 1 或 2 天。

对于我的问题，我有未预定义的可变班次长度——解决方案的关键部分是每次班次的长度。总体思路是，全天都有不同的覆盖要求，例如从上午 8 点到上午 10 点只需要 1 名员工，从上午 10 点到下午 4 点需要 2 名员工，从下午 4 点到晚上 8 点需要 1 名员工。还有一份员工名单及其要求：他们每天的最小和最大工作时间是多少，他们可以分配到的最小和最大轮班时间，每天可以分配的最大轮班数，最短时间间隔班次等。不同员工的班次可以完全或部分重叠。

我可以用与上面示例类似的方式对此进行建模，在该示例中，我通过将每天分成 24 个时间窗口，每 1 小时长来增加班次维度的大小。员工被分配到这些固定的时间窗口。移位是分配给 True 的连续变量序列。为了使轮班符合一些常识（例如，早上 1 小时没有人进来，然后在午夜前又 1 小时），我可以使用与上述示例类似的方法，其中我需要特定的最小和最大轮班持续时间（分配给员工的连续时间窗口数）。

这可行，但感觉力适合这个 is-this-employee-assigned-to-this-shift 布尔张量模型。

我的问题是 - 是否有更自然的方法来使用整数、间隔或其他东西对约束进行建模，例如建模为每天的班次列表，其中“班次”是开始和结束时间以及分配的员工？

4

2 回答 2

1

为了总结在特定时间值班的员工人数以检查需求满足情况，您需要知道每个员工当时是否在值班 - 这基本上是布尔数组对于[员工，班次，一天]。我认为无论您做什么，您的模型中都需要该数组。

您还可IntervalVar以为每个员工引入一个表示轮班的列表，以便更轻松地编写关于最大/最小轮班持续时间和轮班之间的休息时间的约束，但是您必须将它们与具有附加约束的布尔数组相关联。

在我使用伪代码的答案中，我实际上并没有实现它。

对班次长度和关闭时间的限制类似于强制执行此伪代码中的表达式（仅在班次处于活动状态时强制执行）：

(shift.duration <= maxShiftLength).OnlyEnforceIf(active)
(shift.duration >= minShiftLength).OnlyEnforceIf(active)
(shift[i].end + minOffTime <= shift[i+1].start).OnlyEnforceIf(active[i+1])

由于您需要为每位员工创建比实际分配更多的潜在班次，因此您需要一个关于班次是否实际有效的标志。对于不活跃的班次，强制执行

(shift.start == 0).OnlyEnforceIf(active.Not())
(shift.end == 0).OnlyEnforceIf(active.Not())

每天最大小时数的约束可以通过为每一天制作一个（常数）IntervalVar day，然后对表达式求和来计算

max(0,min(shift.end, day.end) - max(shift.start, day.start))

每个员工当天的所有班次，并将总和限制为小于限制。每天和员工都这样做。

以连续小时而不是使用两个索引 shift 和 day 来测量时间会更简单，因此您将拥有一个布尔数组作为onDuty[employee, hour]. 小时的值将从 0 到您的计划范围。将这些与IntervalVar列表相关联的约束会更容易。

如果给定班次在时间 h 值班，则

min((shift.start >= h), (shift.end <h), active)

制定不等式以便从 0 到 1 的区间在第 0 小时而不是在第 1 小时有效。

如果该值在他或她的所有班次中的最大值为 1，则给定员工在时间 h 值班。

onDuty[e, h] == max((min((shift[i].start >= h), (shift[i].end <h), active[i]) for all i for the employee e)

最后一条评论：仅仅作为一个多维数组并不能使布尔数组成为张量——请参阅https://en.wikipedia.org/wiki/Tensor。

于 2022-01-26T15:56:37.920 回答
0

当约束主要是可接受的每日轮班顺序时，此问题针对固定轮班进行了调整。

它不适合可变班次模型。

于 2022-01-25T18:15:13.357 回答