有一個流水作業排程問題，n=4，a[]={5,10,9,7}，b[]={7,5,9,8}，請實作基于優先隊列的分枝限界算法進行求解。

#問題：

有一個流水作業排程問題，n=4，a[]={5,10,9,7}，b[]={7,5,9,8}，請實作基于優先隊列的分枝限界算法進行求解。
           

##源代碼：

//有一個流水作業排程問題，n=4，a[]={5,10,9,7}，b[]={7,5,9,8}，請實作基于優先隊列的分枝限界算法進行求解。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 999999
#define	MAX 5

using namespace std;

//問題表示
int n = 4; //作業數
int a[MAX] = { 0,5,10,9,7 };//M1上的執行時間,不用下标0的元素
int b[MAX] = { 0,7,5,9,8 };//M2上的執行時間,不用下标0的元素
//求解結果表示
int bestf = INF;//存放最優排程時間
int bestx[MAX];//存放目前作業最佳排程
int total = 1;//結點個數累計

struct NodeType//隊列結點類型
{
    int no;//結點編号
    int x[MAX];//x[i]表示第i步配置設定作業編号
    int y[MAX];//y[i]=1表示編号為i的作業已經配置設定
    int i;//步驟編号
    int f1;//已經配置設定作業M1的執行時間
    int f2;//已經配置設定作業M2的執行時間
    int lb;//下界
    bool operator<(const NodeType& s) const//重載<關系函數
    {
        return lb > s.lb;//lb越小越優先出隊
    }
};

void bound(NodeType& e)//求結點e的限界值
{
    int sum = 0;
    for (int i = 1; i <= n; i++)//掃描所有作業
    {
        if (e.y[i] == 0)
        {
            sum += b[i];//僅累計e.x中還沒有配置設定的作業的b時間
        }
    }
    e.lb = e.f1 + sum;
}

void bfs()//求解流水作業排程問題
{
    NodeType e, e1; priority_queue<NodeType> qu;//定義優先隊列
    memset(e.x, 0, sizeof(e.x));//初始化根結點的x
    memset(e.y, 0, sizeof(e.y));//初始化根結點的y
    e.i = 0;//根結點
    e.f1 = 0;
    e.f2 = 0;
    bound(e);
    e.no = total++;
    qu.push(e);//根結點進隊列
    while (!qu.empty())
    {
        e = qu.top();
        qu.pop(); //出隊結點e
        if (e.i == n) //達到葉子結點
        {
            if (e.f2 < bestf) //比較求最優解
            {
                bestf = e.f2;
                for (int j1 = 1; j1 <= n; j1++)
                {
                    bestx[j1] = e.x[j1];
                }
            }
        }
        e1.i = e.i + 1;//擴充配置設定下一個步驟的作業，對應結點e1
        for (int j = 1; j <= n; j++)//考慮所有的n個作業
        {
            if (e.y[j] == 1)
            {
                continue;//作業j是否已配置設定,若已配置設定，跳過
            }
            for (int i1 = 1; i1 <= n; i1++)//複制e.x得到e1.x
            {
                e1.x[i1] = e.x[i1];
            }
            for (int i2 = 1; i2 <= n; i2++)//複制e.y得到e1.y
            {
                e1.y[i2] = e.y[i2];
            }
            e1.x[e1.i] = j;//為第i步配置設定作業j
            e1.y[j] = 1;//表示作業j已經配置設定
            e1.f1 = e.f1 + a[j];//求f1=f1+a[j]
            e1.f2 = max(e.f2, e1.f1) + b[j];//求f[i+1]=max(f2[i],f1)+b[j]
            bound(e1);
            if (e1.f2 <= bestf)//剪枝,剪去不可能得到更優解的結點
            {
                e1.no = total++;//結點編号增加1
                qu.push(e1);
            }
        }
    }
}

int main()
{
    bfs();
    cout << "Optimal plan is :" << endl;
    for (int k = 1; k <= n; k++)
    {
        cout << "The " << k << " step is to execute the job is :" << bestx[k] << endl;
    }
    cout << "The total time is :" << bestf << endl;
    cout << "Ahui nb Ahui nb!";
    return 0;
}