algorithm - 安排具有重叠周期性任务的工作人员

Question

一个 worker ，一次只能执行一项任务(但可以在任务之间即时切换)

给定任务列表，
-- 定义为“n 秒，每 m 秒”(例如，每 3600 秒 5 秒)

我如何找到最佳开始时间并计算每项任务？

如果每个任务都是“1 秒，每 60 秒”，每个任务都有一个唯一的起始秒，并且计数将是无限的(稳态)。
如果是“每 4 秒 1 秒”和“每 3 秒 1 秒”，结果将是:“0，无限和 3，3 次”

--希望是最简单的形式

如果我已经有了一个任务列表，用“开始秒数和次数”详细说明，返回 {start, count} for additional {n seconds every m seconds} 任务的函数会是什么样子？

--(稍微复杂一点的形式--
如果不是“每 m 秒 n 秒”，
任务被定义为“每 l..o 秒 n 秒”，
我可以在 l - o 范围内选择一个数字 m(但在任务完成之前必须提交那个 m)，
这会提高员工利用率吗？
我将如何选择最好的“m”？

Answer 1

我认为这取决于您如何定义“最佳”。例如，如果您希望任务“平均”每 m 秒运行一次，则有一种简单的方法可以使用与 Bresenham 方法相同的算法来绘制线条(“每 m 秒 n 秒”的任务非常简单)就像画一条线时在 m 个水平步骤中分散 n 个垂直步骤)。为每个任务分配一个计数器和一个步长值(对于“每 3 秒 1 秒”，步长为 1/3)。然后在每个“循环”通过时将步骤添加到计数器。当计数器超过零时，该任务应该运行(并从计数器中减去 1)。如果您有多个计数器大于零，请选择最大的一个。这可能会为您提供一个对于稍微复杂一点的表单也“足够好”的解决方案。

虽然“1/4”和“1/3”示例听起来您需要“恰好”间隔 m 秒运行任务。从列表开始并添加新任务以最大化计数并不是一个困难的搜索问题——但我认为这不是您所需要的。 A(1/4) B(1/4) C(1/2) 的例子在加上 A 然后 B 之后会得到 A B x x A B x x。然后 C 不能被添加，

我认为适合度函数有明显的候选者 - n,m,start 的表可以有一个适合度函数，它是不超过一个任务被安排的时间部分。如果存在，GA/退火很有可能找到稳态解。但在 (1/4)、(1/3) 等情况下，似乎没有稳态解决方案，定义“最佳”也应该定义您的适应度函数。