流水作業(yè)調(diào)度

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

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

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

4、集S在機(jī)器M2的等待時(shí)間為t時(shí)的任一最優(yōu)調(diào)度。若在這個(gè)調(diào)度中，安排在最前面的兩個(gè)作業(yè)分別是i和j,記(1)i,(2)j，由動(dòng)態(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,則稱(chēng)作業(yè)i和作業(yè)j滿足Johnson不等式。如果作業(yè)i和作業(yè)j不滿足Johnson不等式，則交換作業(yè)i和作業(yè)j的加工順序后，作業(yè)i和作業(yè)j滿足Johns

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

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

7、度下總的調(diào)度時(shí)間。(4) 輸出最優(yōu)調(diào)度方案的模塊：輸出最優(yōu)調(diào)度安排方式和最優(yōu)調(diào)度所用的時(shí)間。整體架構(gòu)如下main初始化Johnson算法顯示結(jié)果四、詳細(xì)設(shè)計(jì)五、1、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：為了實(shí)現(xiàn)Johnson算法，本項(xiàng)目采用以下的數(shù)據(jù)結(jié)構(gòu):typedefstructintkey,index;booljob;Jobtype;typedefstructJobtyperMAXSIZE;intlength;Sjob;ey>j.key)t=i;i=j;j=t;/*執(zhí)行Johnson算法確定最優(yōu)調(diào)度*/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ù)調(diào)用關(guān)系:六、編碼#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è)個(gè)數(shù)是：");scanf("%d",&n);printf("第一個(gè)的加工時(shí)間是：");for(i=0;i<n;i+)scanf("%d,",&ai);printf("第二個(gè)的加工時(shí)間是：");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("最短加工完成時(shí)間是%dn",m);七、測(cè)試在運(yùn)行dos窗口下輸入命令，這次測(cè)試輸入4個(gè)作業(yè)，得出了如下結(jié)果:進(jìn)行一組測(cè)試，得出了如下結(jié)果：若按照J(rèn)ohnson算法手工做題，可知知道N仁0,2,3,N2=1最優(yōu)調(diào)度是0,2,3,1計(jì)算的最優(yōu)調(diào)度時(shí)間是38再次進(jìn)行一組測(cè)試，這次再次測(cè)試4個(gè)作業(yè)的情況，在N1和N2中各有兩個(gè)作業(yè)的情況。得到了如下結(jié)果：計(jì)穿機(jī)卻法設(shè)計(jì)'作業(yè)涼水謂度Pressenykeytocontinue頃術(shù)錢(qián)電的作業(yè)個(gè)數(shù)是i4懐二個(gè)的加工可間是；5,12,2第二木的加工時(shí)|可JE；4,14,8,1712S最裁加工完成時(shí)間是的如按照手工計(jì)算，可知N仁1,3,N2=0,2,排序后的最優(yōu)調(diào)度是3,1,2,0,和程序結(jié)果一致，而且最優(yōu)調(diào)度時(shí)間也是45再次進(jìn)行一次較為合理的測(cè)試：若出現(xiàn)兩個(gè)作業(yè)的加工時(shí)間一樣，這次作業(yè)的個(gè)數(shù)是6個(gè)，作業(yè)1和作業(yè)5在兩個(gè)機(jī)器上的加工時(shí)間是一樣的得到如下的結(jié)果：E5:計(jì)算機(jī)算袪設(shè)計(jì)'作業(yè)涼水調(diào)度Debujjob.«e2BTrBTr“作二二的結(jié)個(gè)個(gè);38是：數(shù)是是卜一日_ztn、J-業(yè)£LPans*Keytoc