python - 给定一组可能的任务，如何优化 worker 劳动力的最大使用时间

Question

所以我在算法建模方面有点困难，我希望你们能帮我找到一些方向。问题出在我公司后勤部，作为CS实习生，我还没找到解决办法

问题:给定固定时间、固定数量的 worker 和一组可行的任务，以所有 worker 都尽可能忙的方式将任务分配给 worker ，并且小组的最后一个 worker 只被分配到其他人无法承担的剩余任务。

这种方法的目的是让最后一个 worker 尽可能自由，这样他就可以只在真正需要的时候从事那些任务

约束:

• 截止时间:每个任务都有自己的截止时间。这意味着任何工作人员都可以随时开始一项任务，只要它在规定时间内最后一次完成即可。
• 不重叠:一个 worker 不能同时处理多个任务，一个任务不能在 worker 之间分配

到目前为止，我已经尝试...

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

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

为了找到类似的解决方案，我阅读了一些文章:

• Fitness Uniform Optimization

• Flexible Job Shop Scheduling

• Job Shop Problem Approach to Order-Picking Problem

提前致谢!

Answer 1

同构问题已经解决。我假设每项任务都有所需的工作量，并且工作人员可以互换:例如，Paul 将能够在与 Abby 完全相同的时间内完成任务 #17。

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

调用可用工作人员的数量 N+1，其中 +1 是按需工作人员。

按 LST 对任务进行排序，并按顺序将它们分配给 N 个可用的工作人员。用明显的间隔填写时间表:当每个工作人员完成当前任务时，分配下一个可用任务。

如果您在计划中到达了一个没有指定工作人员的 LST 点，请将其放入按需工作人员的队列中，N+1。当你走到尽头时，如果工作人员 N+1 的任务多于可用时间，那么你就没有解决方案。

例如，给定 2+1 个 worker 和任务

    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

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

    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，我们就完成了。

这会让你动起来吗？