fac3_8.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 90 页，例
//流水作业调度问题动态规划解法
public class Fac3_8{
 static class Elememt 
   {
    int key;
    int index;
    boolean job;
    private Elememt(int kk,int ii,boolean jj)
      {
       key=kk;
       index=ii;  //作业编号
       job=jj;    //子集N1标记为true 
      }
   }
 
   public static int flowShop(int []a,int []b,int []c)
   {
     int n=a.length; 
     Elememt []d=new Elememt[n];
     for(int i=0;i<n;i++){
       int key=a[i]>=b[i]? b[i]:a[i]; //按johnson 法则分别取对应的b[i]或 a[i]值作为关键字 
       boolean job=a[i]<b[i];        //给符合条件a[i]<b[i]的放入N1子集大标记true
       d[i]=new Elememt(key,i,job);
      System.out.println("d["+i+"] "+key+"  "+i+"  "+job);
       }
     mergeSort(d);    // 对数组d 按关键字升序进行排序
     System.out.println("*****键值****作业号******");
     for(int i=0;i<n;i++)
     System.out.println("d["+i+"] "+d[i].key+"  "+d[i].index+"  "+d[i].job);
     int j=0,k=n-1;
     for(int i=0;i<n;i++){
       if(d[i].job)c[j++]=d[i].index;  //将排过序的数组d，取其中作业序号
       else c[k--]=d[i].index;         //属于N1的从前面进入，属于N2的从后面进入
       }                               //从而实现了N1的非减排序，N2 的非增排序
     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 mergeSort(Elememt[] e)
   {
     int k=e.length-1;  
     Elememt a;
     for(int i=0;i<k;i++)
      for(int j=i+1;j<=k;j++)
       if(e[i].key>e[j].key){
        a=e[i];
        e[i]=e[j];
        e[j]=a;
       }      
   }  

  public static void main(String args[])
  {
    int []x={2,4,3,6,1};
    int []y={5,2,3,1,7};
    int n=x.length;
    int []z=new int[n];
    System.out.println("完成作业所需最短时间 "+flowShop(x,y,z));
    System.out.println("作业编号自0开始，作业执行顺序为 ");
    for(int j=0;j<n;j++)   
    System.out.print(" "+z[j]);
    System.out.println();
  }
}