批处理作业调度问题.cpp

回溯法实现多个经典算法

// 批处理作业调度问题

#include <iostream.h>
int Int_Max=10000;  // ∞
const int n=3;  // 作业个数

class Flowshop
{
	friend Flow(int M[n][2], int []);
private:
	void Backtrack(int i);
	int m[n][2],	// 各作业所需处理时间
		*x,		// 当前作业调度
        *bestx,	// 当前最优作业调度
		*f2,	// 机器2完成处理时间
		f1,		// 机器1完成处理时间
		f,		// 完成时间和
		bestf;	// 当前最优值
};

void Flowshop::Backtrack(int i)
{
	void Swap(int &a, int &b);
	if (i+1>n)
	{
		bestf=f;
		for (int j=0; j<n; j++) bestx[j]=x[j];
		return;
	}

	for (int j=i; j<n; j++)
	{
		f1+=m[x[j]][0];
		f2[i+1]=((f2[i]>f1) ? f2[i] : f1)+m[x[j]][1];
		f+=f2[i+1];
		if (f<bestf)
		{
			Swap(x[i], x[j]);
			Backtrack(i+1);
			Swap(x[i], x[j]);
		}
		f1-=m[x[j]][0];
		f-=f2[i+1];
	}
}

int Flow(int M[n][2], int bestx[])
{
	Flowshop X;
	X.x=new int [n];
	X.f2=new int [n];
	X.bestx=bestx;
	X.bestf=Int_Max;
	X.f1=0;
	X.f=0;
	for (int i=0; i<n; i++)
	{
		X.m[i][0]=M[i][0];
		X.m[i][1]=M[i][1];
		X.x[i]=bestx[i];
		X.f2[i]=0;
	}

	X.Backtrack(0);
	delete [] X.x, X.f2;
	return X.bestf;
}

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

void main()
{
	int t[n][2]={{2,1},{3,1},{2,3}}, x[n]={0,1,2};
	cout<<"\nx: t1,t2\n--------\n";
	for (int i=0; i<n; i++) cout<<x[i]+1<<": "<<t[i][0]<<", "<<t[i][1]<<endl;

	cout<<"\n\n BestF = "<<Flow(t, x);
	cout<<"\n\n BestX = "<<x[0]+1;
	for (i=1; i<n; i++) cout<<", "<<x[i]+1;
	cout<<"\n\n";
}