问题描述
    给定 n 个作业的集合 j = {j1, j2, ..., jn}。每一个作业 j[i] 都有两项任务分别在两台机器上完成。每一个作业必须先由机器1 处理，然后由机器2处理。作业 j[i] 需要机器 j 的处理时间为 t[j][i] ，其中i = 1, 2, ..., n, j = 1, 2。对于一个确定的作业 调度，设F[j][i]是作业 i 在机器 j 上的完成处理的时间。所有作 业在机器2上完成处理的时间之和 f = sigma F[2][i] 称为该作业 调度的完成时间之和。

    批处理作业调度问题要求对于给定的 n 个作业，制定最佳作业调度 方案，使其完成时间和达到最小。

 

tji          机器1     机器2

作业1         2          1
作业2         3          1
作业3         2          3
这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；

它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。

以1,2,3为例:
作业1在机器1上完成的时间为2,在机器2上完成的时间为3
作业2在机器1上完成的时间为5,在机器2上完成的时间为6
作业3在机器1上完成的时间为7,在机器2上完成的时间为10
3+6+10=19，所以是19
1，3，2
作业1在机器1上完成的时间为2, 在机器2上完成的时间为3
作业3在机器1上完成的时间为4,在机器2上完成的时间为7
作业2在机器1上完成的时间为7,在机器2上完成的时间为8
3+7+8=18，所以时间和为18

 

分析：

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

 

代码实现：

1. Java实现

import java.util.*;

public class FlowShop
{
 static int n; //作业数
 static int f1; //机器1完成处理时间
 static int f; //完成时间和
 static int bestf; //当前最优值
 
 static int[][] m; //各作业所需要的处理时间
 static int[] x;  //当前作业调度
 static int[] bestx; //当前最优作业调度
 static int[] f2; //机器2完成处理时间

 public static void trackback(int i) {

                     //i用来指示到达的层数（第几步，从0开始），同时也指示当前执行完第几个任务

  if (i == n) { //得出一组最优值
      for (int j = 0; j < n; j++) {
          bestx[j] = x[j];
      }
      bestf = f;
  }
  else {
      for (int j = i; j < n; j++) {  //j用来指示选择了哪个任务（也就是执行顺序）  tb(0)进来了，不管怎么递归，就有j=0,1,2这三个过程，因此肯定能遍历完全

         f1 += m[x[j]][0];  //选择第x[j]个任务来执行

         if (i > 0) {  //选择出的不是第一个任务
             f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + m[x[j]][1];  //从f2[i - 1] 和 f1中选一个大的出来
        }
        else {//选择出的是第一个任务
          f2[i] = f1 + m[x[j]][1];
        }
        f += f2[i];
        if (f < bestf) {
          swap(x, i, j);  //关键：把选择出的任务j调到当前执行的位置i
          trackback(i + 1);  //选择下一个任务执行
          swap(x, i, j);  //递归后恢复原样
        }
        f1 -= m[x[j]][0];  //递归后恢复原样
        f -= f2[i];
    }
  }
 }

 private static void swap(int[] x, int i, int j) {

  int temp = x[i];
  x[i] = x[j];
  x[j] = temp;
 }

 private static void test() {

  n = 3;
  int[][] testm = {
{2, 1}, {3, 1}, {2, 3}};
  m = testm;

  int[] testx = {0, 1, 2};

  x = testx;
 
  bestx = new int[n];
  f2 = new int[n];
 

  f1 = 0;

  f = 0;
  bestf = Integer.MAX_VALUE;

  trackback(0);  //起点可变用trackback(0)，如果从一定点开始，就要用trackback(1)

  System.out.println(Arrays.toString(bestx));
  System.out.println(bestf);
 }
 public static void main(String[] args)
 {
  test();
  System.out.println("Hello World!");
 }
}

 

2.C++实现

 #include<stdio.h>

#include<string.h>
#define N 3//作业数目
#define MAX 1000
int x[N+1]={0,1,2,3};
int m[3][N+1]={
    0,0,0,0,
    0,2,3,2,
    0,1,1,3
    };
int bestx[N+1];//用于保存结果调度顺序
int f2[N+1];//第i阶段机器2完成处理的时间
int f1=0;//机器1完成处理时间
int f=0;//当前完成时间和
int bestf=MAX;
void swap(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}
void Backtrace(int t)
{
    if(t>N)
    {
        bestf=f;
        for(int i=1;i<=N;i++)
        {
            bestx[i]=x[i];
        }
    }
    else
    {
        for(int i=t;i<=N;i++)
        {

            f1+=m[1][x[i]];

            f2[t]=(f2[t-1]>f1?f2[t-1]:f1)+m[2][x[i]];
            f+=f2[t];
            swap(x[t],x[i]);
            if(f<bestf)
            {
                Backtrace(t+1);
            }
            swap(x[t],x[i]);
            f1-=m[1][x[i]];
            f-=f2[t];
       }
    }
}
int main()
{
    memset(bestx,0,(N+1)*sizeof(int));
    memset(f2,0,(N+1)*sizeof(int));
    Backtrace(1);
    printf("该作业调度的最优完成时间和为：%d\n调度顺序为：\n",bestf);
    for(int i=1;i<=N;i++)
    {
        printf("%d ",bestx[i]);
    }
    return 0;
}

 

来源：http://blog.sina.com.cn/s/blog_690e57390100kf3p.html