回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果不包含则跳过，逐层向其祖先结点回溯；否则进入子树看，继续按深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根结点的所有子树都搜索遍才结束。

批处理作业调度

一、问题描述

1.给定n个作业的集合{J1, J2, …, Jn}。每一个作业Ji都有两项任务需要分别在2台机器上完成。每个作业必须先由机器1处理,然后由机器2处理。

2.三个作业的调度方案对应三个作业的全排列。三个作业的6种可能的调度方案是1, 2, 3；1, 3, 2；2, 1, 3；2, 3, 1；3, 2, 1；3, 1, 2。批处理作业调度问题要求制定最佳作业调度方案，使其完成时间和达到最小。
3.举例：
设有一调度方案 x =[3, 1, 2] ，

对于x1 (作业3)： f2,1=2+3=5；
对于x2 (作业1) ：f2,2=5+1=6；
对于x3 (作业2) ：f2,3=7+1=8；
F=f2,1+f2,2+f2,3=5+6+8=19
19就是该作业调度方案 x =[3, 1, 2] 的时间和。
规定每一个作业用 记录其在机器2处理的时间，则

二、问题解决

package backtrack;

public class FlowShop {

    static int n=3; //作业数
    static int f1=0; //机器1完成处理的时间
    static int f=0;  //完成时间和
    static int bestf=9999;  //当前最优值
    static int[][] m=new int[n+1][n+1];  //各个作业的处理时间，如m[x[2]][1]表示，(其中x[2]=3)第2个作业所代表的作业3,在机器1上运行的时间，
//即前代表作业，后代表机器
    static int[] x=new int[n+1];  //当前作业的调度，如x={1,2,3}
    static int[] bestx=new int[n+1];  //当前最优作业调度
    static int[] f2=new int[n+1];  //机器2完成处理时间
    public static void backtrack(int i) {  //表示安排的第几个作业
        if(i>n) {  //当i大于n时说明已经到达了叶结点，找到当前最优值
//            System.out.print("当前最优值：");
            for(int j=1;j<=n;j++) { //记录最优作业调度和最优完成时间
                bestx[j]=x[j];
//                System.out.print(bestx[j]+" ");
                bestf=f;
            }
//            System.out.println();
//            System.out.println("bestf="+bestf);
        }
        else  //未达到叶结点时，继续搜索
            for(int j=i;j<=n;j++) {
//                System.out.println("i="+i);
//                System.out.println("j="+j);
                f1+=m[x[j]][1]; //作业在机器1上花费的时间（等待时间加自己本身的运行时间）
//                System.out.println("f1="+f1);
                f2[i]=(f2[i-1]>f1?f2[i-1]:f1)+m[x[j]][2];
//                System.out.println("f2="+f2[i]);
                /*
                 * 作业在机器2上花费的时间受两个因素影响：1.作业在机器1上花费的时间。2.上一个作业在机器2上花费的时间。
                 * 这两者的较大者就是作业在机器2上花费的时间。如作业1，2在机器1上的运行时间分别为｛1，3｝，在机器2上运行的时间分别为｛1，2｝，
                 * 那么如果作业1先运行，当祖业1在机器2上已经完成运行，作业2也不能立即在机器2上运行，因为这时作业2在机器1上还未运行完。
                 */
                f+=f2[i];  //所有作业的最终完成时间实际上就是在机器2上运行完所花费的时间
//                System.out.println("完成时间f="+f);
                if(f<bestf) {  //限界函数，看当前的调度方案是否优于当前最优值
//                    System.out.println("进入子树");
//                    System.out.println("第一次swap");
                    swap(i,j);
//                    System.out.print("x=");
//                    for(int k=1;k<=n;k++)
//                        System.out.print(x[k]+" ");
//                    System.out.println();
                    backtrack(i+1);
//                    System.out.println("第二次swap");
                    swap(i,j);
//                    for(int k=1;k<=n;k++)
//                        System.out.print(x[k]+" ");
                }
//                System.out.println();
                f1-=m[x[j]][1];
//                System.out.println("回溯f1="+f1);
                f-=f2[i];
//                System.out.println("回溯f="+f);
            }
    }

    public static void swap(int i,int j) {
        int temp=x[i];
        x[i]=x[j];
        x[j]=temp;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        n=3;
        int[] fa= {2,3,2};  //在机器1上的运行时间
        int[] fb={1,1,3};  //在机器2上的运行时间
        for(int i=1;i<=n;i++) {
            m[i][1]=fa[i-1];
            m[i][2]=fb[i-1];
        }
        for(int j=1;j<=n;j++)
            x[j]=j;
        for(int k=0;k<=n;k++)
            f2[k]=0;
        backtrack(1);
        System.out.print("最优调度方案:");
        for(int m=1;m<=n;m++)
            System.out.print("作业"+bestx[m]+" ");
        System.out.println();
        System.out.print("最少花费时间："+bestf);

    }

}

运行结果

运算过程

三、时间复杂度分析

批作业处理调度的解空间结构是一棵排列树，如果作业总数为n，那么排列树共有n!叶个结点，backtrack算法在每一个结点处耗费O(1)计算时间，所以在最坏情况下，整个算法的时间复杂度为O(n!)。