批处理作业调度问题·回溯法·java 版 问题描述： /************************************************************* 批处理作业调度 给定 n 个作业的集合{J1,J2,…,Jn}。 每个作业必须先由机器 1 处理，然后由机器 2 处理。 作业 Ji 需要机器 j 的处理时间为 tji。 对于一个确定的作业调度，设 Fji 是作业 i 在机器 j 上完成处理的时间。 所有作业在机器 2 上完成处理的时间和称为该作业调度的完成时间和。 f = F21 + F22 + F23 + ... + F2n 批处理作业调度问题要求对于给定的 n 个作业， 制定最佳作业调度方案，使其完成时间和达到最小。 *************************************************************/ public class FlowShop { int n, f1, f, bestf; //作业数； //机器 1 完成处理时间； //完成时间和； //当前最优值； int [][]m; int []x; int []bestx; int []f2; //各作业所需的处理时间； //当前作业调度； //当前最优作业调度； //机器 2 完成处理时间； void backtrack(int i) private { if(i>n) { for (int j=1;j<=n;j++) { bestx[j]=x[j]; System.out.print(x[j]+" "); } System.out.println(); bestf=f; System.out.println("每条深度优先搜索结果为："+bestf); } else for(int j=i;j<=n;j++) { 

f1+=m[x[j]][0]; f2[i]=((f2[i-1]>f1)? f2[i-1]:f1)+m[x[j]][1]; f+=f2[i]; // if(f

} public static void main(String[] args) { // TODO Auto-generated method stub FlowShop fs=new FlowShop(); fs.ShowTest(); } } class MyMath { public MyMath(){} public static int[] swap(int[] x,int i,int j) { // int[] returnString=new int[3]; int ss; ss=x[j]; x[j]=x[i]; x[i]=ss; return x; } }