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