flowshop.java

来自「java实现批处理作业调度算法 开发环境为Eclipse」· Java 代码 · 共 66 行

public class FlowShop
{
	static int n;          //作业数
	static int f1;         //机器1完成处理时间
	static int f;          //完成时间和
	static int bestf;      //当前最优值
	static int[][]m;       //各作业所需的处理时间
	static int[]x;         //当前作业调度
	static int[]bestx;     //当前最优作业调度
	static int[]f2;        //机器2完成处理时间
	public static void main(String[] args)
	{
		n=3;
		bestf=19;
		m=new int[n+1][3];
		m[1][1]=5;
		m[1][2]=4;
		m[2][1]=3;
		m[2][2]=4;
		m[3][1]=2;
		m[3][2]=6;
		x=new int[n+1];
		for(int i=0;i<=n;i++)
			x[i]=i;
		bestx=new int[n+1];
		f2=new int[n+1];
		backtrack(1);
		System.out.println("批处理作业完成的最短时间和为："+bestf);
		System.out.println("批处理最短时间的作业调度为：");
		for(int i=1;i<=n;i++)
			System.out.print(bestx[i]+" ");
		System.out.println();
	}
	////////////////////////////////////
	public static void backtrack(int i)
	{
		if(i>n)
		{
			for(int j=1;j<=n;j++)
				bestx[j]=x[j];
			bestf=f;
		}
		else
			for(int j=i;j<=n;j++)
			{
				f1+=m[x[j]][1];
				f2[i]=((f2[i-1]>f1) ? f2[i-1]:f1)+m[x[j]][2];
				f+=f2[i];
				if(f<bestf)
				{
					swap(x,i,j);
					backtrack(i+1);
					swap(x,i,j);
				}
				f1-=m[x[j]][1];
				f-=f2[i];
			}
	}
	////////////////////////////////
	public static void swap(int []x,int i,int j)
	{
		int temp=x[i];
		x[i]=x[j];
		x[j]=temp;
	}
}