在给定一组可能的任务的情况下，如何优化工人劳动力的完工时间以最大程度地利用时间

Question

所以我的算法建模有点困难，我希望你们能帮助我找到一些方向。问题出在我公司的物流部门，作为一名CS实习生，我还没有找到解决方案

问题：给定固定的时间、固定的工人数量和一组可行的任务，将任务分配给工人，使所有工人都尽可能忙碌，并且组中的最后一个工人是只分配别人无法承担的剩余任务。

这种方法的目的是让最后一个工人尽可能自由，这样他只能在真正需要的时候完成那些任务

限制：

• 截止时间：每个任务都有自己的截止时间。这意味着任务可以由任何工作人员随时启动，只要它在预定时间最后完成即可。
• 无重叠：一个工人不能同时处理多个任务，并且一个任务不能在工人之间分配

到目前为止我已经尝试过了...

• Job-Shop 问题：情况似乎并非如此，因为任务不能分组为作业，而作业必须由特定机器（在我们的例子中为工人）处理。在我的场景中，任何工人都可以完成任务，没有偏好。
• 灵活的JSP：我真的认为这就是我的情况，因为任务可以由任何机器（工人）处理。但我不知道如何将我的任务分组到工作中，因为它们没有明确的顺序，而只有截止时间。

我也尝试过通过谷歌或工具的方法，但似乎没有一个适合这个问题。由于它看起来像一个 NP 完全问题，我不认为通过暴力组合任务来找到解决方案是一种方法，尽管任务和工作人员的集合并没有那么大。

以下是我为了找到类似的解决方案而阅读的一些文章：

• 健身制服优化

• 灵活的车间调度

• 作业车间问题解决订单拣选问题的方法

提前致谢！

Answer 1

同构问题已经解决。我假设每项任务都有所需的努力，并且工人是可以互换的：例如，保罗将能够在与艾比完全相同的时间内完成任务＃17。

有了这个，调度变得微不足道：计算每个任务的“最晚开始时间”（LST），截止日期减去所需的工作量。例如，一项需要 4 小时且截止时间为 18:00 的任务，LST 为 14:00。

调用可用工人数量

N+1

，其中

+1

是按需工人。

按 LST 对任务进行排序，并按顺序将其分配给

N

可用的工作人员。用明显的间隔填写时间表：当每个工作人员完成当前任务时，分配下一个可用任务。

如果您到达时间表中的某个点，其中 LST 没有分配工作人员，请将其放入按需工作人员的队列中，

N+1

。当你到达最后时，如果工人

N+1

的任务多于可用时间，那么你就没有解决方案。

例如，给定2+1工人和任务

    Due  Effort  LST (computed from input)
A    5      3     2
B    3      2     1
C    1      1     0
D    5      2     3
E    4      3     1

按 LST 对列表排序

    Due  Effort  LST
C    1      1     0
E    4      3     1
B    3      2     1
A    5      3     2
D    5      2     3

我们现在开始按小时为每个工人制定时间表

    0  1  2  3  4
#1  C  B  B
#2  E  E  E

此时，我们看到任务A必须启动，但是两个正常的worker已经很忙了。我们必须将“某事”分配给#3。作业跨度的过载是 1 小时（实际上，这就是整个计划过载），因此将 1 小时作业交换到 #3，并在其 LST 处启动“过载”作业（这将减少回溯和重新生成的量）尝试在复杂的情况下）。

    0  1  2  3  4
#1  B  B  A  A  A
#2  E  E  E
#3  C

现在，任务 

D

很容易分配给#2，我们就完成了。

这让你感动吗？