1、“批处理作业调度”上机报告1问题描述给定 n 个作业的集合 JJ1,J2,Jn，每一个作业 Ji 都有两项任务要分别在两台机器上完成，每一个作业必须先由机器 1 处理，然后再由机器 2 处理，作业 Ji 需要机器 j 的处理时间为 tij，i1,2,n;j=1,2。对于一个确定的作业调度，设 Fji 是作业 i 在机器 j 上完成处理的时间，则所有作业在机器 2 上完成处理的时间和 f F2i 称为该作业调度的完成时间和，批处理作业调度问题要求对于给定的 n 个作业，制定最佳作业调度方案，使其完成时间和达到最小。2算法描述与设计用优先队列式分支限界法解决此问题。由于要从 n 个作业的所有排列中
2、找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间树是一棵排列树，对于批处理作业调度问题，可以证明存在最佳作业调度使得在机器 1 和机器 2 上作业以相同次序完成。在作业调度问题相应的排列空间树中，每一个结点 e 都对应于一个已安排的作业集 M1,2,n。以该结点为根的子树中所含叶结点的完成时间和可表示为 fF 2i F 2i iM iM设|M|r ，且 L 是以结点 e 为根的子树中的一个叶结点，相应的作业调度为pk , k=1,2,n，其中 pk 是第 k 个安排的作业。如果从结点 E 开始到叶结点 L的路上，每一个作业 pk 在机器 1 上完成处理后都能立即在机器 2 上开始
3、处理，即从 pr1 开始机器 1 没有空闲时间，则对于该叶结点 L 有：F 2i F 1pr +(n-k+1) t1pr + t2pr=S1 ( i M)如果不能做到上面这一点，则 S1 只会增加，从而有F 2i S1 ( i M)类似地，如果从结点 E 开始到结点 L 的路上，从作业 pr1 开始，机器 2 没有空闲时间，则：F 2i max(F 1pr , F2pr +min( t1i )+ (n-k+1)t2pr)=S2 ( i M)同理可知，S2 是F 2i 的一个下界。由此，得到在结点 E 出相应子树中叶结点完成时间和的下界是fF 2i maxS1,S2其中，S1 和 S2 的计算依
4、赖于叶结点 L 相应的作业调度 pk , k=1,2,n。注意到如果选择 pk，使 t1pr 在 kr1 时依非减序排序，则 S1 取得极小值 S1，同理如果选择 pk，使 t2pr 在 kr1 时依非减序排序，则 S2 取得极小值 S2，因此 S1S1， S2S2 ，且 S1和 S2与叶结点的调度无关。从而有fF 2i maxS1,S2这可以作为优先队列式分支限界法中的限界函数算法中用一个最小堆来表示活结点优先队列。最小堆元素类型是 HeapNode。每一个 HeapNode 类型的结点包含域 x，用来表示结点所相应的作业调度，s 表示该结点已安排的作业是 x1:s，f1 表示当前已安排的作
5、业在机器 1 上的最后完成时间；f2 表示当前已安排的作业在机器 2 上的最后完成时间，sf2 表示当前已安排的作业在机器 2 上的完成时间和，bb 表示当前完成时间和的下界。在具体实现时，用二维数组 m 表示所给的 n 个作业在机器 1 和机器 2 所需的处理时间，在类 Flowshop 中用一个二维数组 b 存储排好序的作业处理时间，数组 a 表示数组 M 和 b 的相应关系，bestc 记录当前最小完成时间和， bestx 记录相应的当前最优解，函数 Sort 实现对各作业在机器 1 和机器 2 上所需时间排序，函数 Bound 用于计算完成时间和下界。函数 BBFlow 是解批处理作业
6、调度问题的优先队列式分支限界法的主体。算法开始时，将排列树的根结点置为当前扩展结点。在初始扩展结点处还没有选定的作业，故 s0，数组 x 初始化为单位排列。算法的 while 循环完成对排列树内部结点的有序扩展，在 while 循环体内算法依次从活结点优先队列中取出具有最小 bb 值的结点作为当前扩展结点，并加以扩展。算法将当前扩展结点 E 分为两种情形处理，首先考虑 E.s=n 的情形，此时已排定 n 个作业，故当前扩展结点 E 是排列树的一个叶结点。 E.x 表示相应于该叶结点的作业调度。E.sf2 是相应于该叶结点的完成时间和。当 E.sf2class flowshoppublic:fl
7、owshop(int *,int);flowshop();void backtrack(int i);void print();private:void swap(int int n,f1,f,bestf,*M,*X,*bestX,*f2;flowshop:flowshop(int *M1,int n1)n=n1;M=M1;X=new intn+1;bestX=new intn+1;f2=new intn+1;bestf=100;for(int i=0;in)if(ff1)?f2i-1:f1)+MXj2;f+=f2i;if(f#include #include “string.h“#include “make2db.h“#include “Flowshop.h“void main()int n,*M;ifstream fin(“data.txt“);finn;Make2DArray(M,n+1,3);for(int i=1;iMij;flowshop F1(M,n);F1.backtrack(1);F1.print();remove2DArray(M,n+1);结果如下：最低作业调度是：132最低值是：18
