問(wèn)題描述：給定n個(gè)作業(yè)的集合{J1,J2,…,Jn}。每個(gè)作業(yè)必須先由機(jī)器1處理，然后由機(jī)器2處理。作業(yè)Ji需要機(jī)器j的處理時(shí)間為tji。對(duì)于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。所有作業(yè)在機(jī)器2上完成處理的時(shí)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。

批處理作業(yè)調(diào)度問(wèn)題要求對(duì)于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。

這3個(gè)作業(yè)的6種可能的調(diào)度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所相應(yīng)的完成時(shí)間和分別是19，18，20，21，19，19。易見(jiàn)，最佳調(diào)度方案是1,3,2，其完成時(shí)間和為18。

以1,2,3為例:
作業(yè)1在機(jī)器1上完成的時(shí)間為2,在機(jī)器2上完成的時(shí)間為3
作業(yè)2在機(jī)器1上完成的時(shí)間為5,在機(jī)器2上完成的時(shí)間為6
作業(yè)3在機(jī)器1上完成的時(shí)間為7,在機(jī)器2上完成的時(shí)間為10
3+6+10=19，所以時(shí)間和為19。

以1,3,2為例:
作業(yè)1在機(jī)器1上完成的時(shí)間為2,在機(jī)器2上完成的時(shí)間為3
作業(yè)3在機(jī)器1上完成的時(shí)間為4,在機(jī)器2上完成的時(shí)間為7
作業(yè)2在機(jī)器1上完成的時(shí)間為7,在機(jī)器2上完成的時(shí)間為8
3+7+8=18，所以時(shí)間和為18。

批處理作業(yè)調(diào)度問(wèn)題要從n個(gè)作業(yè)的所有排列中找出具有最小完成時(shí)間和的作業(yè)調(diào)度，所以如圖，批處理作業(yè)調(diào)度問(wèn)題的解空間是一顆排列樹。按照回溯法搜索排列樹的算法框架，設(shè)開始時(shí)x=[1,2,……n]是所給的n個(gè)作業(yè)，則相應(yīng)的排列樹由x[1:n]的所有排列構(gòu)成。

算法分析：

#include<iostream>#include<stdlib.h> using namespace std; class Flowshop {public:int **M;//各作業(yè)需要的處理時(shí)間 int *x;//當(dāng)前作業(yè)調(diào)度 int *bestx;//當(dāng)前最優(yōu)作業(yè)調(diào)度 int *f2;//機(jī)器2完成處理時(shí)間 int f1;//機(jī)器1完成處理時(shí)間 int f;//完成時(shí)間和 int bestf;//當(dāng)前最優(yōu)值 int n;//作業(yè)數(shù)量 void Backtrack(int i);//回溯算法 };void Flowshop::Backtrack(int i) {if(i>n){for(int i=1;i<=n;i++)//記錄路徑 {bestx[i]=x[i];}bestf = f;//因?yàn)榈搅巳~子結(jié)點(diǎn)了，不需要判斷了 }else{for(int j=i;j<=n;j++)//分枝數(shù) {//設(shè)置作業(yè)在機(jī)器1完成的時(shí)間f1 +=M[x[j]][1];//回溯算法的關(guān)鍵 f2[i]=((f2[i-1]>f1)? f2[i-1]:f1) +M[x[j]][2];f+=f2[i];//回溯算法的關(guān)鍵 if(f<bestf){swap(x[i],x[j]);Backtrack(i+1);swap(x[i],x[j]);}f1 -=M[x[j]][1];//回溯算法的關(guān)鍵 f -=f2[i];//回溯算法的關(guān)鍵 } } } int Flow(int **M,int n,int bestx[])//初始化 {int ub = INT_MAX;Flowshop X;X.x = new int [n+1];X.f2 = new int [n+1];X.M=M;X.n=n;X.bestx=bestx;X.bestf = ub;X.f1 = 0;X.f = 0;for(int i=0;i<=n;i++){X.f2[i]=0,X.x[i]=i;}X.Backtrack(1);delete[] X.x;delete[] X.f2;return X.bestf; } int main() {int n;cout<<"請(qǐng)輸入要處理作業(yè)的數(shù)量：";cin>>n;int bestx[n+1];int **M =new int *[n+1];for(int i=0;i<n+1;i++){M[i]= new int [3];}cout<<"請(qǐng)輸入每個(gè)作業(yè)在兩個(gè)機(jī)器上工作的處理時(shí)間序列:(如1 2)："<<endl; for(int i=1;i<=n;i++){cin>>M[i][1]>>M[i][2];}cout<<"所有作業(yè)在機(jī)器2上的完成時(shí)間和(該作業(yè)調(diào)度的完成時(shí)間)為："<<Flow(M,n,bestx); }

算法的時(shí)間復(fù)雜度為O(n!)

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析——回溯法——批处理作业调度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。