算法設(shè)計(jì)與分析第08章-資料下載頁
2025-06-16 12:32本頁面
【正文】 NextValue(k,x)。 //產(chǎn)生 x[k]的下一個(gè)值 if (!x[k]) return。 //x[k]=0表示 x[k]已沒有可取值 if (k==n1) { //輸出一個(gè)哈密頓環(huán) for (int i=0。 in。 i++) coutx[i] 39。 39。 cout 0\n。 } else Hamiltonian(k+1,x)。 //深度優(yōu)先進(jìn)入下一層 } while (1)。 } void ExtMGraph:: Hamiltonian(int *x) { Hamiltonian(1,x)。 //x[0]=0為約定的起始結(jié)點(diǎn) } 批處理作業(yè)調(diào)度 問題描述 設(shè)有 n個(gè)作業(yè)的集合 {0,1,… ,n1}， 每個(gè)作業(yè)有兩項(xiàng)任務(wù) 要求分別在 2臺設(shè)備 P1和 P2上完成 。 每個(gè)作業(yè)必須先在 P1上加工 ， 然后在 P2上加工 。 P1和 P2加工作業(yè) i所需的時(shí)間分別為 ai和 bi。 作業(yè) i的完成時(shí)間 fi(S)是指在調(diào)度方案 S下 ， 該作業(yè)的所有任務(wù)得以完成的時(shí)間 ， 則 是采用調(diào)度方案 S的 平均完成時(shí)間 。 ????1n0ii )S(fn1)S(M FT 批處理作業(yè)調(diào)度 (batch job schedule)問題要求確定這 n個(gè)作業(yè)的最優(yōu)作業(yè)調(diào)度方案使其 MFT最小 。 這等價(jià)于求使得所有作業(yè)的完成時(shí)間之和 最小的調(diào)度方案 。 ????1n0ii )S(f)S(FT 例 8－ 5 設(shè)有三個(gè)作業(yè)和兩臺設(shè)備，作業(yè)任務(wù)的處理時(shí)間為（ a0,a1,a2） =(2,3,2)和（ b0,b1,b2） =(1,1,3)。這三個(gè)作業(yè)有 6種可能的調(diào)度方案： (0,1,2),(0,2,1),(1,0,2), (1,2,0),(2,0,1),(2,1,0),它們相應(yīng)的完成時(shí)間之和分別是19,18,20,21,19,19。其中，最佳調(diào)度方案 S=(0,2,1)。在這一調(diào)度方案下， f0(S)=3， f1(S)=7， f2(S)=8，F(xiàn)T=3+7+8=18。 回溯法求解 對于雙機(jī)批處理作業(yè)調(diào)度問題 ， 其可行解是 n個(gè)作業(yè)所有可能的排列 ， 每一種排列代表一種作業(yè)調(diào)度方案S， 其目標(biāo)函數(shù)是 使 FT(S)具有最小值的調(diào)度方案或作業(yè)排列是問題的最優(yōu)解 。 對于雙機(jī)作業(yè)調(diào)度 ， 存在一個(gè)最優(yōu)非搶先調(diào)度方案 ，使得在 P1和 P2上的作業(yè)完全以相同次序處理 。 批處理作業(yè)調(diào)度問題的狀態(tài)空間樹解空間的大小為 n！ 。 ????1n0ii )S(f)S(FT 求解這一問題沒有有效的約束函數(shù) ， 但可以使用最優(yōu)解的上界值 U進(jìn)行剪枝 。 如果對于已經(jīng)調(diào)度的作業(yè)子集的某種排列 ， 所需的完成時(shí)間和已經(jīng)大于迄今為止所記錄下的關(guān)于最優(yōu)調(diào)度方案的完成時(shí)間和的上界值 U,則該分枝可以剪去 。 批處理作業(yè)調(diào)度算法 【 程序 8－ 9】 批處理作業(yè)調(diào)度算法 class BatchJob{ public: BatchJob(int sz, int *aa,int *bb,int up) { n=sz。 U=up。 f=f1=0。 a=new int[n]。b=new int[n]。 f2=new int[n]。y=new int[n]。 for(int i=0。in。i++){ a[i]=aa[i]。b[i]=bb[i]。y[i]=i。 } } int JobSch(int *x)。 private: void JobSch(int i,int *x)。 int *a,*b,n,U, f,f1,*f2,*y。 }。 void BatchJob::JobSch(int i,int *x) { if (i==n) { for (int j=0。 jn。j++) x[j]=y[j]。 U=f。 } else for (int j=i。jn。j++) { f1+=a[y[j]]。 f2[i]=((f2[i1]f1)?f2[i?1]:f1)+b[y[j]]。 f+=f2[i]。 if (fU) { Swap(y,i,j)。 JobSch(i+1,x)。 Swap(y,i,j)。 } f1=a[y[j]]。f=f2[i]。 } } int BatchJob::JobSch(int *x) { JobSch(0,x)。 return U。 }
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1