algorithm - 优先区间调度算法

Question

我有以下问题。想象一组作业，开始时间 (st) 和结束时间 (et)。每个作业都有一个优先级值。我需要使用数量大于 1 的机器来安排这些作业。

基本上是与多个班级的课堂间隔安排相同的问题，但是我有优先级而不是权重。我不需要最大化权重，我只需要确保一个具有更高优先级的作业不会被丢弃，而另一个具有更高优先级的作业较低的优先级被选中并与其重叠。

此外，机器必须大部分时间都被占用。

这与其他已知问题相似吗？帮助：S

用一个例子和我的想法编辑（输入作业是有序的）：

----(a)0
  ----(b)1
   --------------(c)2
    ---- --------(d)3
      ----(e)5
        ------------(f)3
                     --- -----(g)4

                     ---------(h)4

                     ---------(i)4

字母 = 工作 ID，数字 = 优先级。
例如，对于 1 个输出队列，算法应该很简单： - 检查
局部最大值，（即比较后续作业，保持最佳作业，直到优先级 x 的作业与优先级 > x 的作业不重叠）。在这种情况下，“e”是局部最大值。所以我们分析直到工作 f。
- 在之前分析的工作中搜索兼容的工作，删除冲突的工作。在我们的例子中，我们分析到“f”。我们可以删除与“e”冲突的工作，因此我们还剩下“a”和“b”。我们可以用“a”和“b”重复算法，得到“b”和“e”作为结果。现在我们可以继续处理未丢弃的后续作业（“g”、“h”和“

我的问题是在多个输出队列的情况下。
例如，我对 3 个输出队列的想法：
-选择局部最大值“e”。
- 选择其冲突域中最好的 2 个工作或以前的工作：在我们的例子中是“d”和“f”。
- 检查“d”和“f”的冲突域是否有 3 个优先级较高的作业。在这种情况下，丢弃它并选择碰撞中最好的那个。
- 必须更新以前选择的工作。假设“b”更长，优先级为 2.5 并与 f 发生碰撞。我们首先选择“f”，然后我们需要丢弃它来选择“g”、“h”和“i”，然后选择 b。

先感谢您

标签： algorithmscheduled-tasksschedulingschedulenp

Answer 1

首先将作业从最高优先级排序到最低优先级，然后从最短到最长排序。如果已经安排了不超过n重叠的作业，则可以将每个作业添加到“待办作业列表”中。获得完整的“待办事项”列表后，您可以按开始时间排序并一次性将作业分配给机器。

这是一种贪心算法，您可能找不到在给定优先级下完成最多工作的组合。但是优先级较低的工作永远不会碰到优先级较高的工作。