-
回溯法——批处理作业调度
问题描述：
给定n个作业的集合J=（J1，J2，... ，Jn）。每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先有机器1处理，然后再由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=F2i，称为该作业调度的完成时间和。
简单描述：
对于给定的n个作业，指定最佳作业调度方案，使其完成时间和达到最小。
举例说明：
| tji | 机器1 | 机器2 |
| 作业1 | 2 | 1 |
| 作业2 | 3 | 1 |
| 作业3 | 2 | 3 |
这3个作业的调度方案共有6种（即3个作业的全排列），分别是123,132,213,231,312,321，它们所相应的完成时间和分别是19,18,20,21,19,19。显而易见，最佳调度方案是132，其完成时间和为18。
算法设计：
从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时x=[1,2, ... , n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。
类Flowshop的数据成员记录解空间的结点信息，以便减少传给Backtrack的参数。二维数组M是输入作业的处理时间，bestf记录当前最小完成时间和，bestx记录相应的当前最佳作业调度。
在递归函数Backtrack中，
当i>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。
当i<n时，当前扩展结点位于排列树的第（i-1）层，此时算法选择下一个要安排的作业，以深度优先方式递归的对相应的子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。
算法描述：
注：1、区分作业i和当前第i个正在执行的作业
给x赋初值，即其中一种排列，如x=[1,3,2]；M[x[j]][i]代表当前作业调度x排列中的第j个作业在第i台机器上的处理时间；如M[x[2]][1]就意味着作业3在机器1上的处理时间。
2、bestf的初值
此问题是得到最佳作业调度方案以便使其完成时间和达到最小，所以当前最优值bestf应该赋值为较大的一个值。
3、f1、f2的定义与计算
假定当前作业调度排列为：x=[1,2,3]；f1[i]即第i个作业在机器1上的处理时间，f2[j]即第j个作业在机器2上的处理时间；则：
f1[1]=M[1][1] , f2[1]=f1[1]+M[1][2]
f1[2]=f1[1]+M[2][1] , f2[2]=MAX(f2[1],f1[2])+M[2][2] //f2[2]不光要等作业2自己在机器1上的处理时间，还要等作业1在机器2上的处理时间，选其大者。
f1[3]=f1[2]+M[3][1] , f2[3]=MAX(f2[2],f1[3])+M[3][2]
f1只有当前值有用，可以覆盖赋值，所以定义为int型变量即可，减少空间消耗；f2需要记录每个作业的处理时间，所以定义为int *型，以便计算得完成时间和。
4、f2[0]的初值
f2[i]的计算都是基于上一个作业f2[i-1]进行的，所以要记得给f2平[0]赋值为0。
1 class Flowshop 2 { 3 friend Flow(int * *,int,int[]); 4 private: 5 void Backtrack(int i); 6 int * * M, //各作业所需的处理时间，根据上面的例子就是4*3的矩阵————M[j][i]代表第j个作业在第i台机器上的处理时间 7 * x, //当前作业调度————其中一种排列顺序 8 * bestx, //当前最优作业调度 9 * f2, //机器2完成处理时间————记录每个作业在机器2上的完成时间 10 f1, //机器1完成处理时间————定义int型，减少空间消耗（因为只有当前的f1有用，所以可以覆盖赋值） 11 f, //完成时间和 12 bestf, //当前最优值 13 n; //作业树 14 }; 15 void Flowshop::Backtrack(int i) 16 { 17 if(i>n) 18 { 19 for(int j=1;j<=n;j++) 20 bestx[j] = x[j]; 21 bestf = f; 22 } 23 else 24 { 25 for(int j=i;j<=n;j++) //排列树中j从i开始————控制分支数 26 { 27 f1+=M[x[j]][i]; //在第1台机器上的完成处理时间————着重关注M矩阵的行标（代表当前执行的作业，是动态变化的） 28 f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2]; //在机器2上的完成处理时间，f2[0]初值赋为0 29 f+=f2[i]; //总的完成时间和 30 if(f<bestf) //剪枝函数 31 { 32 Swap(x[i],x[j]); 33 Backtrack(i+1); 34 Swap(x[i],x[j]); 35 } 36 f1 -= M[x[j]][1]; //改变机器完成时间计数————递归返回时 37 f -= f2[i]; 38 } 39 } 40 } 41 int Flow(int * * M,int n,int bestx[]) 42 { 43 int ub = INT_AMX; 44 Flowshop X; 45 X.x = new int [n+1]; 46 X.f2 = new int [n+1]; 47 X.M = M; 48 X.n = n; 49 X.bestf = ub; 50 X.bestx = bestx; 51 X.f1 = 0; 52 X.f = 0; 53 for(int i=0;i<=n;i++) 54 { 55 X.f2[i] = 0; 56 X.x[i] i; 57 } 58 X.Backtrack(1); 59 delete [] X x; 60 delete [] X f2; 61 return X.bestf; 62 }
具体实现 示例代码：
1 #include <iostream> 2 using namespace std; 3 #define MAX 200 4 int* x1;//作业Ji在机器1上的工作时间； 5 int* x2;//作业Ji在机器2上的工作时间； 6 7 int number=0;//作业的数目； 8 9 int* xOrder;//作业顺序； 10 int* bestOrder;//最优的作业顺序； 11 12 int bestValue=MAX;//最优的时间； 13 int xValue=0;//当前完成用的时间； 14 int f1=0;//机器1完成的处理时间； 15 int* f2;//第i阶段机器2完成的时间； 16 17 18 void BackTrace(int k) 19 { 20 if (k>number) 21 { 22 for (int i=1;i<=number;i++) 23 { 24 bestOrder[i]=xOrder[i]; 25 } 26 bestValue=xValue; 27 } 28 else 29 { 30 for (int i=k;i<=number;i++) 31 { 32 f1+=x1[xOrder[i]]; 33 f2[k]=(f2[k-1]>f1?f2[k-1]:f1)+x2[xOrder[i]]; 34 xValue+=f2[k]; 35 swap(xOrder[i],xOrder[k]); 36 if (xValue<bestValue) 37 { 38 BackTrace(k+1); 39 } 40 swap(xOrder[i],xOrder[k]); 41 xValue-=f2[k]; 42 f1-=x1[xOrder[i]]; 43 } 44 45 } 46 } 47 int main() 48 { 49 cout<<"请输入作业数目："; 50 cin>>number; 51 x1=new int[number+1]; 52 x2=new int[number+1]; 53 xOrder=new int[number+1]; 54 bestOrder=new int[number+1]; 55 f2=new int[number+1]; 56 57 x1[0]=0; 58 x2[0]=0; 59 xOrder[0]=0; 60 bestOrder[0]=0; 61 f2[0]=0; 62 63 cout<<"请输入每个作业在机器1上所用的时间："<<endl; 64 for (int i=1;i<=number;i++) 65 { 66 cout<<"第"<<i<<"个作业="; 67 cin>>x1[i]; 68 } 69 70 cout<<"请输入每个作业在机器2上所用的时间："<<endl; 71 for (i=1;i<=number;i++) 72 { 73 cout<<"第"<<i<<"个作业="; 74 cin>>x2[i]; 75 } 76 77 for (i=1;i<=number;i++) 78 { 79 xOrder[i]=i; 80 } 81 BackTrace(1); 82 cout<<"最节省的时间为："<<bestValue; 83 cout<<endl; 84 cout<<"对应的方案为："; 85 for (i=1;i<=number;i++) 86 { 87 cout<<bestOrder[i]<<" "; 88 } 89 return 0; 90 }
原文：https://www.cnblogs.com/xymqx/p/3724366.html
