第5章回溯法.ppt

* 这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。显而易见，最佳调度方案是1,3,2，其完成时间和为18。 tji 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 例如，考虑如下n=3 的实例： * tji 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 public class FlowShop static int n, // 作业数 f1, // 机器1完成处理时间 f, // 完成时间和 bestf; // 当前最优值 static int [][] m; // 各作业所需的处理时间 static int [] x; // 当前作业调度 static int [] bestx; // 当前最优作业调度 static int [] f2; // 机器2完成处理时间 tji 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 * 算法设计 批处理作业调度问题要从n个作业的所有排列中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。按照回溯法有哪些信誉好的足球投注网站排列树的算法框架，设开始时x=[1,2,…,n]是所给的n个作业，则相应的排列树由x[1:n]的所有排列构成。 类Flowshop的数据成员记录解空间树中结点信息，以减少传给backtrack的参数。二维数组m是输入的作业处理时间，m[i][1]代表i作业在1机器上的加工时间， m[i][2]代表i作业在2机器上的加工时间。bestf 记录当前最小完成时间和，bestx 是相应的当前最佳作业调度。 * 在递归方法backtrack中，当in 时，算法有哪些信誉好的足球投注网站至叶结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳作业调度。 当in时，当前扩展结点位于排列树的第i-1层。此时算法选择下一个要安排的作业，以深度优先的方式递归地对相应子树进行有哪些信誉好的足球投注网站。对于不满足上界约束的结点，则剪去相应的子树。 * 批处理作业调度 解空间：排列树 private 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) { MyMath.swap(x,i,j); backtrack(i+1); MyMath.swap(x,i,j); } f1-=m[x[j]][1]; f-=f2[i]; } } public class FlowShop static int n, // 作业数 f1, // 机器1完成处理时间 f, // 完成时间和 bestf; // 当前最优值 static int [][] m; // 各作业所需的处理时间 static int [] x; // 当前作业调度 static int [] bestx; // 当前最优作业调度 static int [] f2; // 机器2完成处理时间 * 该问题关键是求作业在机器2上的完成处理时间，从28页的图可以看出，由于作业调度的顺序不同，每个作业在机器1上的开始时间不同，但由于机器1从一开工就对各个作业连续处理，因此作业i的机器的加工开始时间，就是它前面被加工作业的机器1上的处理时间之和。机器2对各个作业的加工，由于调度的差异会造成不连续，产生等待时间，也就是说，前一个作业的机器2的加工时间，大于后一个作业的机器1的加工时间时，后一个作业必须等