algorithm - 连续休息的调度算法

Question

我迷路了。这就是问题所在，我认为这是 NP 难的。一个中心配备了有限数量的 worker ，并满足以下条件:

1. 每天3类，每类2人
2. 每位员工连续工作 5 天，然后休息 2 天，每天只轮类一次

所以问题是:如果中心每天都保持活跃且时间表可行，我们需要多少 worker ？

更新:

感谢所有出色的回答。我最接近的(使用随机蛮力算法)如下:

X       3       0
1       0       3
2       3       1
2       1       3
0       1       2
0       2       1
3       0       2

我已将问题简化为每批 2 人(0-3 代表 4 批)，希望得到可行的解决方案。 X 指的是尚未分配的类次(这不是最初的目标，但看起来可能没有替代方案)。

Answer 1

不能像问题中表达的那样完全遵守约束。
那是因为数字不相加(或者更确切地说“相除”)。

因此，问题应该改写为要求

• 每天正好 3 个类次
• 每类恰好 2 名 worker
• worker 最多连续工作 5 天
• worker 至少连续休息 2 天

随着最小和最大限定符的引入，所需的最小 worker 数量为 9(再次假设没有兼职 worker )。
请注意，虽然 9 似乎是绝对最小值，但考虑到需要每周轮类 42 个类次 (3 * 2 * 7)， worker 每周最多可以轮类 5 个类次(5 个工作日 2 个休息日 = 一周) , 鉴于连续工作和/或休息日的要求，无法保证 9 天就足够了。

我是这样想的...
8个worker是不够的，下面9个worker的排类，就是这样一个排类的例子。
为了让事情变得简单，我将除 worker #1 和 #9 之外的所有 worker 分配到一个最佳时间表，即 5 天工作和 2 天休息时间表； #1 和#9 工作较少。当然，许多其他安排也会起作用(也许这就是 OP 在暗示 NP 完全问题时所感觉到的)。此外，时间表是这样的，每个人每周的时间表都完全相同，但这也可以改变(也许引入一些公平，让所有 worker 每隔一段时间有一个更轻松的一周，但顺便说一句，这可能会导致一些遵守最多 5 个工作日的要求的困难)。
示例时间表显示了连续两周，以帮助查看连续的工作日或休息日，但如前所述，每个周都是相同的。

                              Max Conseq Ws   Min Conseq Rs
Worker #1   RRWWWRW RRWWWRW         3              2
Worker #2   WWWWWRR WWWWWRR         5              2
Worker #3   WWWRRWW WWWRRWW         5              2
Worker #4   WWWRRWW WWWRRWW         5              2
Worker #5   WRRWWWW WRRWWWW         5              2
Worker #6   WRRWWWW WRRWWWW         5              2
Worker #7   RWWWWWR RWWWWWR         5              2
Worker #8   RWWWWWR RWWWWWR         5              2
Worker #9   WWRRRRW WWRRRRW         3              3

Nb of Ws    6666666 6666666

底部的计数显示每天正好有 6 名 worker (尊重需要涵盖 3 个类次，每个类次有 2 个 worker )，右侧的最大和最小列显示满足最大连续工作和最小连续休息要求。