flowshop.h

算法设计中的分支限界法中的批处理作业调度问题的实现

#include "minheap.h"
#include "iostream.h"
#include "make2db.h"
class Flowshop;
class MinHeapNode
{
	friend Flowshop;
public:
	operator int () const
	{
		return bb;
	}
private:
	void Init(int);
	void NewNode(MinHeapNode,int,int,int,int);
	int s,f1,f2,sf2,bb,*x;
};

void MinHeapNode::Init(int n)
{
	x=new int[n];
	for(int i=0;i<n;i++)
		x[i]=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 int[n];
	for(int i=0;i<n;i++)
		x[i]=E.x[i];
	f1=Ef1;
	f2=Ef2;
	sf2=E.sf2+f2;
	bb=Ebb;
	s=E.s+1;
}


class Flowshop
{
	friend void main();
public:
	int BBFlow();
	void Swap(int &,int &);
	Flowshop(int**,int);
	~Flowshop();
private:
	int Bound(MinHeapNode,int &,int&,bool **);
	void print();
	void Sort();
	int n,**M,**b,**a,*bestx,bestc;
	bool **y;
};

Flowshop::Flowshop(int **M1,int n1)
{
	n=n1;
	Make2DArray(M,n,n);
	M=M1;
	bestx=new int[n];
	Make2DArray(a,n,n);
	Make2DArray(b,n,n);
	Make2DArray(y,n,2);
	bestc=100;
}

Flowshop::~Flowshop()
{
	remove2DArray(a,n);
	remove2DArray(b,n);
	remove2DArray(y,n);
	delete []bestx;
}

void Flowshop::Swap(int &a,int &b)
{
	int temp=a;
	a=b;
	b=temp;
}

void Flowshop::Sort()
{
	int *c=new int[n];
	for(int j=0;j<2;j++)
	{
		for(int i=0;i<n;i++)
		{
			b[i][j]=M[i][j];
			c[i]=i;
		}
		for(int j=0;j<n-1;j++)
			for(int k=n-1;k>j;k--)
				if(b[k][j]<b[k-1][j])
				{
					Swap(b[k][j],b[k-1][j]);
					Swap(c[k],c[k-1]);
				}
		for(int h=0;h<n;h++)
			a[c[h]][j]=h;
	}
	delete []c;
}

int Flowshop::Bound(MinHeapNode E,int &f1,int &f2,bool **y)
{
	for(int k=0;k<n;k++)
		for(int j=0;j<2;j++)
			y[k][j]=false;
	for(int h=0;h<=E.s;h++)
		for(int j=0;j<2;j++)
			y[a[E.x[h]][j]][j]=true;
	f1=E.f1+M[E.x[E.s]][0];
	f2=((f1>E.f2)?f1:E.f2)+M[E.x[E.s]][1];
	int sf2=E.sf2+f2;
	int s1=0,s2=0,k1=n-E.s,k2=n-E.s,f3=f2;
	for(int j=0;j<n;j++)
		if(!y[j][0])
		{
			k1--;
			if(k1==n-E.s-1)
				f3=(f2>f1+b[j][0])?f2:f1+b[j][0];
			s1+=f1+k1*b[j][0];
		}
	for(int g=0;g<n;g++)
		if(!y[g][1])
		{
			k2--;
			s1+=b[g][1];
			s2+=f3+k2*b[g][1];
		}
		return sf2+((s1>s2)?s1:s2);
}

int Flowshop::BBFlow()
{
	Sort();
	MinHeap<MinHeapNode> H(1000);
	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++)
					bestx[i]=E.x[i];
			}
			delete []E.x;
		}
		else
		{
			for(int i=E.s;i<n;i++)
			{
				Swap(E.x[E.s],E.x[i]);
				int f1,f2;
				int bb=Bound(E,f1,f2,y);
				if(bb<bestc)
				{
					MinHeapNode N;
					N.NewNode(E,f1,f2,bb,n);
					H.Insert(N);
				}
				Swap(E.x[E.s],E.x[i]);
			}
			delete []E.x;
		}
		try
		{
			H.DeleteMin(E);
		}
		catch(OutOfBounds)
		{
			break;
		}
	}
	return bestc;
}

void Flowshop::print()
{
	for(int i=0;i<n;i++)
		cout<<bestx[i]<<ends;
	cout<<endl;
	cout<<bestc;
}