1.问题描述
    给定n个作业的集合J={J1,J2,…,Jn}。每一个作业有两项任务分别在两台机器上完成。每个作业必须先由机器1处理，再由机器2处理。作业Ji需要机器j的处理时间为tji，i=1,2,…n，j=1,2。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。则所有作业在机器2上完成处理的时间和f=F21+F22+…+F2n称为该作业调度的完成时间和。
    批处理作业调度问题要求，对于给定的n个作业，制定最佳的作业调度方案，使其完成时间和最小。
    样例输入：
    3
    2 1
    3 1
    2 3
    样例输出：
    18
    1 3 2
    2. 算法描述
    算法中用活节点优先队列。元素类型是Node。每一个Node类型的节点包含域x,用来表示节点所相应的作业调度。s表示该作业已安排的作业时x[1:s]。f1表示当前已安排的作业在机器1上的最后完成时间；f2表示当前已安排作业在机器2上的完成时间；sf2表示当前已安排的作业在机器2上的完成时间和；bb表示当前完成时间和下界。二维数组M表示所给的n个作业在机器1和机器2所需的处理时间。函数Bound用于计算完成时间和下界。
    函数flowShop中while循环完成对排列树内部结点的有序扩展。在while循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。算法将当前扩展节点E分两种情形处理：
    1)当E.s=bestc时，可将结点node舍去。
    2)E.s=n的情形，当前节点为最优解。

    1. #include<iostream>
    2. using namespace std;
    4. int  n1;            // 作业数
    5. int f1 = 0;         // 机器1完成处理时间
    6. int f = 0;          // 完成时间和
    7. int bestf = 10000;  // 当前最优值
    8. int m[100][100];    // 各作业所需的处理时间
    9. int x[100];         // 当前作业调度
    10. int best_x[100];     // 当前最优作业调度
    11. int f2[100];        // 机器2完成处理时间
    13. void backtrack(int i)
    14. {
    15.     if (i > n1 && f < bestf)          //到达叶子结点，搜索到最底部且存在最优解
    16.     {
    17.         for (int j = 1; j <= n1; j++)
    18.             best_x[j] = x[j];
    19.         bestf = f;
    20.     }
    21.     else
    22.         for (int j = i; j <= n1; j++)
    23.         {
    24.             f1 += m[x[j]][1];
    25.             f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + m[x[j]][2];   //上一个任务在机器2上完成的时间是否大于本次任务在1上完成的时间
    26.             f += f2[i];
    27.             if (f < bestf)
    28.             {
    29.                 swap(x[i], x[j]);//交换两个作业的位置
    30.                 backtrack(i + 1);
    31.                 swap(x[i], x[j]);
    32.             }
    33.             f1 -= m[x[j]][1];
    34.             f -= f2[i];
    35.         }
    36. }
    38. int main()
    39. {
    40.     cout << "请输入作业数：";
    41.     cin >> n1;
    42.     cout << "请输入在各机器上的处理时间" << endl;
    43.     for (int i = 1; i <= n1; i++)
    44.         for (int j = 1; j <= 2; j++)
    45.             cin >> m[i][j];
    47.     for (int i = 1; i <= n1; i++)
    48.         x[i] = i;       //初始化
    49.     backtrack(1);
    51.     cout << "最少完成时间: " << bestf << endl << "最优调度: ";
    52.     for (int i = 1; i <= n1; i++)
    53.         cout << best_x[i] << " ";
    54.     cout << endl;
    55.     return 0;
    56. }
    1. #include<iostream>
    2. #include<queue>
    3. using namespace std;
    5. struct Node
    6. {
    7.     int s;          //已安排作业数
    8.     int f1;         //机器1上最后完成时间
    9.     int f2;         //机器2上最后完成时间
    10.     int sf2;        //当前机器2完成时间和
    11.     int* x;         //当前作业调度
    12. };
    14. const int MAX = 100;
    15. const int MACHINE = 2;
    16. int n;                    //作业数
    17. int M[MAX][MACHINE];      //各作业所需时间，键盘输入
    18. int b[MAX][MACHINE];      //各作业所需时间排序后
    19. int a[MAX][MACHINE];      //数组m和b的对应关系
    20. bool y[MAX][MACHINE];     //工作数组
    21. int bestx[MAX];           //最优解
    22. int bestc = 1e6;         //最小完成时间和
    24. queue<Node> q;    //队列
    26. //最小堆节点初始化
    27. Node Init()
    28. {
    29.     Node node;
    30.     node.x = new int[n];
    31.     for (int i = 0; i < n; i++)
    32.         node.x[i] = i;
    33.     node.s = 0;
    34.     node.f1 = 0;
    35.     node.f2 = 0;
    36.     node.sf2 = 0;
    37.     return node;
    38. }
    40. //最小堆新节点
    41. Node NewNode(Node E, int Ef1, int Ef2)
    42. {
    43.     Node node = Init();
    44.     node.x = new int[n];
    45.     for (int i = 0; i < n; i++)
    46.         node.x[i] = E.x[i];
    47.     node.f1 = Ef1;
    48.     node.f2 = Ef2;
    49.     node.sf2 = E.sf2 + Ef2;         //E為父結點，計算子結點当前机器2完成时间和
    50.     node.s = E.s + 1;
    51.     return node;
    52. }
    54. void sort() {
    55.     int* c = new int[n];
    56.     for (int j = 0; j < 2; j++)                     //对机器1和机器2别排序，并在a数组中记录作业序号
    57.     {
    58.         for (int i = 0; i < n; i++)
    59.         {
    60.             b[i][j] = M[i][j];
    61.             c[i] = i;
    62.         }
    63.         for (int i = 0; i < n - 1; i++)
    64.             for (int k = n - 1; k > i; k--)
    65.                 if (b[k][j] < b[k - 1][j])
    66.                 {
    67.                     swap(b[k][j], b[k - 1][j]);
    68.                     swap(c[k], c[k - 1]);
    69.                 }
    70.         for (int i = 0; i < n; i++)
    71.             a[c[i]][j] = i;
    72.     }
    73.     delete[]c;
    74. }
    76. //排序结果：
    77. /*b[][]
    78. 2 - 1
    79. 2 - 1
    80. 3 - 3
    81. */
    82. /*a[][]
    83. 0 * 0
    84. 2 * 1
    85. 1 * 2
    86. */
    87. //计算完成时间下界
    88. int Bound(Node E, int& f1, int& f2)
    89. {
    90.     for (int k = 0; k < n; k++)
    91.         for (int j = 0; j < 2; j++)
    92.             y[k][j] = false;
    93.     for (int k = 0; k <= E.s; k++)
    94.         for (int j = 0; j < 2; j++)
    95.             y[a[E.x[k]][j]][j] = true;
    97.     f1 = E.f1 + M[E.x[E.s]][0];
    98.     f2 = ((f1 > E.f2) ? f1 : E.f2) + M[E.x[E.s]][1];
    100.     int sf2 = E.sf2 + f2;
    101.     int s1 = 0, s2 = 0;
    102.     int k1 = n - E.s, k2 = n - E.s;
    103.     int f3 = f2;
    105.     for (int j = 0; j < n; j++)             //计算s1
    106.         if (!y[j][0])
    107.         {
    108.             k1--;
    109.             if (k1 == n - E.s - 1)
    110.                 f3 = (f2 > f1 + b[j][0]) ? f2 : f1 + b[j][0];
    111.             s1 += f1 + k1 * b[j][0];
    112.         }
    113.     for (int j = 0; j < n; j++)             //计算s2
    114.         if (!y[j][1])
    115.         {
    116.             k2--;
    117.             s1 += b[j][1];
    118.             s2 += f3 + k2 * b[j][1];
    119.         }
    120.     return sf2 + (s1 > s2 ? s1 : s2);       //返回完成计算的时间下界
    121. }
    123. void flowShop()
    124. {
    125.     sort();                                 //机器1和机器2上所需时间排序
    127.     Node E = Init();
    129.     while (E.s <= n)                        //搜索排列树
    130.     {
    131.         if (E.s == n && E.sf2 < bestc)      //叶节点且存在最优解——>更新
    132.         {
    133.             bestc = E.sf2;
    134.             for (int i = 0; i < n; i++)
    135.                 bestx[i] = E.x[i];
    136.             delete[]E.x;
    137.         }
    138.         else
    139.         {                                   //产生扩展当前节点的儿子节点
    140.             for (int i = E.s; i < n; i++)
    141.             {
    142.                 int f1, f2;                 //計算机器1、机器2上最后完成时间
    143.                 swap(E.x[E.s], E.x[i]);
    144.                 int bb = Bound(E, f1, f2);
    145.                 if (bb < bestc)             //子树可能含有最优解
    146.                     q.push(NewNode(E, f1, f2));
    147.                 swap(E.x[E.s], E.x[i]);
    148.             }
    149.             delete[]E.x;
    150.         }                           //完成节点扩展
    152.         if (q.empty())
    153.             break;
    154.         E = q.front();
    155.         q.pop();
    156.     }
    157. }
    158. void BFS() {
    159.     cout << "请输入作业数：";
    160.     cin >> n;
    161.     cout << "输入作业所需时间：";
    162.     for (int i = 0; i < n; i++)         /*初始化*/
    163.         for (int j = 0; j < 2; j++)
    164.             cin >> M[i][j];
    166.     flowShop();
    168.     cout << "最少完成时间: " << bestc << endl << "最优调度: ";
    169.     for (int i = 0; i < n; i++)
    170.         cout << bestx[i] + 1 << " ";
    171.     cout << endl;
    172. }
    174. int main()
    175. {
    176.     BFS();      //分支限界
    177.     //DFS();      //回溯
    178.     return 0;
    179. }
    182. /*
    183.  * 測試1：
    184.  * 请输入作业数：3
    185.  * 输入作业所需时间：2 1 3 1 2 3
    186.  * 測試2：
    187.  * 请输入作业数：3
    188.  * 输入作业所需时间：2 3 5 2 4 1
    189.  */
    #include<iostream>
