给定一组可能的任务，如何优化工人劳动力的最大使用时间
How to optimize makespan of worker labor to maximum time usage given a set of possible tasks
所以我的算法建模有点困难，希望你们能帮我找到一些方向。问题出在我公司后勤部，身为CS实习生，还没找到解决办法
问题：给定固定的时间、固定数量的工人和一组可行的任务，将任务分配给工人，使所有工人都像越忙越好，组里的最后一个工人只分配到其他人无法承担的剩余任务。
这种方法的目的是让最后一个工人尽可能地空闲，这样他就可以只在真正需要的时候从事那些任务
约束：
- 截止时间：每个任务都有自己的截止时间。这意味着任务可以由任何工作人员随时开始，只要它在截止时间最后完成即可。
- 不重叠：一个工人不能分担多项任务，一个任务不能分工
到目前为止我试过了...
- Job-Shop 问题：似乎并非如此，因为任务不能分组为作业，必须由特定机器处理（我们的工作人员案件）。在我的场景中，任务可以由任何工人完成，没有偏好。
- 灵活JSP：我真的认为这是我的情况，因为任务可以由任何机器（工人）处理。但我不知道如何将我的任务分组，因为它们没有明确的顺序，只有截止时间。
我也尝试过 google OR-Tools 的方法，但 none 似乎适合这个问题。由于它看起来像一个 NP 完全问题，我不认为暴力组合任务以找到解决方案是一种方法，尽管任务和工作人员的集合不是那么大。
为了找到类似的解决方案，我阅读了一些文章：
提前致谢！
同构问题已经解决。我假设每个任务都有所需的努力，并且工人可以互换：例如，Paul 将能够在与 Abby 完全相同的时间内完成任务 #17。
有了这个，调度变得微不足道：为每个任务计算一个 "latest start time" (LST)，截止日期减去所需的工作量。例如，一项需要 4 小时并在 18:00 到期的任务的 LST 为 14:00。
调用可用工人数 N+1，其中 +1 是 on-demand 工人。
按 LST 对任务进行排序，然后按该顺序将它们分配给 N 个可用的工作人员。用明显的间隔填写时间表：当每个工人完成当前任务时，分配下一个可用任务。
如果您在没有指定工人的情况下进行了 LST，请将其放入 on-demand 工人 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已经忙了。我们必须将 something 分配给 #3。作业跨度的超载是 1 小时（实际上，这是整个计划超载），因此将 1 小时的作业换成#3 并在其 LST 开始 "overload" 作业（这将减少回溯量和re-tries 在复杂的情况下）。
0 1 2 3 4
#1 B B A A A
#2 E E E
#3 C
现在，任务 D 很容易分配给 #2，我们就完成了。
这让你感动吗？
所以我的算法建模有点困难，希望你们能帮我找到一些方向。问题出在我公司后勤部，身为CS实习生，还没找到解决办法
问题：给定固定的时间、固定数量的工人和一组可行的任务，将任务分配给工人，使所有工人都像越忙越好，组里的最后一个工人只分配到其他人无法承担的剩余任务。
这种方法的目的是让最后一个工人尽可能地空闲，这样他就可以只在真正需要的时候从事那些任务
约束：
- 截止时间：每个任务都有自己的截止时间。这意味着任务可以由任何工作人员随时开始，只要它在截止时间最后完成即可。
- 不重叠：一个工人不能分担多项任务，一个任务不能分工
到目前为止我试过了...
- Job-Shop 问题：似乎并非如此，因为任务不能分组为作业，必须由特定机器处理（我们的工作人员案件）。在我的场景中，任务可以由任何工人完成，没有偏好。
- 灵活JSP：我真的认为这是我的情况，因为任务可以由任何机器（工人）处理。但我不知道如何将我的任务分组，因为它们没有明确的顺序，只有截止时间。
我也尝试过 google OR-Tools 的方法，但 none 似乎适合这个问题。由于它看起来像一个 NP 完全问题，我不认为暴力组合任务以找到解决方案是一种方法，尽管任务和工作人员的集合不是那么大。
为了找到类似的解决方案，我阅读了一些文章：
提前致谢！
同构问题已经解决。我假设每个任务都有所需的努力，并且工人可以互换：例如，Paul 将能够在与 Abby 完全相同的时间内完成任务 #17。
有了这个，调度变得微不足道：为每个任务计算一个 "latest start time" (LST)，截止日期减去所需的工作量。例如，一项需要 4 小时并在 18:00 到期的任务的 LST 为 14:00。
调用可用工人数 N+1，其中 +1 是 on-demand 工人。
按 LST 对任务进行排序，然后按该顺序将它们分配给 N 个可用的工作人员。用明显的间隔填写时间表：当每个工人完成当前任务时，分配下一个可用任务。
如果您在没有指定工人的情况下进行了 LST，请将其放入 on-demand 工人 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已经忙了。我们必须将 something 分配给 #3。作业跨度的超载是 1 小时（实际上，这是整个计划超载），因此将 1 小时的作业换成#3 并在其 LST 开始 "overload" 作业（这将减少回溯量和re-tries 在复杂的情况下）。
0 1 2 3 4
#1 B B A A A
#2 E E E
#3 C
现在，任务 D 很容易分配给 #2，我们就完成了。
这让你感动吗？