代码之家 › 专栏 › 技术社区 › Jacob

连续断点调度算法

computer-science algorithm

Jacob · 技术社区 · 15 年前

我在这里迷路了。这是个问题,我认为它是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

我把问题简化成两人一组(0-3代表4组),希望得到一个可行的解决方案。 X

4 回复 | 直到 5 年前

mjv 15 年前

正如问题中所表达的那样。
这是因为这些数字不相加(或者更确切地说是“除以”)。

每天正好3班
每班2个工人
工人工作 最大值 连续5天
最低限度 连续两天

随着最小和最大限定符的引入, 最少需要9名工人
请注意,尽管9似乎是一个绝对最小值,但考虑到需要每周轮班42次(3*2*7),且工人每周最多轮班5次(5个工作日2个休息日=一周),鉴于连续工作和/或休息日的要求,不能保证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

btreat 15 年前

每天3班*每班2人*(每周7天/每人5个工作日)=8.4人(如果不选择兼职,则为9人)。

Randy 15 年前

3班x 7天=21

Grembo 15 年前

好吧-尽管你有答案,让我试试。

有7种可能的员工日程安排,表示为(1)天&休息日(0)

0011111 1100111 1110011 1111001 1111100 0111110

我有一个每班每种类型的员工数量矩阵,这个数字是一个整数变量。我的优化模型是:

受制于:总计(#员工计划*员工计划) = 每班所需人员

和

计划的员工数为整数

您可以将第一个约束中的=符号更改为>=。然后你会得到一个可行的解决方案与额外的工作人员。您可以在Excel中使用basic SOLVER addin解决此问题。

比方说,我每天需要4名员工轮班,但我愿意容忍额外的员工。

使用上述时间表的解决方案是:

按计划类型列出的员工人数:0,2,0,2,0,2,0

(换言之,附表1001111有2个,附表1111001有2个,附表11111 00有2个以上)

当然,这不是唯一的解决方案。至少有6个其他解决方案,有两个额外的工作人员。约束编程将是一种更好更快的方法,因为通常会有许多可行的时间表。