流水作業(yè)調度

1、流水作業(yè)調度一、可行性分析與項目開發(fā)計劃n個作業(yè)1,2,.n要在由2臺機器M1和M2組成的流水線上完成加工。每個作業(yè)的順序都是現(xiàn)在M1上加工，然后再M2上加工。M1和M2加工作業(yè)i所需的時間分別是ai和0，1<=i<=n流水作業(yè)調度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器M2上加工完成所需要的時間最少。直觀上，一個最優(yōu)調度應該使得機器M1沒有空閑時間，而且機器M2的空閑時間最少，在一般情況下，機器M2上會出現(xiàn)機器空閑和作業(yè)積壓兩種情況。設全部作業(yè)的集合為N=1,2,。SN是N的作業(yè)子集，在一般情況下，機器M1開始加工作業(yè)S中作

2、業(yè)時，機器M2還在加工其他作業(yè)，要等時間t后才可以利用。將這種情況下完成S中作業(yè)所需要的最短時間記做T(S,t)則流水作業(yè)調度問題的最優(yōu)值就是T(N,0).我們通過分析可以知道流水作業(yè)調度問題具有最優(yōu)子結構的性質，因此考慮用動態(tài)規(guī)劃算法自后向前來解決其最優(yōu)問題。這就需要通過建模來得出最優(yōu)子結構的遞歸式子，從而設計算法求解最優(yōu)值。二、需求分析1、用戶可以根據(jù)自己的需要輸入想要進入流水線的作業(yè)數(shù)。2、用戶可以輸入這幾個作業(yè)在機器M1和M2上的加工時間。3、由主函數(shù)調用流水作業(yè)調度的Johnson算法來實現(xiàn)對流水作業(yè)的安排。4、輸出經過Johnson算法安排后的作業(yè)序列，這就是最終的一個最優(yōu)調度。三

3、、概要設計總體設計：假定這n個作業(yè)在機器M1上加工時間為aj,在機器M2上加工時間為bi,1<=i<=n.由流水作業(yè)調度問題具有最優(yōu)子結構性質可知，T(N,0)minaiT(Ni,bi)1<=i<=n推廣到一般情況下，T(S,t)aiT(Si,bimaxtai,0)iS式子中，maxtai,0這一項是由于在機器M2上，作業(yè)i必須在maxt,ai時間之后才能開工，因此，在機器M1上完成作業(yè)加工i之后，在機器還需要bimaxt,aiaibmaxta"時間完成對作業(yè)i的加工。按照上述遞歸式，可以設計出流水作業(yè)調度問題的動態(tài)規(guī)劃算法，但是算法還可以進一步簡化。設是作業(yè)

4、集S在機器M2的等待時間為t時的任一最優(yōu)調度。若在這個調度中，安排在最前面的兩個作業(yè)分別是i和j,記(1)i,(2)j，由動態(tài)規(guī)劃遞歸式可得：T(S,t)aiT(Si,bimaxtai,0)aiajTSi,j,tijtijbjmaxbimaxtai,0aj,0bjbiajmaxmaxtai,0,0,ajbi其中bjbiajmaxtai,ajbi,0bjbiajaimaxt,aiajbi,ai如果作業(yè)i和作業(yè)j滿足minb,ajminbj,ai,則稱作業(yè)i和作業(yè)j滿足Johnson不等式。如果作業(yè)i和作業(yè)j不滿足Johnson不等式，則交換作業(yè)i和作業(yè)j的加工順序后，作業(yè)i和作業(yè)j滿足Johns

5、on不等式，而且不增加加工時間。因此，任意兩個滿足Johnson法則的調度具有相同的加工時間，從而所有滿足Johnson法則的調度均為最優(yōu)調度，流水作業(yè)調度問題轉化為求解滿足Johnson法則的調度問題。流水作業(yè)調度的Johnson算法：(1) 令N1=i|a：b,N2=i|a：bj;將N1中的作業(yè)按照a：的非減序排序，將N2中的作業(yè)按照bi的非增序排序；N1中作業(yè)接N2中作業(yè)構成滿足Johnson法則的最優(yōu)調度。1、為了實現(xiàn)上述算法，需要采用順序表的抽象數(shù)據(jù)類型ADTSqlist數(shù)據(jù)對象D：D是具有相同特征的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類型相同、可以唯一標識數(shù)據(jù)元素的關鍵字數(shù)據(jù)關系R:數(shù)