#include<queue>
using namespace std;

struct Node
{
    int s;          //已安排作业数
    int f1;         //机器1上最后完成时间
    int f2;         //机器2上最后完成时间
    int sf2;        //当前机器2完成时间和
    int bb;         //当前完成时间下界
    int* x;         //当前作业调度
    bool operator < (const Node& node) const {
        return bb > node.bb;
        //return sf2 > node.sf2;            //效率低
    }
};

const int MAX = 100;
const int MACHINE = 2;
int n;                    //作业数
int M[MAX][MACHINE];      //各作业所需时间，键盘输入
int b[MAX][MACHINE];      //各作业所需时间排序后
int a[MAX][MACHINE];      //数组m和b的对应关系
bool y[MAX][MACHINE];     //工作数组
int bestx[MAX];           //最优解
int bestc = 1e6;          //最小完成时间和

priority_queue<Node> q;    //优先队列

//最小堆节点初始化
Node Init()
{
    Node node;
    node.x = new int[n];
    for (int i = 0; i < n; i++)
        node.x[i] = i;
    node.s = 0;
    node.f1 = 0;
    node.f2 = 0;
    node.sf2 = 0;
    node.bb = 0;
    return node;
}

//最小堆新节点
Node NewNode(Node E, int Ef1, int Ef2, int Ebb)
{
    Node node;
    node.x = new int[n];
    for (int i = 0; i < n; i++)
        node.x[i] = E.x[i];
    node.f1 = Ef1;
    node.f2 = Ef2;
    node.sf2 = E.sf2 + Ef2;
    node.bb = Ebb;
    node.s = E.s + 1;
    return node;
}

