-1

作业车间调度的约翰逊算法解决了2台机器和N个作业的情况

作业 Pi 有两个操作，持续时间为 Pi1，Pi2，要按顺序在机器 M1，M2 上完成。

Step 1. List A = { 1, 2, …, N }, List L1 = {}, List L2 = {}.
Step 2. From all available operation durations, pick the minimum.
If the minimum belongs to Pk1,
Remove K from list A; Add K to end of List L1.
If minimum belongs to Pk2,
Remove K from list A; Add K to beginning of List L2.
Step 3. Repeat Step 2 until List A is empty.
Step 4. Join List L1, List L2. This is the optimum sequence.

我不明白为什么这是给出“最佳”答案。这是维基百科链接

我认为这是一个反例：

工作组：

(2,3);(4,5);(6,7)

算法给出的最终答案是机器 1 上的 J1,J2,J3(2,4,6)，而机器 2 一直处于空闲状态。相反，如果我们将 J1、J2 安排在机器 1 上，将 J3 安排在机器 2 上，那么我们可以早点完成

谁能解释我做错了什么。

4

1 回答 1

1

算法给出的最终答案是机器 1 上的 J1,J2,J3(2,4,6)，而机器 2 一直处于空闲状态。相反，如果我们将 J1、J2 安排在机器 1 上，将 J3 安排在机器 2 上，那么我们可以早点完成。

不。关键是工作由两部分组成，第一部分必须在第一台机器上完成，第二部分必须在第一部分完成后在第二台机器上完成。

所以在你的例子中，你会得到序列{ J1, J2, J3 }，没错，它会被执行

  1. J1[1]在 M1 上；2分钟
  2. J2[1]在 M1 和J1[2]M2 上同时启动；4分钟和3分钟
  3. J3[1]在 M1 和J2[2]M2 上，开始 - 巧合，因为J2[1] > J1[2]- 同时；6分钟和5分钟
  4. J3[2]在 M2 上；7 分钟

所以你总共需要2 + 4 + 6 + 7 = 19几分钟，这是最快的方法。

目标是最大化 M1 和 M2 上的活动之间的重叠。因此，如果您的作业的第一部分较短，请先完成它们以尽快占用机器 2。如果可能的话，最后有第二部分短的工作，这样机器 2 工作而机器 1 已经完成的时间很短。

于 2013-03-05T22:35:11.877 回答