第9章-分支限界法完课件.ppt

《第9章-分支限界法完课件.ppt》由会员分享，可在线阅读，更多相关《第9章-分支限界法完课件.ppt（58页珍藏版）》请在三一办公上搜索。

1、2023/4/3,第9章 分支限界法,Page 1,9.1 概 述,9.2 图问题中的分支限界法,9.3 组合问题中的分支限界法,9.4 实验项目电路布线问题,第9章 分支限界法,2023/4/3,第9章 分支限界法,Page 2,9.1.1 解空间树的动态搜索（2）,9.1.2 分支限界法的设计思想,9.1.3 分支限界法的时间性能,9.1 概 述,2023/4/3,第9章 分支限界法,Page 3,分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down,up。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目

2、标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点表（以下简称表PT）中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。,9.1.1 解空间树的动态搜索（2）,2023/4/3,第9章 分支限界法,Page 4,随着这个遍历过程的不断深入，表PT中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时，如果该结点的目标函数值是表PT中的极值（对于最小化问题，是极小值；对于最大化问题，是极大值），则该叶子结点对应的解就是问题的最优

3、解；否则，根据这个叶子结点调整目标函数的界（对于最小化问题，调整上界；对于最大化问题，调整下界），依次考察表PT中的结点，将超出目标函数界的结点丢弃，然后从表PT中选取使目标函数取得极值的结点继续进行扩展。,2023/4/3,第9章 分支限界法,Page 5,例：0/1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：,2023/4/3,第9章 分支限界法,Page 6,应用贪心法求得近似解为(1,0,0,0)，获得的价值为40，这可以作为0/1背包问题的下界。如何求得0/1背

4、包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界40,100。,2023/4/3,第9章 分支限界法,Page 7,假设背包中已装入物品的重量是w，获得的价值是v，计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值v，加上背包剩余容量W-w与剩下物品的最大单位重量价值的积，于是，得到限界函数为：,2023/4/3,第9章 分支限界法,Page 8,分支限界法求解0/1背包问题,2023/4/3,第9章 分支限界法,Page 9,分

5、支限界法求解0/1背包问题，其搜索空间如图9.1所示，具体的搜索过程如下：（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为1010=100；（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40+(10-4)6=76，将结点2加入待处理结点表PT中；在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10660，将结点3加入表PT中；（3）在表PT中选取目标函数值取得极大的结点2优先进行搜索；,2023/4/3,第9章 分支限界法,Page 10,（4）在结点4，将

6、物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40+(10-4)5=70，将结点5加入表PT中；（5）在表PT中选取目标函数值取得极大的结点5优先进行搜索；（6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65+(10-9)4=69，将结点6加入表PT中；在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40+(10-4)464，将结点6加入表PT中；,2023/4/3,第9章 分支限界法,Page 11,（7）在

7、表PT中选取目标函数值取得极大的结点6优先进行搜索；（8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为65；（9）由于结点9是叶子结点，同时结点9的目标函数值是表PT中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。,2023/4/3,第9章 分支限界法,Page 12,假设求解最大化问题，解向量为X=(x1,x2,xn)，其中，xi的取值范围为某个有穷集合Si，|Si|=ri（1in）。在使用分支限界法搜索问题的解空间树时，首先根据限界函数估算目标函数的界do

8、wn,up，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。对这r1个孩子结点分别估算可能取得的目标函数值bound(x1)，其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于bound(x1)，也就是部分解应满足：bound(x1)bound(x1,x2)bound(x1,x2,xk)bound(x1,x2,xn),9.1.2 分支限界法的设计思想,2023/4/3,第9章 分支限界法,Page 13,若某孩子结点的目标函数值超出目标函数的界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。从表PT中选取使目标函数取得极大值的结点

