成为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的
n
个作业
，
制定一个最佳的作业调度方案
，
使其完成时间和达到最小。
批处理作业调度问题的一个常见例子是在计算机系统中完成一批
n
个作业，每个作业都要完成先计算，然
后将计算机结果打印输出这两项任务
。
计算任务由计算机的中央处理器完成
，
打印输出任务由打印机完成。
因此在这种情况下，计算机的中央处理器是机器
1
，打印机是机器
2
。
关于输入
要求输入：
1
、作业数
2
、每个作业完成时间表，如下
;
作业完成时间
机器
1
机器
2
作业
1
2
1
作业
2
3
1
作业
3
2
3
分析：给定
n
个作业的集合
{J1,J2,…,Jn}
。每个作业必须先由机器
1
处理，然后由机器
2
处理。作业
Ji
需
要机器
j
的处理时间为
tji
。对于一个确定的作业调度，设
Fji
是作业
i
在机器
j
上完成处理的时间。所有作
业在机器
2
上完成处理的时间和称为该作业调度的完成时间和。
这
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
。

批处理作业调度
临近考试，又仔细复习了一遍，感觉比以前刚刚学的时候更加深刻和理解。以下是算法思想和代码。有不对的地方请指教。
给定n个作业，每一个作业都有两项任务分别在2台机器上完成。每个作业ji必须先有机器1处理，然后再由机器2处理。作业需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理时间。则所有作业在机器2上完成处理时间和f=F2i，称为该作业调度的完成时间和。

简单描述

对于给定的n个作业，指定最佳作业调度方案，使其完成时间和达到最小。

算法设计

类Flowshop的数据成员记录解空间的结点信息，M输入作业时间，bestf记录当前最小完成时间和，bestx记录相应的当前最佳作业调度。在递归函数Backtrack中，当i>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。当i<n时，当前扩展结点在i-1层，以深度优先方式，递归的对相应子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。

算法描述

class Flowshop{    
    friend Flow(int * *,int,int[]);
private:
    void Backtrack(int i);
    int * * M, * x, * bestx, * f2, f1, f,    bestf, n;
};
void Flowshop::Backtrack(int i){    
    if(i>n){
        if(f＞bestf){
             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]][i]; 
            f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];            
            f+=f2[i];     
            if(f<bestf){       
                Swap(x[i],x[j]);   
                Backtrack(i+1);     
                Swap(x[i],x[j]);     
            }           
            f1 -= M[x[j]][1];       
            f -= f2[i];      
        }   
    }
}
int Flow(int * * M,int n,int bestx[]){ 
    int ub = INT_AMX;   
    Flowshop X;  
    X.x = new int [n+1];    
    X.f2 = new int [n+1];   
    X.M = M;    
    X.n = n;   
    X.bestf = ub; 
    X.bestx = bestx;  
    X.f1 = 0;  
    X.f = 0;   
    for(int i=0;i<=n;i++){       
        X.f2[i] = 0;       
        X.x[i]=1;
    }
    X.Backtrack(1);
    delete [] X.x;   
    delete [] X.f2;   
    return X.bestf;
}

