008算法筆記——動態(tài)規(guī)劃流水作業(yè)調(diào)度問題與Johnson法則

1、0018算法筆記一一【動態(tài)規(guī)劃】流水作業(yè)調(diào)度問題與Johnson法則 1、問題描述： n個作業(yè)1,2,，n要在由2臺機器M1和M2組成的流水線上完成加工。每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時間分別為ai和bi。 流水作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器M2上加工完成所需的時間最少。 2、問題分析 直觀上，一個最優(yōu)調(diào)度應(yīng)使機器M1沒有空閑時間，且機器 M2的空閑時間最少。在一般情況下，機器M2上會有機器空閑和作業(yè)積 壓2種情況。設(shè)全部作業(yè)的集合為N=1,2,，n。S是N的作業(yè)子集。

2、在一般情況下，機器M1開始加工S中作業(yè)時，機器M2還在加工其他作業(yè)，要等時間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時間記為T（S,t）。流水作業(yè)調(diào)度問題的最優(yōu)值為 T（N,0）。 設(shè)兀是所給n個流水作業(yè)的一個最優(yōu)調(diào)度，它所需的加工時間為a兀 （1 1） + 。 其中丁是在機器M2的等待時間為b兀 （1 1） 時， 安排作業(yè)兀 （2 2） ,，兀（n n）所需的時間。 記S=N-兀(1)(1),則有T=T(S,b兀(1)(1) 證明： 事實上， 由T的定義知丁=T(S,b兀(1)(1)。 若丁T(S,b兀(1),(1),設(shè)兀是作業(yè)集S在機器M2的等待時間為b兀(1)(1)情況下的一個最

3、優(yōu)調(diào)度。則兀(1),(1),兀(2)(2),，兀(n)(n)是N的一個調(diào)度，且該調(diào)度所需的時間為a兀(1)(1)+T(S,b兀(1)(1)a兀(1)(1)+T。這與兀是N的最優(yōu)調(diào)度矛盾。故丁=T(S,b兀(1)(1)。從而丁=T(S,b兀(1)0(1)0 這就證明了流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。 由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知： I I 亍(M0)=眄 M M0 0 也)一 11三理 丁(Sj)(Sj)= =minminaai i十丁(S(S+ +maxfmaxfq,0)2)q,0)2) 從公式(1)可以看出，該問題類似一個排列問題，求N個作 業(yè)的最優(yōu)調(diào)度問題，利用其子結(jié)構(gòu)性質(zhì)

4、，對集合中的每一個作業(yè)進行試調(diào)度，在所有的試調(diào)度中，取其中加工時間最短的作業(yè)做為選擇方案。將問題規(guī)模縮小。公式(2)說明一般情況下，對作業(yè)集S進行調(diào)度，在M2機器上的等待時間，除了需要等該部件在M1機器上完成時 間，還要沖抵一部分原來的等待時間，如果沖抵已成負值，自然仍需等待M1將作業(yè)做完，所以公式取maxt-ai,0。 3、動態(tài)規(guī)劃法求解思路 假設(shè)有一組作業(yè)需要在M1和M2兩臺機器上進行流水作業(yè)， 他們在M1和M2上的作業(yè)時間如下表： M1 M2 J0 2 5 J1 4 2 J2 3 3 J3 6 1 J4 1 7 問題是如何安排他們的加工順序，使得，到最后一個作業(yè)在 機器M2上加工完成所需

5、要的時間最少。也就是所有作業(yè)在兩臺機器全部加工完成所需的時間最少。 思路如下：考慮如果只有一個作業(yè)的情況，肯定所需時間就 是它自身需要在M1和M2上的加工時間總和；如果有兩個作業(yè)就要考慮在兩種不同的加工順序下選取最優(yōu)的一種作為候選，三個作業(yè)的時會出現(xiàn)三種組合情況(0,(1,2);(1,(0,2);(2,(0,1),拿第一種為 例，它表示先加工作業(yè)0,然后再按照作業(yè)1和作業(yè)2的優(yōu)化順序加工；將三種的作業(yè)時間計算出來，取最小值，即為三個作業(yè)的優(yōu)化結(jié)果，同理可對更多的作業(yè)進行排序優(yōu)化。具體做法是，用類似矩陣連乘的辦法，自底向上將所有能的情況計算出來，并產(chǎn)生一個表，供后面的計算查用，減少重復(fù)計算的工作

6、量。 JOJO J1 R P 0 7 12 16 19 j1j1 6 6 9 9 J2J2 6 6 1010 P P 7 9 抻 8 對于j1作業(yè)M2的等待時間為b0,實際上在M2加工j0作業(yè) 的同時，M1并行加工j1,實際它需要等待b1-a0時間。 alblalbl 2+4+(5-4)+2=9 從J0和J1兩個作業(yè)的加工順序，可以看出，先加工J0后 J1,所用時間最短為9,將其填入表中，依此類推，即可得出最優(yōu)解。 J3 J2J2 j4j4 a4+a0+a2+a1+a3+(b4+b0+b1+b2)-(a0+a1+a2+a3)+b3=1+2+3+4+6+(7+5+2+3)-(2+4+3+6)+1

7、=16+17-15+1=19 選其中加工時間短的作為候選方案；在具體計算時非最優(yōu) 子集不必考慮，這樣可以減少計算次數(shù)。 4、流水作業(yè)調(diào)度的Johnson法則 設(shè)兀是作業(yè)集S在機器M2的等待時間為t時的任一最優(yōu)調(diào) 度。若在這個調(diào)度中，安排在最前面的兩個作業(yè)分別是i和j，即兀 (1)=I,兀(2)=j。則有動態(tài)規(guī)劃遞歸式可得 T(S,f)=q+T(S-i74+maxf-a.ft) =%+a+T(S-f,/#)JJ jljl alal blbl 其中 ty-bj+max也+max一qOQjJ)I =b+“一a+maxmaxt-minbj,ai,則稱作業(yè)i和j滿足Johnson不等式。如果作業(yè)i和j不

8、滿足Johnson不等式，則交換作業(yè)i和j滿足Johnson不等式。 證明：在作業(yè)集S中，對于機器M2的等待時間為t的調(diào)度兀，交換作業(yè)i和j的加工順序，得到作業(yè)集S的另一個調(diào)度兀，它所需的加工時間為 tn=b-+bt-a.一q+maxt.%+a-,a)JufuXBFurvJ 當(dāng)作業(yè)i和j滿足Johnson不等式minbi,aj minbj,ai時，有 maxmax一maxmax等號書式 從而 .I 區(qū)+%+max-q+a.+max-% 由此可得 maxaf+二%min61/n-1 這樣的調(diào)度冗稱為滿足Johnson法則的調(diào)度。進一步還可以證明，調(diào) 度滿足Johnson法則當(dāng)且僅當(dāng)對任意i0mi

9、nmin鼠(上心八ijij 由此可知，任意兩個滿足Johnson法則的調(diào)度具有相同的加工時間，從而所有滿足Johnson法則的調(diào)度均為最優(yōu)調(diào)度。 5、流水作業(yè)調(diào)度問題Johnson算法 從上面的分析可知，流水作業(yè)調(diào)度問題一定存在滿足 Johnson法則的最優(yōu)調(diào)度，且容易由下面的算法確定： 流水作業(yè)調(diào)度問題的Johnson算法： (1)令N1=i|ai=bi; (2)將N1中作業(yè)按ai的非減序排序；將N2中作業(yè)按bi的非增序排序； (3)N1中作業(yè)接N2中作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)度。 Johnson算法中分類及排序的作用(驗證不等式)設(shè)數(shù)組可 為排序后的作業(yè)排列，排序結(jié)果如下： 4

10、40oMlac2Jbc3blc4bcIObclJbc2ac3ac4J 符合johnson不等式， min(bci,aci+1)=min(bci+1,aci) 優(yōu)； 紅線右側(cè)滿足bci=min(bci+1,aci) 優(yōu)； 中間過渡部分橫向比較，左側(cè) bci+1=min(bci+1,aci) 優(yōu)； 程序具體代碼如下: cppviewplaincopy 1. /3d9動態(tài)規(guī)劃流水作業(yè)調(diào)度問題 2. #includestdafx.h 3. #include 4. usingnamespacestd; 5. 6. constintN=5; 7. 8. classJobtype 9. 10. public

11、: 11. intoperator=(Jobtypea)const 12. 13. return(key=a.key); 14. 紅線左側(cè)滿足aci=bci 和aci=bci+1 其調(diào)度順序最 acibci右側(cè) 其調(diào)度順序也最 intkey,index; booljob; )； intFlowShop(intn,inta口，intb,intc); voidBubbleSort(Jobtype*d,intn);/本例采用冒泡排序 cout作業(yè)在機器1上的運行時間為：endl; for(inti=0;iN;i+)coutai; )coutendl; cout作業(yè)在機器2上的運行時間為：endl;

12、for(inti=0;iN;i+)coutbi; )coutendl; cout完成作業(yè)的最短時間為：minTimeendl; cout編號從0開始，作業(yè)調(diào)度的順序為：endl; for(inti=0;iN;i+)coutci; )coutendl;return0; ) intFlowShop(intn,inta口，intb,intc口) Jobtype*d=newJobtypen; for(inti=0;ibi?bi:ai;/按Johnson法則分別取對應(yīng)的bi或 ai值作為關(guān)鍵字 di.job=ai=bi;給符合條件aibi的放入到N1子集標(biāo)記為 true di.index=i; Bubb

13、leSort(d,n);/對數(shù)組d按關(guān)鍵字升序進行排序 intj=0,k=n-1; for(inti=0;in;i+) if(di.job) cj+=di.index;/將排過序的數(shù)組d,取其中作業(yè)序號屬于 N1的從前面進入 else ck-=di.index;屬于N2的從后面進入，從而實現(xiàn)N1的非 減序排序，N2的非增序排序 j=ac0; k=j+bc0; for(inti=1;in;i+) j+=aci;/M1在執(zhí)行ci作業(yè)的同時，M2在執(zhí)行ci-1號作業(yè)，最 短執(zhí)行時間取決于M1與M2誰后執(zhí)行完 k=jk?k+bci:j+bci;/計算最優(yōu)加工時間 deleted; returnk; /冒泡排序 voidBubbleSort(Jobtype*d,intn) inti,j,flag; Jobtypetemp;58. 59. . 60. . 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. for(i=0;ii;j-) /如果前一個數(shù)大于后一個數(shù)，則交換 if(dj=dj-1) temp=dj; dj=dj-1; dj-1=temp; flag