9、作为下一次扩展的根结点，重复上述过程，当到达一个叶子结点时，就得到了一个可行解X=(x1,x2,xn)及其目标函数值bound(x1,x2,xn)。,2023/4/3,第9章 分支限界法,Page 14,如果bound(x1,x2,xn)是表PT中目标函数值最大的结点，则bound(x1,x2,xn)就是所求问题的最大值，(x1,x2,xn)就是问题的最优解；如果bound(x1,x2,xn)不是表PT中目标函数值最大的结点，说明还存在某个部分解对应的结点，其上界大于bound(x1,x2,xn)。于是，用bound(x1,x2,xn)调整目标函数的下界，即令down=bound(x1,x2,

10、xn)，并将表PT中超出目标函数下界down的结点删除，然后选取目标函数值取得极大值的结点作为下一次扩展的根结点，继续搜索，直到某个叶子结点的目标函数值在表PT中最大。,2023/4/3,第9章 分支限界法,Page 15,分支限界法求解最大化问题的一般过程,分支限界法的一般过程1根据限界函数确定目标函数的界down,up；2将待处理结点表PT初始化为空；3对根结点的每个孩子结点x执行下列操作 3.1 估算结点x的目标函数值value;3.2 若(value=down)，则将结点x加入表PT中；4循环直到某个叶子结点的目标函数值在表PT中最大 4.1 i=表PT中值最大的结点；4.2 对结点i

11、的每个孩子结点x执行下列操作 4.2.1 估算结点x的目标函数值value;4.2.2 若(value=down)，则将结点x加入表PT中；4.2.3 若(结点x是叶子结点且结点x的value值在表PT中最大)，则将结点x对应的解输出，算法结束；4.2.4 若(结点x是叶子结点但结点x的value值在表PT中不是最大)，则令down=value，并且将表PT中所有小于value的结点删除；,2023/4/3,第9章 分支限界法,Page 16,应用分支限界法的关键问题（1）如何确定合适的限界函数（2）如何组织待处理结点表（3）如何确定最优解中的各个分量,2023/4/3,第9章 分支限界法,P

12、age 17,分支限界法对问题的解空间树中结点的处理是跳跃式的，回溯也不是单纯地沿着双亲结点一层一层向上回溯，因此，当搜索到某个叶子结点且该叶子结点的目标函数值在表PT中最大时（假设求解最大化问题），求得了问题的最优值，但是，却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以用如下方法解决：对每个扩展结点保存该结点到根结点的路径；在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。,对于（3）：如何确定最优解中的各个分量：,2023/4/3,第9章 分支限界法,Page 18,方法一：例如图9.1所示0/1背包问题，为了对每个扩展结点

13、保存该结点到根结点的路径，将部分解(x1,xi)和该部分解的目标函数值都存储在待处理结点表PT中，在搜索过程中表PT的状态如图9.2所示。,2023/4/3,第9章 分支限界法,Page 19,方法二：图9.1所示0/1背包问题，为了在搜索过程中构建搜索经过的树结构，设一个表ST，在表PT中取出最小值结点进行扩充时，将最小值结点存储到表ST中，表PT和表ST的数据结构为(物品i-1的选择结果，ub)，在搜索过程中表PT和表ST的状态如图9.3所示。,2023/4/3,第9章 分支限界法,Page 20,分支限界法和回溯法实际上都属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数

14、阶个结点的解空间树，在最坏情况下，时间复杂性肯定为指数阶。与回溯法不同的是，分支限界法首先扩展解空间树中的上层结点，并采用限界函数，有利于实行大范围剪枝，同时，根据限界函数不断调整搜索方向，选择最有可能取得最优解的子树优先进行搜索。所以，如果选择了结点的合理扩展顺序以及设计了一个好的限界函数，分支界限法可以快速得到问题的解。,9.1.3 分支限界法的时间性能,2023/4/3,第9章 分支限界法,Page 21,分支限界法的较高效率是以付出一定代价为基础的，其工作方式也造成了算法设计的复杂性。首先，一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值，而且对于具体的问题实例，通常需要进

15、行大量实验，才能确定一个好的限界函数；其次，由于分支限界法对解空间树中结点的处理是跳跃式的，因此，在搜索到某个叶子结点得到最优值时，为了从该叶子结点求出对应的最优解中的各个分量，需要对每个扩展结点保存该结点到根结点的路径，或者在搜索过程中构建搜索经过的树结构，这使得算法的设计较为复杂；再次，算法要维护一个待处理结点表PT，并且需要在表PT中快速查找取得极值的结点，等等。这都需要较大的存储空间，在最坏情况下，分支限界法需要的空间复杂性是指数阶。,2023/4/3,第9章 分支限界法,Page 22,9.2.1 TSP问题,9.2.2 多段图的最短路径问题,9.2 图问题中的分支限界法,2023/

