具有连续中断的调度算法

发布于 2024-09-08 06:53:53 字数 473 浏览 1 评论 0原文

我在这里迷路了。这就是问题所在，我认为它是 NP 难的。一个中心的员工数量是有限的，其条件如下：

每天 3 个班次，每班 2 人
每个员工连续工作 5 天，然后休息 2 天，每天只有一个班次

所以问题是：如果中心每天保持活动并保持可行的时间表，我们需要多少工人？

更新：

感谢所有精彩的答案。我最接近的结果（使用随机暴力算法）如下：

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 指的是尚未分配的班次（这不是最初的目标，但看起来可能没有替代方案）。

原文

I'm lost here. Here's the problem and I think it's NP-hard. A center is staffed with a finite number of workers with the following conditions:

There are 3 shifts per day with 2 people in each shift
Each employee works for 5 days straight and then 2 days off with only one shift per day

So the problem is: how many workers do we need if the center remains active every day and a feasible schedule?

Update:

Thanks for all the great answers. The closest I've come to (with a randomized brute-force algorithm) is the following:

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

I've simplified the problem into batches of 2 people (0-3 represent 4 batches) in the hopes of getting a feasible solution. X refers to a shift which has not been assigned (which was not the initial goal but it looks like there may not be an alternative).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

云淡风轻 2024-09-15 06:53:53

不能完全遵守问题中所表达的约束。
这是因为这些数字没有相加（或者更确切地说“相除”）。

因此，问题应该改写为

每天正好需要 3 个轮班
，每个轮班
最多有 2 个工人工作连续 5 天的
工人休息至少连续 2 天

随着最小和最大限定条件的引入，所需的最少工人数量为 9（同样假设没有任何人员参与） -时间工人）。
请注意，虽然 9 似乎是绝对最小值，但考虑到每周需要承担 42 个轮班 (3 * 2 * 7)，而工人每周最多可以承担 5 个轮班（5 个工作日 2 个休息日 = 一周），考虑到连续工作和/或休息日的要求，不能保证 9 就足够了。

我就是这样想的...
8 名工人是不够的，下面的 9 名工人的阵容就是这种时间表的一个例子。
为了让事情变得简单，我将除了工人 #1 和 #9 之外的所有工人分配到一个最佳的时间表，即工作 5 天和休息 2 天； #1 和 #9 工作较少。当然，许多其他安排也可以工作（也许这就是OP在暗示NP完全问题时所感觉到的）。此外，时间表是这样的，每个人每周的时间表都是完全相同的，但这也可以改变（也许引入一些公平性，让所有工人每隔一段时间就有一个轻松的一周，但是顺便说一句，这可能会导致一些遵守最多 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 个工人（考虑到需要覆盖 3 个班次，每个班次有 2 名工人），右侧的最大和最小列显示遵守最大连续工作和最小连续休息要求。

The constraints cannot be respected exactly as expressed in the question.
That's because the numbers don't add up (or rather "divide up").

Consequently, the problem should be reworded to require

exactly 3 shifts per day
exactly 2 workers per shift
workers work a maximum of 5 consecutive days
workers rest a minimum of 2 consecutive days

With the introduction of the minimum and maximum qualifiers, the minimum number of workers required is 9 (again assuming no part-time worker).
Note that although 9 appears to be a absolute minimum, given the need to cover 42 shifts per week (3 * 2 * 7) with workers who can cover a maximum of 5 shifts per week (5 work days 2 rest days = a week), there is no assurance that 9 would be sufficient given the consecutive work and/or rest day requirements.

This is how I figure...
8 workers isn't enough, and the following 9 workers line-up, is an example of such a schedule.
To make things easy, I assigned all workers except for worker #1 and #9, to an optimal schedule of exactly a 5 days-on and 2 days-off schedule; #1 and #9 work less. Of course many other arrangements would work (maybe this is what the OP sensed when he hinted at an NP-complete problem). Also, the schedule is such that each week's schedule is exactly the same for everyone, but that could also be changed (maybe introducing some fairness, by having all workers have a lighter week every once in a while, but this BTW can lead to some difficulties of respecting the requirement of 5 maximum work days).
The sample schedule shows two consecutive weeks to help see the consecutive work or rest days, but as said, all weeks are the same for every one.

                              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

The tally at the bottom shows exactly 6 workers per day (respecting the need to cover 3 shifts with 2 workers each), the max and min columns on the right show that the maximum consecutive work and minimum consecutive rest requirements are respected.

回复收藏 0 原文