爲什麼約翰遜算法給出最優順序

Question

約翰遜算法車間作業調度解決了2臺機器和N就業

工作丕有兩個操作期間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. 

我不明白爲什麼這是給「最佳」的答案。這裏是wikipedia link

我認爲這是一個計數器例如：

工作集：

（2,3）;（4,5）;（6,7）

最終答案算法給出機器1上的J1，J2，J3（2,4,6），而機器2始終保持空閒。相反，如果我們的機器2計劃J1，J2機1和J3上那麼我們可以做它前面

誰能解釋我在做什麼錯。

Answer 1

最終答案算法給出機器1上的J1，J2，J3（2,4,6），而機器2一直保持空閒狀態。相反，如果我們在機器1上安排了J1，J2，並在機器2上安排了J3，那麼我們可以早點完成。

號的一點是，該作業由兩個部分組成，第一部分必須機1中，第二，在第一後進行結束，所述第二機器上。

所以在你的榜樣，你會得到的序列{ J1, J2, J3 }，這是正確的，它會被執行

1. J1[1]（M1）上; 2分鐘
2. J2[1]上M1，和J1[2]上M2，同時啓動; 4分鐘和3分鐘
3. J3[1]在M1上，J2[2]在M2上開始 - 巧合的是，因爲 - 同時; 6分5分鐘
4. J3[2]上M2; 7分鐘

所以你總共需要2 + 4 + 6 + 7 = 19分鐘，這是最快的方法。

的目標是最大化M1和M2上的活性之間的重疊。所以如果你有短的第一部分的工作，首先做他們讓機器2儘快佔領。如果可能的話，第二部分的作業持續時間最短，以便在機器1已經完成時機器2工作的時間很短。