1、问题描述(排列树)

给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和,即F12+F22 +F32+…+Fn2。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

２、简单描述

对于给定的n个作业，指定最佳作业调度方案，使其完成时间和达到最小。
区别于流水线调度问题：批处理作业调度旨在求出使其完成时间和（第一个最终完成时间+第二个最终完成时间+第三个最终完成时间）达到最小的最佳调度序列；
流水线调度问题旨在求出使其最后一个作业的完成时间最小的最佳调度序列；

3、算法分析

从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。
类Flowshop的数据成员记录解空间的结点信息，以减少传给Backtrack的参数

int n; // 作业数
int f1=0; // 机器1完成处理时间
int f=0; // 完成时间和
int bestf=10000; // 当前最优值
int m[100][100]; // 各作业所需的处理时间，m[j][i]表示在第i台机器上作业j的处理时间
int x[100]; // 当前作业调度
int bestx[100]; // 当前最优作业调度
int f2[100]; // 机器2完成处理时间
初始时，x[i]=i ; bestx[i]=∞; (i=0,1,…,n)

示例

tji 机器1 机器2
作业1 2 1
作业2 3 1
作业3 2 3

调度分析

处理结束时间：10，“结束时间和”：3+6+10=19

处理结束时间：8，“结束时间和”：3+7+8=18
……
最优调度顺序：1 3 2
处理时间：18

比较

在递归函数Backtrack中:
1、当i>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。
2、当i<=n时，当前扩展结点在i层，以深度优先方式，递归的对相应子树进行搜索，对不满足上界约束的结点，则剪去相应的子树。

时间复杂度

算法backtrack在每个节点处耗费的时间O(1)计算时间，因此在最坏的情况下，整个算法时间复杂度为O(n!)

 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];
                    //上一个任务在机器2上完成的时间是否大于本次任务在1上完成的时间
            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];
        }
}

#include<iostream>
using namespace std;
int  n;             // 作业数
int f1=0;           // 机器1完成处理时间
int f=0;            // 完成时间和
int bestf=10000;    // 当前最优值
int m[100][100];    // 各作业所需的处理时间
int x[100];         // 当前作业调度
int bestx[100];     // 当前最优作业调度
int f2[100];        // 机器2完成处理时间
 void 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]][1];
            f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];
                    //上一个任务在机器2上完成的时间是否大于本次任务在1上完成的时间
            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 main()
{
    int i, j;
    cout << "请输入作业数：" << endl;
    cin >> n;
    cout << "请输入在各机器上的处理时间" << endl;
    for (i = 1; i <= 2; i++)
        for (j = 1; j <= n; j++)
            cin >> m[j][i];
    for (i = 1; i <= n; i++)
        x[i] = i;//初始化
    backtrack(1);
    cout << "调度作业顺序：" << endl;
    for (i = 1; i <= n; i++)
        cout << bestx[i] << ' ';
    cout << endl;
    cout << "处理时间：" << endl;
    cout << bestf;
    return 0;
}
/*
测试数据：
3
2 3 2
1 1 3
3
2 5 4
3 2 1
*/