flowshop.java

《算法设计与分析》王晓东编著

public class FlowShop {

	public static int flowShop(int []a,int []b,int []c)
	{
		int n=a.length;
		Element []d=new Element[n];
		
		for (int i=0;i<n;i++) {
			int key=a[i]>b[i]?b[i]:a[i];
			boolean job=a[i]<=b[i];
			d[i]=new Element(key,i,job);
		}
		MergeSort.mergeSort(d);		
		int j=0,k=n-1;
		for (int i=0;i<n;i++) {
			if (d[i].job) c[j++]=d[i].index;
			else c[k--]=d[i].index;
		}				
		j=a[c[0]];
		k=j+b[c[0]];
		for (int i=1;i<n;i++) {
			j+=a[c[i]];
			k=j<k?k+b[c[i]]:j+b[c[i]];
		}
		return k;		
	}
	
	public static void main(String[] args) {
		int n=8;
		/* 初始化a数组和b数组,
		 * ai表示M1加工作业i所需时间，bi表示M2加工作业i所需时间 */
		int a[]=new int[]{5,10,8,40,1,6,25,13};
		int b[]=new int[]{7,1,10,20,10,4,9,8};
		
		/* c数组记录最优调度序列 */
		int c[]=new int[n];
		
		/* 计算并输出最少时间 */
		System.out.println(flowShop(a,b,c));
	}

}