6、據(jù)元素同屬于一個集合?；静僮鳎簊ort(&L,n)初始條件:順序表L存在操作結果:對順序表L中的內容按關鍵字大小進行由小到大的排序Flowshop(n,a,b,c)初始條件:數(shù)組a.、b存在并且不為空，大小為n操作結果：執(zhí)行Johnson算法，并且返回最優(yōu)調度的時間長度，在數(shù)組c中存放最優(yōu)調度安排ADTSqlist2、本項目主要有以下幾個模塊：(1) 輸入需要調度作業(yè)的模塊：輸入作業(yè)的個數(shù)，以及在每個作業(yè)在機器M1和機器M2上需要加工的時間。(2) 排序模塊：對一個順序表按照關鍵字由小到大進行排序(3) 執(zhí)行Johnson算法模塊：對N個作業(yè)調用Johnson算法確定最優(yōu)調度和最優(yōu)調

7、度下總的調度時間。(4) 輸出最優(yōu)調度方案的模塊：輸出最優(yōu)調度安排方式和最優(yōu)調度所用的時間。整體架構如下main初始化Johnson算法顯示結果四、詳細設計五、1、數(shù)據(jù)結構的設計：為了實現(xiàn)Johnson算法，本項目采用以下的數(shù)據(jù)結構:typedefstructintkey,index;booljob;Jobtype;typedefstructJobtyperMAXSIZE;intlength;Sjob;ey>j.key)t=i;i=j;j=t;/*執(zhí)行Johnson算法確定最優(yōu)調度*/intFlowshop(intn,inta,intb,intc)inti;Sjobd;for(i=0;i

8、<n;i+)i.key=ai>bibi:ai;i.job=ai<=bi;i.index=i;sort(d,n);intj=0,k=n-1;for(i=0;i<n;i+)ifi.job)cj+=i.index;elseck-=i.index;j=ac0;k=j+bc0;for(i=1;i<n;i+)j+=aci;k=j<kk+bci:j+bci;returnk;函數(shù)調用關系:六、編碼#include""#defineMAXSIZE1000typedefstructintkey,index;booljob;Jobtype;typedefstr

9、uctJobtyperMAXSIZE;intlength;Sjob;ey>j.key)t=i;i=j;j=t;intFlowshop(intn,inta,intb,intc)inti;Sjobd;for(i=0;i<n;i+)i.key=ai>bibi:ai;i.job=ai<=bi;i.index=i;sort(d,n);intj=0,k=n-1;for(i=0;i<n;i+)ifi.job)cj+=i.index;elseck-=i.index;j=ac0;k=j+bc0;for(i=1;i<n;i+)j+=aci;k=j<kk+bci:j+bci

10、;returnk;voidmain()intn,i;intaMAXSIZE,bMAXSIZE,cMAXSIZE;printf("流水線中的作業(yè)個數(shù)是：");scanf("%d",&n);printf("第一個的加工時間是：");for(i=0;i<n;i+)scanf("%d,",&ai);printf("第二個的加工時間是：");for(i=0;i<n;i+)scanf("%d,",&bi);intm=Flowshop(n,a,b,c);

11、for(i=0;i<n;+i)printf("%d",ci);printf("n");printf("最短加工完成時間是%dn",m);七、測試在運行dos窗口下輸入命令，這次測試輸入4個作業(yè)，得出了如下結果:進行一組測試，得出了如下結果：若按照Johnson算法手工做題，可知知道N仁0,2,3,N2=1最優(yōu)調度是0,2,3,1計算的最優(yōu)調度時間是38再次進行一組測試，這次再次測試4個作業(yè)的情況，在N1和N2中各有兩個作業(yè)的情況。得到了如下結果：計穿機卻法設計'作業(yè)涼水謂度Pressenykeytocontinue頃術錢電的作業(yè)個數(shù)是i4懐二個的加工可間是；5,12,2第二木的加工時|可JE；4,14,8,1712S最裁加工完成時間是的如按照手工計算，可知N仁1,3,N2=0,2,排序后的最優(yōu)調度是3,1,2,0,和程序結果一致，而且最優(yōu)調度時間也是45再次進行一次較為合理的測試：若出現(xiàn)兩個作業(yè)的加工時間一樣，這次作業(yè)的個數(shù)是6個，作業(yè)1和作業(yè)5在兩個機器上的加工時間是一樣的得到如下的結果：E5:計算機算袪設計'作業(yè)涼水調度Debujjob.«e2BTrBTr“作二二的結個個;38是：數(shù)是是卜一日_ztn、J-業(yè)£LPans*Keytoc