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

1、#include<iostream> #include<queue> using namespace std;class MinHeapNodefriend class Flowshop;public:bool operator<(const MinHeapNode &a) constreturn a.bb<bb; private: void Init(int);void NewNode(MinHeapNode,int,int,int,int);int s; /已安排作业数int f1; /机器 1 上最后完成时间int f2; /机器 2 上最后完

2、成时间int sf2; /当前机器 2 上的完成时间和int bb; /当前完成时间和下界int *x; / 当前作业调度;void MinHeapNode:Init(int n) / 最小堆结点初始化x=new intn;for(int i=0;i<n;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;i<n;i+) xi=E.xi;f1=Ef1;f2=Ef2;s

3、f2=E.sf2+f2; bb=Ebb; s=E.s+1; class Flowshop friend int main(); public: 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;

4、 b=new int *n; a=new int *n; y=new bool *n; bestx=new int n; bestc=10000; for(int i=0;i<n;i+) /Mi=new int2; bi=new int2; ai=new int2; yi=new bool2;Flowshop:Flowshop()for(int i=0;i<n;i+)delete Mi;delete bi;delete ai;delete yi;delete bestx,M,b,a,y;void Flowshop:Sort() / 对各作业在机器 1 和 2 上所需时间进行冒泡排序

5、 int *c=new intn; for(int j=0;j<2;j+)for(int i=0;i<n;i+) bij=Mij; ci=i; for(i=0;i<n-1;i+) for(int k=n-1;k>i;k-) if(bkj<bk-1j) swap(bkj,bk-1j); swap(ck,ck-1); for(i=0;i<n;i+) acij=i;delete c;int Flowshop:Bound(MinHeapNode E,int &f1,int &f2,bool *y) / 计算完成时间和 下界for(int k=0;k&

6、lt;n;k+)for(int j=0;j<2;j+) ykj=0;for(k=0;k<=E.s;k+)for(int j=0;j<2;j+) yaE.xkjj=1; f1=E.f1+ME.xE.s0;f2=(f1>E.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;j<n;j+) if(!yj0) k1-;if(k1=n-E.s-1) f3=(f2>f1+bj0)?f2:f1+bj0; s1+=f1+k1*bj

7、0;/计算 s2 的值 for(j=0;j<n;j+) if(!yj1) k2-; s1+=bj1;s2+=f3+k2*bj1; /返回完成时间和下界 return sf2+(s1>s2)?s1:s2);int Flowshop:BBFlow()Sort(); priority_queue<MinHeapNode> H; MinHeapNode E;E.Init(n);while(E.s<=n)if(E.s=n)if(E.sf2<bestc)bestc=E.sf2;for(int i=0;i<n;i+) bestxi=E.xi; delete E.x;

8、elsefor(int i=E.s;i<n;i+)swap(E.xE.s,E.xi);int f1,f2;int bb=Bound(E,f1,f2,y); if(bb<bestc) 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; cout<<" 输入作业数 :" cin>>n; int *M=new int*n; for(int i=0;i<n;i+) Mi=new int2; for(i=0;i<n;i+) for(int j=0;j<2;j+) cout<<"M"<<i<<""<<j<<":" cin>>Mij;Flowshop G(n);G.M=M; G.n=n; int f=G.BBFlow(); cout<<" 最佳调度方案 :" for(