backward assembly_line scheduling(安博).h

使用动态规划方法解决多个生产线上的调度问题

const int N=6;

int a1[N],a2[N];
int f1[N],f2[N];
int t1[N-1],t2[N-1];
int l1[N-1],l2[N-1];
int e1,e2;
int x1,x2;
int f,l;

void InitInputValues()
{
	cout<<"There are "<<N<<" stations in each of the two assembly lines."<<endl;
	cout<<"For each of the two lines, please input assembly time at each station"<<endl;
	cout<<"          (from left to right; first line1, then line2)"<<endl;
	for(int i=0;i<N;i++)
		cin>>a1[i];
	for(i=0;i<N;i++)
		cin>>a2[i];

	cout<<"Please input the value of t1,1--t1,n-1 first, and that of t2,1--t2,n-1"<<endl;
	for(i=0;i<N-1;i++)
		cin>>t1[i];
	for(i=0;i<N-1;i++)
		cin>>t2[i];

	cout<<"Please input the value of e1,e2"<<endl;
	cin>>e1>>e2;
	cout<<"Please input the value of x1,x2"<<endl;
	cin>>x1>>x2;
}

void Backward_FastestWay()
{
	f1[N-1]=a1[N-1]+x1;
	f2[N-1]=a2[N-1]+x2;

	for(int j=N-1;j>=1;j--)
	{
		if((a1[j-1]+f1[j])<=(a1[j-1]+t1[j-1]+f2[j]))
		{
			f1[j-1]=a1[j-1]+f1[j];
			l1[j-1]=1;
		}
		else
		{
			f1[j-1]=a1[j-1]+t1[j-1]+f2[j];
			l1[j-1]=2;
		}
		if((a2[j-1]+f2[j])<=(a2[j-1]+t2[j-1]+f1[j]))
		{
			f2[j-1]=a2[j-1]+f2[j];
			l2[j-1]=2;
		}
		else
		{
			f2[j-1]=a2[j-1]+t2[j-1]+f1[j];
			l2[j-1]=1;
		}
	}
	if((f1[0]+e1)<=(f2[0]+e2))
	{
		f=f1[0]+e1;
		l=1;
	}
	else
	{
		f=f2[0]+e2;
		l=2;
	}
}

void Display()
{
	cout<<"******************output******************"<<endl;
	cout<<"\t";
	for(int i=0;i<N;i++)
		cout<<f1[i]<<"  ";
	cout<<endl;
	cout<<"f*="<<f<<endl;
	cout<<"\t";
	for(i=0;i<N;i++)
		cout<<f2[i]<<"  ";

	cout<<endl;
	cout<<"\t";
	for(i=0;i<N-1;i++)
		cout<<l1[i]<<"  ";
	cout<<endl;
	cout<<"l*="<<l<<endl;
	cout<<"\t";
	for(i=0;i<N-1;i++)
		cout<<l2[i]<<"  ";

	int ll[2][N-1];
	for(i=0;i<N-1;i++)
		ll[0][i]=l1[i];
	for(i=0;i<N-1;i++)
		ll[1][i]=l2[i];

	i=l;
	cout<<endl;
	cout<<"line "<<i<<','<<" station "<<1<<endl;
	for(int j=2;j<=N;j++)
	{
		i=ll[i-1][j-2];
		cout<<"line "<<i<<','<<" station "<<j<<endl;
	}
}