1、一、 問題描述給定n個作業，每個作業有兩道工序，分別在兩臺機器上處理。一臺機器一次只能處理一道工序，并且一道工序一旦開始就必須進行下去直到完成。一個作業只有在機器1上的處理完成以后才能由機器2處理。假設已知作業i在機器j上需要的處理時間為ti,j。流水作業調度問題就是要求確定一個作業的處理順序使得盡快完成這n個作業。二、 算法分析n個作業1,2,n要在由2臺機器和組成的流水線上完成加工。每個作業加工的順序都是先在上加工，然后在上加工。和加工作業所需要的時間分別為ti,1和ti,2, .流水作業調度問題要求確定這n個作業的最優加工順序，使得從第一個作業在機器上開始加工，到最后一個作業在機器上加工

2、完成所需的時間最少。從直觀上我們可以看到，一個最優調度應使機器沒有空閑時間，且機器的空閑時間是最少。在一般情況下，機器上會有機器空閑和作業積壓兩種情況。設全部作業的集合為。是的作業子集。在一般情況下，機器開始加工中作業時，機器還在加工其他作業，要等時間t后才能利用。將這種情況下完成中作業所需的最短時間計為。流水作業調度問題的最優解為。1. 證明流水作業調度問題具有最優子結構設a是所給n個流水作業的一個最優調度，它所需要的加工時間為。其中，是在機器的等待時間為時，安排作業所需的時間。記，則我們可以得到。事實上，有T的定義可知.若，設是作業集在機器的等待時間為情況下的一個最優調度。則是的一個調度且

3、該調度所需的時間。這與a是N的一個最優調度矛盾，所以。從而。這就是證明了流水作業調度問題具有最優子結構的性質。2. 建立遞歸式計算最優解由流水作業調度問題的最優子結構的性質我們可以得到，。推廣到更一般的情形，我們便有：。其中，這一項是由于機器上，作業需在時間之后才能開工。因此，在機器上完成作業之后，在機器上還需時間才能完成對作業的加工。按照上面所敘述的遞歸式，可以設計出解決流水作業調度問題的動態規劃算法。通過對遞歸式的分析，算法可以得到進一步的改進。3. 流水調度問題的Johnson法則 設a是作業集S在機器的等待時間為t時的任意一個最優調度。如果在調度中，安排在最前面的兩個作業分別為i和j，

4、即。則由動態規劃的遞歸式可以得到：其中， 如果作業i和j滿足，則稱作業i和j滿足Johnson不等式。如果作業i和j不滿足Johnson不等式，則交換作業i和j的加工次序后，作業i和j滿足Johnson不等式。 在作業集S當機器的等待時間為t時的調度a中，交換作業i和作業j的加工次序，得到的作業集S的另一個調度a，它所需要的加工時間為 。其中， 當作業i和j滿足Johnson不等式時，我們有從而，由此可得，因此任意t有從而，。由此可見。 換句話說，當作業i和作業j不滿足Johnson不等式時，交換它們的加工順序后，作業i和作業j就滿足Johnson不等式了，且不增加加工時間。由此可得，對于流水

5、作業調度問題，必存在一個最優的調度a，使得作業和滿足Johnson不等式：，稱這樣的調度a為滿足Johnson法則的調度。 進一步可以證明，調度a滿足Johnson法則當且僅當對任意的i和j都有ij時有。由此可知，任意兩個滿足Johnson法則的調度均為最優調度。至此，我們將流水調度問題轉化為求滿足Johnson法則的調度問題。4. 算法的描述從上面的分析可知，流水作業調度問題一定存在滿足Johnson法則的最優調度，且容易由下面的算法確定。流水作業調度問題的Johnson算法：（1） 令；（2） 將中作業依的非減序排列；將中作業依的非增序排列；（3） 作業接種作業構成滿足Johnson法則的

6、最優調度。具體的代碼在文件夾流水作業調度動態規劃法文件夾中。三、 時空效率分析 算法FlowJob的主要計算時間花在對作業集的排序上。在這里，我們使用冒泡排序法(BubbleSort)，因此，在最壞情況下算法FlowJob所需要的計算時間為。所需要的空閑顯然是。四、 運行結果當輸入的作業數目為6時的運行結果當輸入的作業數為8時的運行結果五、 分析輸出結果當輸入的作業數目為6時： 每個作業在M1上執行的時間為，在M2上執行的時間為，輸入的數據為：作業序123456276468532792算法按照先執行的作業，保證M2機器上沒有等待，本例中作業1、4、5滿足條件，被選擇先執行。當選擇第一個作業時，

7、算法選擇讓M2第一次等待時間最少的那個，本例中作業1的最小，這樣就可以讓M2第一次等待最少。所以在的集合中，越小越靠前執行。當執行的作業時，要保證最后一個作業在M2上的執行時間最短，所以作業2，6，3是按照非增序排列，保證了作業3的是它們三個當中最小的一個。算法在計算執行時間的過程如下圖所示： 作業執行次序為：1，4，5，2，6，3.執行1時：M1上運行2個時間后交給M2，這時M2空閑了2個時間并開始工作。 所以此時要想將1做完需要7（2+5）個時間。執行4時：M1上運行4個時間后，M2還在繼續運行1，并沒有結束。M1結束時間為6，而M2結束1的時間為7，即。所以此時要想把1，4做完，需要14

8、（7+7）個時間。執行5時：M1上運行6個時間后，M2還在繼續運行4，并沒有結束。M1的結束時間為12，而M2結束4的時間為14，即.所以此時要想把1，4，5做完，需要23（14+9）個時間。執行2時：M1上運行7個時間后，M2還在繼續運行5，并沒有結束。M1的結束時間為19，而M2結束5的時間為23，即.所以此時要想把1，4，5，2做完，需要26（23+3）個時間。執行6時：M1上運行8個時間后，M2已經不在繼續運行2。M1的結束時間為27，而M2結束2的時間為26，即此時M2已經空閑了一個時間，即.所以此時要想把1，4，5，2，6完成，需要29（27+2）個時間。執行3時：M1上運行6個時間后，M2已經不在繼續運