3

与一名工人一起，一次只能执行一项任务（但可以立即在任务之间切换）

给定一个任务列表，
-- 定义为“n 秒，每 m 秒”（例如，每 3600 秒 5 秒）

我怎样才能找到每个任务的最佳开始时间和计数？

如果每个任务都是“1 秒，每 60 秒”，那么每个任务都会有一个唯一的起始秒，并且计数将是无限的（稳定状态）。
如果是“每 4 秒 1 秒”和“每 3 秒 1 秒”，结果将是：“0, 无限和 3, 3 次”

-- 希望是最简单的形式

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

--（稍微复杂一点的形式——
如果不是“n 秒每 m 秒”，
任务被定义为“n 秒每 l..o 秒”，
我可以在 l - o 范围内选择一个数字 m（但是在任务完成之前必须承诺那个 m），
这样可以更好地利用工人吗？
我将如何选择最好的 'm' ？

4

4 回答 4

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 后给出 AB xx AB xx。然后无法添加 C，

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

于 2008-11-21T20:48:27.400 回答
0

请参阅w:Scheduling (computing)。该链接包含一个很好的调度策略列表：

[调度] 是指进程在优先级队列中被分配优先级的方式。该分配由称为调度程序的软件执行。调度器主要关心：

  • CPU 利用率 - 使 CPU 尽可能忙碌。
  • 吞吐量 - 每个时间单位完成执行的进程数。
  • 周转时间 - 执行特定流程的时间量。
  • 等待时间 - 进程在就绪队列中等待的时间。
  • 响应时间 - 从提交请求到产生第一个响应所花费的时间。
于 2008-11-28T07:32:00.997 回答
0

这类问题很难解决，但相对容易优化。看看模拟退火、大洪水或遗传算法。

于 2008-10-18T19:27:11.350 回答
0

嗯，这里有一个小建议：如果 m 的最大公约数大于或等于 n 的和，则解是稳态的。

我会选择具有最大 n 总和的任务集，以使 m 的 gcd 大于或等于该总和。

于 2008-10-18T19:33:52.693 回答