回溯法之批处理作业调度
1. 问题描述
​n个作业集合{1, 2, ..., n}。每个作业先由机器1处理，再由机器2处理。作业i需要机器j处理的时间为Mij 。
Mij
机器1
机器2
作业1
2
1
作业2
3
1
作业3
2
3
​对于一个确定的作业调度，设Fij 是作业i在机器j上完成的具体时间。所有作业在机器2上完成的具体时间(时刻)之和f称为该作业调度的完成时间和。
​要求：对于给定的n个作业，制定最佳作业调度方案(一个排列)，使其完成时间和达到最小
2. 问题分析
​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。
​Fi1、Fi2表示事件i分别在机器1和机器2上完成的时间。
作业顺序
Fi1
Fi2
f
begin
0
0
0
①
2
3
3
③
4
7
10
②
7
8
18
​假设此时1-2-3的作业调度已经完成计算，遍历到了1-3-2的序列。
​首先是①，将调用f1 += M[x[j]][1];表示作业1在机器1需要2时间才能完成，接下来使用f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];比较F02 和 F11 的大小，即需要等待前一个作业在机器2完成计算才能在机器2开始本次作业，再使用F02 和 F11的较大值F11+作业2在机器2的工作时间1得到F12为3，在使用f += f2[i]，将3赋值给f。
​到③，调用f1 += M[x[j]][1];，F21变为2+2=4，再比较F12和F21，将较大的F21+3=7赋值给F22。f变为10。
​到②，F31变为7，比较F22和F31，将7+1=8复制给F32，最终将f变为18，得到最终结果。
3. 代码求解
​该问题的解空间：排列树：
​
​使用到的全局变量：
M        各作业所需的处理时间
x        当前作业调度
bestx    当前最优作业调度
f2       机器2完成的处理时间
f1       机器1完成的处理时间
f        完成时间和
bestf    当前最优值
n        作业数
​核心求解代码：
void BackTrack(int i) {
// i > n表示已经访问到叶子结点，即一个作业调度遍历完成
// 将此时的最优解暂时保存到bestx中
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];
// 如果f小于当前的最小值，代表这个分支可以继续运算，否则直接裁去该分支，达到优化算法的目的
if (f < bestf) {
swap(i, j);
// 递归求解
BackTrack(i + 1);
// 递归运算后，需要回退到上一层排列树
swap(i, j);
}
// 本条路径求解结束后回退到原本的状态
f1 -= M[x[j]][1];
f -= f2[i];
}
}
}
4. 完整代码
/**
* 回溯法求解批处理作业调度问题
*
* 主要由BackTrack函数递归调用求解问题
* 使用bsetf保存最优解，bestx保存最优的作业调度序列
**/
#include 
#include 
#define MAXROW 4
#define MAXCOL 3
/**
* M        各作业所需的处理时间
* x        当前作业调度
* bestx    当前最优作业调度
* f2       机器2完成的处理时间
* f1       机器1完成的处理时间
* f        完成时间和
* bestf    当前最优值
* n        作业数
**/
int M[MAXROW][MAXCOL], x[MAXROW], bestx[MAXROW], f2[MAXROW], f1, f, bestf, n;
// 值交换函数
void swap(int i, int j) {
int tmp = x[i];
x[i] = x[j];
x[j] = tmp;
}
void BackTrack(int i) {
// i > n表示已经访问到叶子结点，即一个作业调度遍历完成
// 将此时的最优解暂时保存到bestx中
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) {
swap(i, j);
BackTrack(i + 1);
swap(i, j);
}
f1 -= M[x[j]][1];
f -= f2[i];
}
}
}
void main() {
n = 3;
bestf = INT_MAX;
M[1][1] = 2;M[1][2] = 1;
M[2][1] = 3;M[2][2] = 1;
M[3][1] = 2;M[3][2] = 3;
for (int i = 0; i <= n; i++) {
f2[i] = 0;
x[i] = i;
}
BackTrack(1);
printf("%d\n", bestf);
for (int i = 1; i <= n; i++) {
printf("%d ", bestx[i]);
if (i != n)
printf("-> ");
}
printf("\n");
system("pause");
}

批处理作业调度问题的java实现(回溯法)
具体问题描述以及C/C++实现参见网址
http://blog.csdn.net/liufeng_king/article/details/8764319
/**
* 批处理作业调度问题--回溯法(排列树)
* @author Administrator
*
*/
public class FlowShop {
int n;//作业数
int f1;//机器1完成处理时间
int f;//完成时间和
int bestf;//当前最优值
int[][] m;//各作业所需的处理时间
int []x;//当前作业调度
int[] bestx;//当前最优作业调度
int[] f2;//机器2完成处理时间
public FlowShop(int n,int[][] m){
this.n=n;
this.m=m;
f1=0;
f=0;
bestf=10000;//给定初始值
bestx=new int[n+1];
x=new int[n+1];
//初始化，x[i]为原始排序
for(int i=1;i<=n;i++){
x[i]=i;
}
f2=new int[n+1];
}
public  void swap(int[] x,int i,int j){
int temp=x[i];
x[i]=x[j];
x[j]=temp;
}
public  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];//作业x[j]在第一台机器的时间
f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];//f2[i]等于f2[i-1]和f1中较大者加上作业x[j]在第2台机器的时间
f+=f2[i];
if(f
swap(x,i,j);
backtrack(i+1);
swap(x,i,j);
}
f1-=m[x[j]][1];
f-=f2[i];
}
}
}
public static void main(String[] args) {
int n=3;
int[][] m={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};//m的下标从1开始，因此第一行的0和每一行第一列的0无用
FlowShop f=new FlowShop(n,m);
f.backtrack(1);
System.out.println("最优批处理作业调度顺序为：");
for(int i=1;i<=n;i++)
System.out.print(f.bestx[i]+" ");
System.out.println();
System.out.println("最优调度所需的最短时间为："+f.bestf);
}
}
/*
运行结果：
最优批处理作业调度顺序为：
1 3 2
最优调度所需的最短时间为：18
*/