问题描述：
给定n个作业，集合J=（J1，J2，J3）。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=F2i，称为该作业调度的完成时间和。
简单描述：
对于给定的n个作业，指定最佳作业调度方案，使其完成时间和达到最小。
算法设计：
从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。
类Flowshop的数据成员记录解空间的结点信息，M输入作业时间，bestf记录当前最小完成时间和，bestx记录相应的当前最佳作业调度。
在递归函数Backtrack中，
当i>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。
当i<n时，当前扩展结点在i-1层，以深度优先方式，递归的对相应子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。
算法描述：
class Flowshop { friend Flow(int * *,int,int[]); private: void Backtrack(int i); int * * M, * x, * bestx, * f2, f1, f, bestf, n; }; void Flowshop::Backtrack(int i) { if(i>n) { for(int j=1;j<=n;j++) bestx[j] = x[j]; bestf = f; } else { for(int j=i;j<=n;j++) { f1+=M[x[j]][i]; f2=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2]; f+=f2[i]; if(f<bestf) { Swap(x[i],x[j]); Backtrack(i+1); Swap(x[i],x[j]); } f1 -= M[x[j]][1]; f -= f2[i]; } } } int Flow(int * * M,int n,int bestx[]) { int ub = INT_AMX; Flowshop X; X.x = new int [n+1]; X.f2 = new int [n+1]; X.M = M; X.n = n; X.bestf = ub; X.bestx = bestx; 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; }
实例代码：
#include <iostream> using namespace std; #define MAX 200 int* x1;//作业Ji在机器1上的工作时间； int* x2;//作业Ji在机器2上的工作时间； int number=0;//作业的数目； int* xOrder;//作业顺序； int* bestOrder;//最优的作业顺序； int bestValue=MAX;//最优的时间； int xValue=0;//当前完成用的时间； int f1=0;//机器1完成的处理时间； int* f2;//第i阶段机器2完成的时间； void BackTrace(int k) { if (k>number) { for (int i=1;i<=number;i++) { bestOrder[i]=xOrder[i]; } bestValue=xValue; } else { for (int i=k;i<=number;i++) { f1+=x1[xOrder[i]]; f2[k]=(f2[k-1]>f1?f2[k-1]:f1)+x2[xOrder[i]]; xValue+=f2[k]; swap(xOrder[i],xOrder[k]); if (xValue<bestValue) { BackTrace(k+1); } swap(xOrder[i],xOrder[k]); xValue-=f2[k]; f1-=x1[xOrder[i]]; } } } int main() { cout<<"请输入作业数目："; cin>>number; x1=new int[number+1]; x2=new int[number+1]; xOrder=new int[number+1]; bestOrder=new int[number+1]; f2=new int[number+1]; x1[0]=0; x2[0]=0; xOrder[0]=0; bestOrder[0]=0; f2[0]=0; cout<<"请输入每个作业在机器1上所用的时间："<<endl; for (int i=1;i<=number;i++) { cout<<"第"<<i<<"个作业="; cin>>x1[i]; } cout<<"请输入每个作业在机器2上所用的时间："<<endl; for (i=1;i<=number;i++) { cout<<"第"<<i<<"个作业="; cin>>x2[i]; } for (i=1;i<=number;i++) { xOrder[i]=i; } BackTrace(1); cout<<"最节省的时间为："<<bestValue; cout<<endl; cout<<"对应的方案为："; for (i=1;i<=number;i++) { cout<<bestOrder[i]<<" "; } return 0; }
本文转自博客园xingoo的博客，原文链接：批处理作业调度-回溯法，如需转载请自行联系原博主。
