javascript - 固定时间窗上固定时间窗约束的可移动时间窗

Question

我有一组作业。

客户请求了一项工作。客户划定时间(例如:“您可以在 8:00 开始并在 13:00 结束)。一个内部算法会产生这个工作的估计执行时间(即使这个工作有 5 个小时，这个人也可以在 2 小时内完成)。这意味着该人员可以在 8:00 到 10:00 或 10:30 到 12:30 之间完成工作。

在一个工作日的时间窗口(8:00到17:00)，我们会尝试将工作分配给一个列表，然后将这个列表分配给一个worker。有多个列表和 worker 。

列表的唯一限制是我们不能同时执行两个作业。 (但是，例如，你可以有一个 J1(8:00 到 12:00，执行时间 1 小时)和 J2(8:00 到 12:00，执行时间 2 小时) 它是可行。因为 J1 可以在 8:00 到 9:00 完成，然后 J2 可以在 9:00 到 11:00 完成)

在 javascript 中，我的对象有开始时间、结束时间和估计持续时间(使用有用且强大的 moment.js)。

列表只是一个带有专门推送的数组，如果可以添加作业则返回 true。

exemple 这是一个示例，我们有棕色作业，其估计执行时间为红色，它们在一天的时间窗口(黑色)。最上面的工作是最后插入的，要做的是尝试知道工作列表是否仍然可行。所以这里需要做的只是在其他两个作业之间滑动(绿色箭头)执行时间稍晚。首先，我试图找到一种方法来了解是否可以将工作插入到工作列表中。

然后我做了一个算法，其中执行时间总是尽快在作业窗口时间内，但我认为我可以改进它。

是否有任何关于满足约束并允许在列表中插入最多作业的正确方法的建议？

Answer 1

我建议您先尝试在论文或其他内容上思考一些解决方案，然后，如果您找不到任何解决方案，请尝试进行一些研究。

Tip: Try to Sort things, and see if it helps to make decisions.

这是一个经典的算法问题，您应该寻找Scheduling Algorithms，并查看一些方法。也检查一下。 http://www.ctl.ua.edu/math103/scheduling/scheduling_algorithms.htm