批处理作业调度 解空间:排列树 private static void backtrack (int i) if (i>n 4 for(int j=1; j<=n; j++) best[]=xu] best f 3 else for(int j=i; j<=n; j++) f1+=mj]1 12=(f2[-1]>升1)?f2[-1:f1)+mx][2l; 千+=f12[ if(f< besto)i public class FlowShop My Math. swap(x, i,j) static int n,∥作业数 backtrack(i+1) f1,∥机器1完成处理时间 MyMath. swap(x, i, j) f,∥完成时间和 best;∥/当前最优值 f1=m[×j[1 static int [l m;∥/各作业所需的处理时间 f=f2[ static int [x;∥/当前作业调度 static int l best;∥/当前最优作业调度 static int [ f2;∥机器2完成处理时间12 批处理作业调度 •解空间：排列树 private static void 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]][1]; f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2]; f+=f2[i]; if (f < bestf) { MyMath.swap(x,i,j); backtrack(i+1); MyMath.swap(x,i,j); } f1-=m[x[j]][1]; f-=f2[i]; } } public class FlowShop static int n, // 作业数 f1, // 机器1完成处理时间 f, // 完成时间和 bestf; // 当前最优值 static int [][] m; // 各作业所需的处理时间 static int [] x; // 当前作业调度 static int [] bestx; // 当前最优作业调度 static int [] f2; // 机器2完成处理时间