16、4/3,第9章 分支限界法,Page 23,TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。,9.2.1 TSP问题,2023/4/3,第9章 分支限界法,Page 24,采用贪心法求得近似解为135421，其路径长度为1+2+3+7+3=16，这可以作为TSP问题的上界。把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为1+3+1+3+2=10，但是还有一个信息量更大的下界：考虑一个TSP问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元

17、素相加再除以2，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 于是，得到了目标函数的界14,16。需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。,2023/4/3,第9章 分支限界法,Page 25,部分解的目标函数值的计算方法 例如图9.4所示无向图，如果部分解包含边(1,4)，则该部分解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。,2023/4/3,第9章 分支限界法,Page 26,分支限界法求解T

18、SP问题示例,2023/4/3,第9章 分支限界法,Page 27,应用分支限界法求解图9.4所示无向图的TSP问题，其搜索空间如图9.5所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（1）在根结点1，根据限界函数计算目标函数的值为lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14；（2）在结点2，从城市1到城市2，路径长度为3，目标函数的值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，将结点2加入待处理结点表PT中；在结点3，从城市1到城市3，路径长度为1，目标函数的值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/

19、2=14，将结点3加入表PT中；在结点4，从城市1到城市4，路径长度为5，目标函数的值为(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16，将结点4加入表PT中；在结点5，从城市1到城市5，路径长度为8，目标函数的值为(1+8)+(3+6)+(1+2)+(3+5)+(2+8)/2=19，超出目标函数的界，将结点5丢弃；,2023/4/3,第9章 分支限界法,Page 28,（3）在表PT中选取目标函数值极小的结点2优先进行搜索；（4）在结点6，从城市2到城市3，目标函数值为(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16，将结点6加入表PT中；在结点7，从

20、城市2到城市4，目标函数值为(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16，将结点7加入表PT中；在结点8，从城市2到城市5，目标函数值为(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19，超出目标函数的界，将结点8丢弃；（5）在表PT中选取目标函数值极小的结点3优先进行搜索；（6）在结点9，从城市3到城市2，目标函数值为(1+3)+(3+6)+(1+6)+(3+4)+(2+3)/2=16，将结点9加入表PT中；在结点10，从城市3到城市4，目标函数值为(1+3)+(3+6)+(1+4)+(3+4)+(2+3)/2=15，将结点10加入表PT中；在结点1

21、1，从城市3到城市5，目标函数值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，将结点11加入表PT中；,2023/4/3,第9章 分支限界法,Page 29,（7）在表PT中选取目标函数值极小的结点11优先进行搜索；（8）在结点12，从城市5到城市2，目标函数值为(1+3)+(3+9)+(1+2)+(3+4)+(2+9)/2=19，超出目标函数的界，将结点12丢弃；在结点13，从城市5到城市4，目标函数值为(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14，将结点13加入表PT中；（9）在表PT中选取目标函数值极小的结点13优先进行搜索；（10）在结

22、点14，从城市4到城市2，目标函数值为(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16，最后从城市2回到城市1，目标函数值为(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2=16，由于结点14为叶子结点，得到一个可行解，其路径长度为16；,2023/4/3,第9章 分支限界法,Page 30,（11）在表PT中选取目标函数值极小的结点10优先进行搜索；（12）在结点15，从城市4到城市2，目标函数的值为(1+3)+(3+7)+(1+4)+(7+4)+(2+3)/2=18，超出目标函数的界，将结点15丢弃；在结点16，从城市4到城市5，目标函数值为(1+3)+(

23、3+6)+(1+4)+(3+4)+(2+3)/2=15，将结点16加入表PT中；（13）在表PT中选取目标函数值极小的结点16优先进行搜索；（14）在结点17，从城市5到城市2，目标函数的值为(1+3)+(3+9)+(1+4)+(3+4)+(9+3)/2=20，超出目标函数的界，将结点17丢弃；（15）表PT中目标函数值均为16，且有一个是叶子结点14，所以，结点14对应的解135421即是TSP问题的最优解，搜索过程结束。,2023/4/3,第9章 分支限界法,Page 31,2023/4/3,第9章 分支限界法,Page 32,2023/4/3,第9章 分支限界法,Page 33,设图G=

24、(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2kn,1ik），使得E中的任何一条边(u,v)，必有uVi，vVi+m（1ik,1i+mk），则称图G为多段图，称sV1为源点，tVk为终点。,多段图的最短路径问题是求从源点到终点的最小代价路径。,9.2.2 多段图的最短路径问题,2023/4/3,第9章 分支限界法,Page 34,对图9.7所示多段图应用贪心法求得近似解为02589，其路径代价为2+7+6+3=18，这可以作为多段图最短路径问题的上界。把每一段最小的代价相加，可以得到一个非常简单的下界，其路径长度为2+4+5+3=14。于是，得到了目标函数的界

25、14,18。由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，一旦某条路径的一些段被确定后，就可以并入这些信息并计算部分解的目标函数值的下界。一般情况下，对于一个正在生成的路径，假设已经确定了i段（1ik），其路径为(r1,r2,ri,ri+1)，此时，该部分解的目标函数值的计算方法即限界函数如下：,2023/4/3,第9章 分支限界法,Page 35,应用分支限界法求解图9.7所示多段图的最短路径问题，其搜索空间如图9.8所示，具体的搜索过程如下（加黑表示该路径上已经确定的边）：（1）在根结点1，根据限界函数计算目标函数的值为14；（2）在结点2，第1段选择边，目标函数值为l

26、b=4+8+5+3=20，超出目标函数的界，将结点2丢弃；在结点3，第1段选择边，目标函数值为lb=2+7+5+3=17，将结点3加入待处理结点表PT中；在结点4，第1段选择边，目标函数值为lb=3+4+5+3=15，将结点4加入表PT中；（3）在表PT中选取目标函数值极小的结点4优先进行搜索；,2023/4/3,第9章 分支限界法,Page 36,（4）在结点5，第2段选择边，目标函数值为lb=3+4+6+3=16，将结点5加入表PT中；在结点6，第2段选择边，目标函数值为lb=3+7+5+3=18，将结点6加入表PT中；（5）在表PT中选取目标函数值极小的结点5优先进行搜索；（6）在结点7

27、，第3段选择边，可直接确定第4段的边，目标函数值为lb=3+4+8+7=22，为一个可行解但超出目标函数的界，将其丢弃；在结点8，第3段选择边，可直接确定第4段的边，目标函数值为lb=3+4+6+3=16，为一个较好的可行解。由于结点8是叶子结点，并且其目标函数值是表PT中最小的，所以，结点8代表的解即是问题的最优解，搜索过程结束。,2023/4/3,第9章 分支限界法,Page 37,2023/4/3,第9章 分支限界法,Page 38,为了在搜索过程中构建搜索经过的树结构，设一个表ST，在表PT中取出最小值结点进行扩充时，将最小值结点存储到表ST中，表PT和表ST的数据结构为(第i段，lb

28、)，在搜索过程中表PT和表ST的状态如下：,回溯过程是：(3,16)(2,16)(1,15)。,PT,2023/4/3,第9章 分支限界法,Page 39,2023/4/3,第9章 分支限界法,Page 40,9.3.1 任务分配问题,9.3.2 批处理作业调度问题,9.3 组合问题中的分支限界法,2023/4/3,第9章 分支限界法,Page 41,任务分配问题要求把n项任务分配给n个人，每个人完成每项任务的成本不同，要求分配总成本最小的最优分配方案。如图9.10所示是一个任务分配的成本矩阵。,9.3.1 任务分配问题,2023/4/3,第9章 分支限界法,Page 42,求最优分配成本的上

29、界和下界考虑任意一个可行解，例如矩阵中的对角线是一个合法的选择，表示将任务1分配给人员a、任务2分配给人员b、任务3分配给人员c、任务4分配给人员d，其成本是9+4+1+4=18；或者应用贪心法求得一个近似解：将任务2分配给人员a、任务3分配给人员b、任务1分配给人员c、任务4分配给人员d，其成本是2+3+5+4=14。显然，14是一个更好的上界。为了获得下界，考虑人员a执行所有任务的最小代价是2，人员b执行所有任务的最小代价是3，人员c执行所有任务的最小代价是1，人员d执行所有任务的最小代价是4。因此，将每一行的最小元素加起来就得到解的下界，其成本是2+3+1+4=10。需要强调的是，这个解

30、并不是一个合法的选择（3和1来自于矩阵的同一列），它仅仅给出了一个参考下界，这样，最优值一定是10,14之间的某个值。,2023/4/3,第9章 分支限界法,Page 43,设当前已对人员1i分配了任务，并且获得了成本v，则限界函数可以定义为：（式9.4）,2023/4/3,第9章 分支限界法,Page 44,（2）在结点2，将任务1分配给人员a，获得的成本为9，目标函数值为9+(3+1+4)=17，超出目标函数的界10,14，将结点2丢弃；在结点3，将任务2分配给人员a，获得的成本为2，目标函数值为2+(3+1+4)=10，将结点3加入待处理结点表PT中；在结点4，将任务3分配给人员a，获得

31、的成本为7，目标函数值为7+(3+1+4)=15，超出目标函数的界10,14，将结点4丢弃；在结点5，将任务4分配给人员a，获得的成本为8，目标函数值为8+(3+1+4)=16，超出目标函数的界10,14，将结点5丢弃；,应用分支限界法求解图9.10所示任务分配问题，对解空间树的搜索如图9.11所示，具体的搜索过程如下：（1）在根结点1，没有分配任务，根据限界函数估算目标函数值为2+3+1+4=10；,2023/4/3,第9章 分支限界法,Page 45,（3）在表PT中选取目标函数值极小的结点3优先进行搜索；（4）在结点6，将任务1分配给人员b，获得的成本为2+6=8，目标函数值为8+(1+

32、4)13，将结点6加入表PT中；在结点7，将任务3分配给人员b，获得的成本为2+3=5，目标函数值为5+(1+4)10，将结点7加入表PT中；在结点8。将任务4分配给人员b，获得的成本为2+7=9，目标函数值为9+(1+4)14，将结点8加入表PT中；（5）在表PT中选取目标函数值极小的结点7优先进行搜索；（6）在结点9，将任务1分配给人员c，获得的成本为5+5=10，目标函数值为10+4=14，将结点9加入表PT中；在结点10，将任务4分配给人员c，获得的成本为5+8=13，目标函数值为13+4=17，超出目标函数的界10,14，将结点10丢弃；,2023/4/3,第9章 分支限界法,Pag

33、e 46,（7）在表PT中选取目标函数值极小的结点6优先进行搜索；（8）在结点11，将任务3分配给人员c，获得的成本为8+1=9，目标函数值为9+4=13，将结点11加入表PT中；在结点12，将任务4分配给人员c，获得的成本为8+8=16，目标函数值为16+4=20，超出目标函数的界10,14，将结点12丢弃；（9）在表PT中选取目标函数值极小的结点11优先进行搜索；（10）在结点13，将任务4分配给人员d，获得的成本为9+4=13，目标函数值为13，由于结点13是叶子结点，同时结点13的目标函数值是表PT中的极小值，所以，结点13对应的解即是问题的最优解，搜索结束。,2023/4/3,第9章

34、 分支限界法,Page 47,图9.11 分支限界法求解任务分配问题示例(表示该结点被丢弃，结点上方的数组表示搜索顺序),2023/4/3,第9章 分支限界法,Page 48,为了在搜索过程中构建搜索经过的树结构，设一个表ST，在表PT中取出最小值结点进行扩充时，将最小值结点存储到表ST中，表PT和表ST的数据结构为(人员i-1分配的任务,lb),回溯过程是：(3,13)(1,13)(2,13)(0,10)。,2023/4/3,第9章 分支限界法,Page 49,2023/4/3,第9章 分支限界法,Page 50,给定n个作业的集合J=J1,J2,Jn，每个作业都有3项任务分别在3台机器上完

35、成，作业Ji需要机器j的处理时间为tij（1in,1j3），每个作业必须先由机器1处理，再由机器2处理，最后由机器3处理。批处理作业调度问题要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器3上处理结束所需的时间最少。显然，批处理作业的一个最优调度应使机器1没有空闲时间，且机器2和机器3的空闲时间最小。可以证明，存在一个最优作业调度使得在机器1、机器2和机器3上作业以相同次序完成。,9.3.2 批处理作业调度问题,2023/4/3,第9章 分支限界法,Page 51,若处理顺序为(J2,J3,J1,J4)，则从作业2在机器1处理开始到作业4在机器3处理完

36、成的调度方案如图9.14所示。,设J=J1,J2,J3,J4是4个待处理的作业，每个作业的处理顺序相同，即先在机器1上处理，然后在机器2上处理，最后在机器3上处理，需要的处理时间如图9.13所示。,2023/4/3,第9章 分支限界法,Page 52,一般情况下，对于一个已安排的作业集合M 1,2,n，|M|=k，即已安排了k个作业，设sum1k表示机器1完成k个作业的处理时间，sum2k表示机器2完成k个作业的处理时间，现在要处理作业k+1，此时，该部分解的目标函数值的下界计算方法如下：（1）sum1k+1=sum1k+tk1（2）（3）sum2k+1=maxsum1k+1,sum2k+tk

37、2,批处理作业调度问题的限界函数考虑理想情况，机器1和机器2无空闲，最后处理的恰好是在机器3上处理时间最短的作业。例如，以作业Ji开始的处理顺序，估算处理所需的最短时间是：,2023/4/3,第9章 分支限界法,Page 53,应用分支限界法求解图9.13所示批处理作业调度问题，其搜索空间如图9.15所示，具体的搜索过程如下：（1）在根结点，将sum10和sum20分别初始化为0；（2）在结点2，以作业J1开始处理，则sum11=5，目标函数值为5+(7+5+9+8)+2=36，sum21=5+7=12，将结点2加入待处理结点表PT中；在结点3，以作业J2开始处理，则sum11=10，目标函数

38、值为10+(7+5+9+8)+5=44，sum21=10+5=15，将结点3加入表PT中；在结点4，以作业J3开始处理，则sum11=9，目标函数值为9+(7+5+9+8)+2=40，sum21=9+9=18，将结点4加入表PT中；在结点5，以作业J4开始处理，则sum11=7，目标函数值为7+(7+5+9+8)+2=38，sum21=7+8=15，将结点5加入表PT中；,2023/4/3,第9章 分支限界法,Page 54,（3）在表PT中选取目标函数值极小的结点2优先进行搜索；（4）在结点6，准备处理作业J2，则sum12=5+10=15，目标函数值为15+(5+9+8)+5=42，sum

39、22=15+5=20，将结点6加入表PT中；在结点7，准备处理作业J3，则sum12=5+9=14，目标函数值为14+(5+9+8)+2=38，sum22=14+9=23，将结点7加入表PT中；在结点8，准备处理作业J4，则sum12=5+7=12，目标函数值为12+(5+9+8)+2=36，sum22=12+8=20，将结点8加入表PT中；（5）在表PT中选取目标函数值极小的结点8优先进行搜索；（6）在结点9，准备处理作业J2，则sum13=12+10=22，目标函数值为22+(5+9)+5=41，sum23=22+5=27，将结点9加入表PT中；在结点10，准备处理作业J3，则sum13=

40、12+9=21，目标函数值为21+(5+9)+2=37，sum23=21+9=30，将结点10加入表PT中；,2023/4/3,第9章 分支限界法,Page 55,（7）在表PT中选取目标函数值极小的结点10优先进行搜索；（8）在结点11，准备处理作业J2，则sum14=21+10=31，目标函数值为31+5=36，sum24=31+5=36，由于结点11是叶子结点，并且目标函数值在表PT中最小，则结点11代表的解即是问题的最优解，sum24是机器2完成所有4个作业的时间，则机器3完成所有4个作业的时间是sum24+t23=36+2=38。搜索过程结束。,精品课件！,精品课件！,2023/4/3,第9章 分支限界法,Page 58,Sum2=36表示所有任务在机器2上完成的时间，还要再加上最后一个任务在机器3上所需的时间36+2=38，才是在3台机器上完成所有任务所需要的时间。,