【分支限界法】–作业调度问题 批处理作业调度 算法

问题导入：

给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理，最后由机器3处理。对于一个确定的作业调度，在机器数<=3时存在最优解。批处理作业调度问题要求对于给定的n个作业，m台机器，制定最佳作业调度方案，使其完成所有作业调度总时长达到最小。

例如：给定4个作业，3台机器，相关分析和代码分析如下：

                                                        作业调度问题

                                                   求下界方法

                            解空间树

代码：

//分支限界法求解作业调度问题(三台机器，四种作业)
//精髓：确定下界(可贪心)以便剪枝+优先队列+广搜;
#include <bits/stdc++.h>
using namespace std;
const int N=1000;
int n,m;
int a[N][N];
int ub[N+1];
int ans=1000,Min=1000;
vector<int> curStatus(N, 0);


struct node{
    int num;//节点编号
    int k;//已调度作业数
    int sum1;//各作业在第一台机器上的时间和
    int sum2;//各作业在第二台机器上的时间和
    int Lb;//时间总和
    vector<int> status;//各作业状态
 
    node(int _num, int _k,int _sum1,int _sum2,int _Lb, vector<int> _status) : num(_num), k(_k), sum1(_sum1), sum2(_sum2), Lb(_Lb) ,status(_status){}

    friend bool operator<(node a, node b) {
        if(a.k==b.k) return a.Lb>b.Lb;// 自定义优先队列的比较函数，总时长Lb小的先出队;
        else return a.k<b.k;
    }

};


void BFS(){
    priority_queue<node> Q;//创建优先队列
    Q.push(node(0,1,0,0,0,curStatus));优先队列初始值
    while(!Q.empty()){
        node u = Q.top();//获取队首元素;
        Q.pop();
        if(u.Lb>Ub)//如果大于上界，及时剪枝(止损);
            continue;
        if(u.k==n+1){//达到叶子结点，更新ans并进行输出;
            ans=min(ans,u.Lb);
            //cout<<ans<<endl;
            continue;
        }

        for (int i = 1; i <= n; i++) {
            if (u.status[i]==0) {//检查状态数组对应的未加工的作业;
                vector<int> newStatus = u.status;//以下是更新编号,sum1,sum2,Lb,Status值;
                newStatus[i] = 1;
                int new_num=u.num+1;
                int new_k=u.k+1;
                int new_sum1=u.sum1+a[i][1];
                int new_sum2=max(new_sum1,u.sum2)+a[i][2];
                int new_Lb=new_sum2;

                for(int j=1;j<=n;j++){//计算Lb值;
                    if(newStatus[j]==0){
                        new_Lb+=a[j][2];
                        Min=min(Min,a[j][3]);
                    }

                }
                new_Lb+=Min;
                //cout<<new_Lb<<endl;//计算对应的sum1,sum2,Lb;
                Q.push(node(new_num,new_k,new_sum1,new_sum2,new_Lb,newStatus));//将新节点加入优先队列;
            }
}

}
cout<<"Lb="<<ans<<endl;
cout<<"最优解为:"<<ans<<endl;
}


int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            ub[j]=max(ub[j-1],ub[j])+a[i][j];

        }
    }

    Ub=ub[m];//ub数组下标记录对应第几台机器的完成时间;
    cout<<"Ub="<<Ub<<endl;
    BFS();

    return 0;
}


//测试样例：
/*
4 3
7 8 10
9 6 4
5 9 7
10 7 5
*/
//测试输出：
Ub=43
Lb=41
最优解为41

运行结果：

相信有很多方法处理类似的问题，包括动态规划，回溯法。作为第一篇博客，我希望用分支限界，可能不如其他方法简洁，但是这种包含哲理的方法，提前看到最优结果，选择最优路径，进行评估选择，是一种高效和智慧的搜索方法，愿你我的人生都能因这种智慧乘风破浪。
与君共勉

欢迎评论区指出改进之处，一起交流学习啊。