public static int /* * 批处理作业调度--采用回溯法解决--回溯法中的排列集 * Time：2012-12-30 * 下标从1开始 */ package com.book.java; public class Project37_FlowShop { // public static int time[][]={{0,0,0},{0,2,1},{0,3,1},{0,2,3}}; time[][]={{0,0,0},{0,30,80},{0,120,100},{0,50,90},{0,20,60},{0,90,30},{ 0,110,10}}; //用来表示每一个任务分别在机器1和2上完成需要的时间，下标从1开始，time[1][2]表示 public static Job job[]=null;//将任务时间分别存储在各个任务中 public static int n;//用来表示有多少个任务 public static int bestt;//用来表示最佳时间 public static int currentt;//用来表示当前所需要的时间 public static int f[];//记录各个job的延迟时 public static int bestx[];//用来存放最佳的调度的方式 public static void main(String[] args) { // public static int delayt;//用来表示在完成相应任务的时候，所延迟的时间 第一个任务在机器2上完成需要的时间 job[i]=new Job(i,time[i][1],time[i][2]); n=time.length-1;//初始化个数 f=new int[n+1];//初始化各个job的延迟 bestx=new int[n+1];//初始化最佳的调度方式的数组 job=new Job[n+1];//初始化各个任务 for(int i=1;i<=n;i++) { } bestt=Integer.MAX_VALUE;//初始化最佳时间 currentt=0;//出事化当前时间 flowshop(1);//回溯法解决 //输出结果 System.out.println("最佳的时间为:"+bestt); System.out.println("任务调度的方式:"); for(int i=1;i<=n;i++) { } System.out.print(bestx[i]+"\t"); } public static void flowshop(int i) { if(i>n)//当超过任务的个数的时候，计算最佳的使用时间，并记录最佳的调度方案 { int temp=currentt+f[3]; if(temp

{ bestt=temp; for(int k=1;k<=n;k++) { bestx[k]=job[k].ID; } System.out.println(job[k]); } System.out.println("-----------------------"); for(int k=1;k<=n;k++) { } System.out.println("currenttime="+currentt); for(int k=1;k<=n;k++) { } System.out.println("-----------------------"); System.out.println("当前的时间为curt"); return ; System.out.println("f["+k+"],:"+f[k]); // // // // // // // // // // // // } for(int k=i;k<=n;k++) { swap(k,i);//形成相应的排列组合 if(i==1)//当为第一层的时候，初始化相应的变量 { currentt=job[i].time1; f[i]=job[i].time2; }else { int temp=0; f[i]=job[i].time2; int temp=f[i-1]-job[i].time1; f[i]=job[i].time2+temp; }else { } currentt=currentt+job[i].time1; if(job[i].time1>=f[i-1])//当不在第一层的时候，看算法设计和分析（第 二版）P88-89的解析 { } flowshop(i+1); currentt=currentt-job[i].time1; swap(k,i); } } public static void swap(int k,int i)//交换数组中的对应位置的变量 { Job temp=job[k]; job[k]=job[i]; job[i]=temp; } 

} class Job//用于存储对应的任务ID，机器1工作的时间，机器2工作的时间 { return "ID:"+ID+",time1:"+time1+",time:"+time2; int ID; int time1; int time2; public Job(int ID,int time1,int time2) { this.ID=ID; this.time1=time1; this.time2=time2; return ID; ID = iD; } public String toString() { } public int getID() { } public void setID(int iD) { } public int getTime1() { } public void setTime1(int time1) { this.time1 = time1; } public int getTime2() { } public void setTime2(int time2) { } this.time2 = time2; return time1; return time2; }