void sort() {
    int* c = new int[n];
    for (int j = 0; j < 2; j++)
    {
        for (int i = 0; i < n; i++)
        {
            b[i][j] = M[i][j];
            c[i] = i;
        }
        for (int i = 0; i < n - 1; i++)
            for (int k = n - 1; k > i; k--)
                if (b[k][j] < b[k - 1][j])
                {
                    swap(b[k][j], b[k - 1][j]);
                    swap(c[k], c[k - 1]);
                }
        for (int i = 0; i < n; i++)
            a[c[i]][j] = i;
    }
    delete[]c;
}

//计算完成时间上界
int Bound(Node E, int& f1, int& f2)
{
    for (int k = 0; k < n; k++)
        for (int j = 0; j < 2; j++)
            y[k][j] = false;
    for (int k = 0; k <= E.s; k++)
        for (int j = 0; j < 2; j++)
            y[a[E.x[k]][j]][j] = true;

    f1 = E.f1 + M[E.x[E.s]][0];
    f2 = ((f1 > E.f2) ? f1 : E.f2) + M[E.x[E.s]][1];
    int sf2 = E.sf2 + f2;
    int s1 = 0, s2 = 0;
    int k1 = n - E.s, k2 = n - E.s;
    int f3 = f2;
    for (int j = 0; j < n; j++)             //计算s1
        if (!y[j][0])
        {
            k1--;
            if (k1 == n - E.s - 1)
                f3 = (f2 > f1 + b[j][0]) ? f2 : f1 + b[j][0];
            s1 += f1 + k1 * b[j][0];
        }
    for (int j = 0; j < n; j++)             //计算s2
        if (!y[j][1])
        {
            k2--;
            s1 += b[j][1];
            s2 += f3 + k2 * b[j][1];
        }
    return sf2 + (s1 > s2 ? s1 : s2);       //返回完成计算的时间下界
}
void flowShop()
{
    sort();                                 //机器1和机器2上所需时间排序

    Node E = Init();

    while (E.s < n)                         //搜索排列数
    {                                       //产生扩展当前节点的儿子节点
        for (int i = E.s; i < n; i++)
        {
            int f1, f2;
            swap(E.x[E.s], E.x[i]);
            int bb = Bound(E, f1, f2);
            if (bb < bestc)             //子树可能含有最优解
                q.push(NewNode(E, f1, f2, bb));
            swap(E.x[E.s], E.x[i]);
        }
        delete[]E.x;                    //完成节点扩展

        if (q.empty())
            break;                
        E = q.top();
       /* cout << E.bb << "   " << E.sf2 << endl;*/
        q.pop();
        if (E.s == n)      //叶节点且是最优解
        {
            bestc = E.sf2;
            for (int i = 0; i < n; i++)
                bestx[i] = E.x[i];
            delete[]E.x;
        }
    }
    while (!q.empty()) {
        E = q.top();
        q.pop();
        delete[] E.x;
    }           //清空队列            
}

int main(){
    cout << "请输入作业数：";
    cin >> n;
    cout << "输入作业所需时间：";
    for (int i = 0; i < n; i++)         /*初始化*/
        for (int j = 0; j < 2; j++)
            cin >> M[i][j];

    flowShop();

    cout << "最少完成时间: " << bestc << endl << "最有调度: ";
    for (int i = 0; i < n; i++)
        cout << bestx[i] + 1 << " ";
    cout << endl;
    return 0;
}