批处理作业调度分支限界法

1、#include#includeusing namespace std;class MinHeapNodefriend class Flowshop;public:bool operator(const MinHeapNode &a) constreturn a.bbbb; private:void Init(int);void NewNode(MinHeapNode,int,int,int,int);int s; /已安排作业数int f1; /机器1上最后完成时间int f2; /机器2上最后完成时间int sf2; /当前机器2上的完成时间和int bb; /当前完成时间和下界int *

2、x; /当前作业调度;void MinHeapNode:Init(int n) /最小堆结点初始化x=new intn;for(int i=0;in;i+)xi=i;s=0;f1=0;f2=0;sf2=0;bb=0;void MinHeapNode:NewNode(MinHeapNode E,int Ef1,int Ef2,int Ebb,int n) /最小堆新结点x=new intn;for(int i=0;in;i+)xi=E.xi;f1=Ef1;f2=Ef2;sf2=E.sf2+f2;bb=Ebb;s=E.s+1;class Flowshopfriend int main();publ

3、ic:int BBFlow();private:Flowshop(int n); /构造函数Flowshop(); /析构函数int Bound(MinHeapNode,int &,int &,bool *); void Sort();int n;int *M;int *b;int *a;int *bestx;int bestc;bool *y;Flowshop:Flowshop(int n)/M=new int *n;b=new int *n;a=new int *n;y=new bool *n;bestx=new int n;bestc=10000;for(int i=0;in;i+)/M

4、i=new int2;bi=new int2;ai=new int2;yi=new bool2;Flowshop:Flowshop()for(int i=0;in;i+)delete Mi;delete bi;delete ai;delete yi;delete bestx,M,b,a,y;void Flowshop:Sort() /对各作业在机器1和2上所需时间进行冒泡排序 int *c=new intn;for(int j=0;j2;j+)for(int i=0;in;i+)bij=Mij;ci=i;for(i=0;ii;k-)if(bkjbk-1j)swap(bkj,bk-1j);swa

5、p(ck,ck-1);for(i=0;in;i+)acij=i;delete c;int Flowshop:Bound(MinHeapNode E,int &f1,int &f2,bool *y) /计算完成时间和下界for(int k=0;kn;k+)for(int j=0;j2;j+)ykj=0;for(k=0;k=E.s;k+)for(int j=0;jE.f2)?f1:E.f2)+ME.xE.s1;int sf2=E.sf2+f2;int s1=0,s2=0,k1=n-E.s,k2=n-E.s,f3=f2;/计算s1的值for(int j=0;jf1+bj0)?f2:f1+bj0; s

6、1+=f1+k1*bj0;/计算s2的值for(j=0;js2)?s1:s2);int Flowshop:BBFlow()Sort();priority_queue H; MinHeapNode E;E.Init(n);while(E.s=n)if(E.s=n)if(E.sf2bestc)bestc=E.sf2;for(int i=0;in;i+)bestxi=E.xi; delete E.x;elsefor(int i=E.s;in;i+)swap(E.xE.s,E.xi);int f1,f2;int bb=Bound(E,f1,f2,y); if(bbbestc)MinHeapNode N;N.NewNode(E,f1,f2,bb,n); H.push(N);swap(E.xE.s,E.xi); delete E.x;if(H.empty()break;elseE=H.top();H.pop();return bestc;int main()int n;coutn;int *M=new int*n;for(int i=0;in;i+)Mi=new int2;for(i=0;in;i+)for(int j=0;j2;j+)coutMijMij;Flowshop G(n);G.M=M;