分支限界法解作业分配问题的实现（C++）

#include<iostream>
using namespace std;
#define MAX_FLOAT_NUM 10000.0
#define N 4

struct ass_node{
	int x[N];   //分配给操作员的作业
	int k;      //搜索深度
	float t;    //当前搜索深度下，已分配的作业所需时间
	float b;     //本结点所需的时间下界
	struct ass_node *next;
};

typedef struct ass_node ASS_NODE;

float c[N][N];   //n个操作员分别完成n项作业所需的时间
float bound;    //当前已搜索到的可行解的最优时间
ASS_NODE *qbase;  //优先队列的首指针

void Q_insert(ASS_NODE *qbase,ASS_NODE *xnode){
	ASS_NODE *p;
	if(qbase->next==NULL){
		qbase->next=xnode;
		xnode->next=NULL;
	}
	else if(xnode->b < qbase->next->b){
		xnode->next=qbase->next;
		qbase->next=xnode;
	}
	else{
		p=qbase->next;
		while(p->next){
			if((xnode->b > p->b)&&(xnode->b < p->next->b)){
				xnode->next=p->next;
				p->next=xnode;
				break;
			}
			p=p->next;
		}
		if(p->next==NULL){
			p->next=xnode;
			xnode->next=NULL;
		}
	}

}



ASS_NODE *Q_delete(ASS_NODE *qbase){
	ASS_NODE *p;
	p=qbase->next;
	qbase->next=p->next;
	return p;
}

float job_assigned(float c[][N],int n,int job[])
{
	int i,j,m;
	ASS_NODE *xnode,*ynode,*qbase;
	qbase=new ASS_NODE;
	qbase->next=NULL;
	float min,bound=MAX_FLOAT_NUM;
	xnode=new ASS_NODE;
	for(i=0;i<n;i++)      //初始化xnode所指向的根结点
		xnode->x[i]=-1;  
	xnode->t=xnode->b=0;
	xnode->k=0;
	while(xnode->k!=n){          //非叶子结点，继续向下搜索
		for(i=0;i<n;i++){            //对n 个操作员分别判断处理
			if(xnode->x[i]==-1){    //操作员i尚未分配作业
				ynode=new ASS_NODE;   //为操作员i建立一个结点         
				*ynode=*xnode;         //把父亲结点的数据复制给它
				ynode->x[i]=ynode->k;    //把作业k分配给操作员i
				ynode->t +=c[i][ynode->k];   //已分配的作业的时间累计
				ynode->b=ynode->t;
				ynode->k++;                  //该结点下一次的搜索深度
				for(j=ynode->k;j<n;j++){      //未分配作业最小时间估计
					min=MAX_FLOAT_NUM;
					for(m=0;m<n;m++){
						if((ynode->x[m]==-1)&&(c[m][j]<min))
							min=c[m][j];
					}
					ynode->b += min;
				}
				if(ynode->b<bound){        //小于可行解的最优下界
					Q_insert(qbase,ynode);   //把结点按下界插入优先队列
					if(ynode->k==n)           //已得到一个可行解
						bound=ynode->b;        //更新可行解的最优下界
				}
				else delete ynode;           //大于可行解的最优下界，剪除
			}
		}
		delete xnode;                    //释放结点xnode的缓冲区
		xnode=Q_delete(qbase);           //取下对首元素xnode
	}
	min=xnode->b;           //保存下界，以便作为返回值返回
	for(i=0;i<n;i++)         //把分配方案保存与数组job中返回
		job[i]=xnode->x[i];  
	while(qbase->next){     //释放结点缓冲区
		xnode=Q_delete(qbase);
		delete xnode;
	}
	return min;
}

void main()
{
	int i,j;
	int job[N];
	cout<<"请输入各操作员完成各项作业所需要的时间:"<<endl;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			cin>>c[i][j];
	cout<<"完成任务的最优时间为:\n";
	cout<<job_assigned(c,4,job)<<endl;
	cout<<"作业分配方案为："<<endl;
	cout<<"作业号:\t0\t1\t2\t3\t"<<endl;
	cout<<"操作员:\t"<<job[0]<<"\t"<<job[1]<<"\t"<<job[2]<<"\t"<<job[3]<<"\t"<<endl;
	cout<<"耗  时:\t"<<c[0][job[0]]<<"\t"<<c[1][job[1]]<<"\t"<<c[2][job[2]]<<"\t"<<c[3][job[3]]<<"\t"<<endl;

}