回溯算法批处理作业调度问题

• 1、问题描述

• 给定n个作业的集合J={j1，j2，j3，…jn},每一个作业都有两项任务分别在两台机器上完成。每个作业必须先由机器1处理，再由机器2处理。作业Ji需要机器j的处理时间为tij,设Fij是作业i在机器j上的完成处理时间。所有作业在机器2上处理的时间和称为该作业调度的完成时间和。

• 批处理作业调度问题要求对于给定的N个作业，制定最佳作业调度方案，使其完成时间和达到最小。其中最典型的一个例子就是在计算机系统中完成一批n个作业，每个作业都先完成计算，然后将计算结果打印出来。

• 示例：

   		tji          机器1     机器2
   		作业1         2          1
   		作业2         3          1
   		作业3         2          3
   	在这个例子中。最优调度顺序为：1 3 2；处理时间为：18
  

• 2、算法描述

• 从n个作业的所有排列中找出有最小完成时间和的作业调度，所以批处理调度问题是一颗排列树按照回溯搜索排列树的算法框架，设开始时x=[1,2,3,4…,n]是所给的n个作业，则相应的排列树由 x[1,n]的所有排列构成。

• 在递归方法backtrack中,当i>n时，算法搜索至叶结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前作业调度。

• 当i<n时，当前扩展结点位于排列树的第i-1层。此时算法选择下一个要安排的作业，以深度优先的方式递归的对相应字数进行搜索。对于不满足上届约束的结点，则减去相应的子树。

• 程序初始化：

	int x[100];//记录当前调度
	int bestx[100];//记录当前最优调度
	int m[100][100];//在第i太机器上处理j作业的时间
	int f1=0,f2=0,cf=0,bestf=10000,n;//bestf记录当前最小完成时间

3、程序代码：

void swap(int *x,int t,int j)
 {
	int temp=x[t];
	x[t]=x[j];
	x[j]=temp;
 }

 void Backtrack(int t)
 {
	int tempf,j,i;
	if(t>n)
	{
		for(i=1;i<=n;i++)
			bestx[i]=x[i];
			bestf=cf;
	}
	else
	{
		for(j=t;j<=n;j++)
		{
			f1+=m[x[j]][1];//记录作业在第一台机器上的完成处理时间
			tempf=f2;//保存上一个作业在机器2的完成处理时间
			f2=(f1>f2?f1:f2)+m[x[j]][2];//保存当前作业在机器2的完成时间
			cf+=f2;//cf记录当前在机器2上的完成时间和
			if(cf<bestf)
			{
				swap(x,t,j);
				Backtrack(t+1);
				swap(x,t,j);
			}
			f1-=m[x[j]][1];
			cf-=f2;
			f2=tempf;
		}
	}
 }