算法设计ppt课件.ppt

第9章分支限界法BranchandBoundMethod 算法设计与分析 本科DesignandAnalysisofAlgorithm CollegeofInformationScienceandTechnology HainanUniversity 2020 3 27 BranchandBoundMethod 2 学习目标 2020 3 27 BranchandBoundMethod 3 第9章分支限界法 9 1概述 9 2图问题中的分支限界法 9 3组合问题中的分支限界法 2020 3 27 BranchandBoundMethod 4 回溯法 按深度优先策略遍历问题的解空间树 应用约束条件 目标函数等剪枝函数实行剪枝分支限界法 按广度优先策略遍历问题的解空间树 在遍历过程中 对已经处理的每一个结点根据限界函数估算目标函数的可能取值 从中选取使目标函数取得极值的结点优先进行广度优先搜索 从而不断调整搜索方向 尽快找到问题的解 9 1概述 2020 3 27 BranchandBoundMethod 5 9 1概述 9 1 1分支限界法的设计思想 9 1 2分支限界法的时间性能 2020 3 27 BranchandBoundMethod 6 回溯法存在的问题虽用剪枝减少了搜索空间 但按深度优先策略机械地进行 搜索是盲目的 如0 1背包问题 首先将目标函数初始化为最大值 目标函数只有在有一个可行解 第一个叶子 后才有意义 此后的搜索相对来说才有方向 所以从搜索的整个过程来看还是盲目的 如TSP问题 图8 6 分支限界法先确定一个合理的限界函数由限界函数确定目标函数的界 down up 仍以穷举法的解空间树为基础 但以广度优先的原理搜索该结点的所有孩子结点 分别估算这些孩子结点的目标函数的可能取值 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 7 如果某孩子结点的目标函数可能取值超出目标函数的界 则将其丢弃 因为从这个结点生成的解不会比目前已经得到的解更好 否则 将其加入待处理结点表 表PT 依次从表PT中选取使目标函数的值取极值的结点成为当前扩展结点 重复上述过程 直到找到最优解 目标函数的界 down up 的确定对最大化问题Up由限界函数确定 down由某种启发方式得到 如贪心算法对最小化问题down由限界函数确定 up由某种启发方式得到 如贪心算法 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 8 例 0 1背包问题 假设有4个物品 其重量分别为 4 7 5 3 价值分别为 40 42 25 12 背包容量W 10 首先 将给定物品按单位重量价值从大到小排序 结果如下 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 9 确定上下界down 应用贪心法求得近似解为 1 0 0 0 获得的价值为40 这可以作为0 1背包问题的下界 up 考虑最好情况 背包中全部装入第1个物品且可以将背包装满 则可得到一个简单上界的计算方法 up W v1 w1 10 10 100则目标函数的界 40 100 限界函数为 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 10 PT表 图9 10 1背包问题 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 11 分支限界法的搜索过程如下 在根结点1没有物品装入背包 w 0 v 0限界函数值 ub 0 10 0 10 10 100在结点2物品1装入背包 w w1 4 v 40目标函数值 ub 40 10 4 6 76将结点2加入待处理结点表PT中在结点3物品1不装入背包 w 0 v 0目标函数值 10ub 0 10 0 6 60 将结点3加入表PT中 在表PT中选取目标函数值取得极大的结点2优先进行搜索 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 12 在结点4物品2装入背包 w 11 W 不满足约束条件 将结点4丢弃在结点5物品2不装入背包 w 4 v 40与结点2相同目标函数值为 ub 40 10 4 5 70将结点5加入表PT中在结点6物品3装入背包 w 4 5 9 v 40 25 65目标函数值为 ub 65 10 9 4 69将结点6加入表PT中 在表PT中选取目标函数值取得极大的结点5优先进行搜索 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 13 在结点7物品3不装入背包 w 4 v 40 与结点5相同目标函数值为 ub 40 10 4 4 64将结点7加入表PT中在结点8物品4装入背包 w 12 W 不满足约束条件 将结点8丢弃 在结点9物品4不装入背包 w 9 v 65 与结点6相同目标函数值为 ub 65 W w 0 65将结点7加入表PT中 在表PT中选取目标函数值取得极大的结点6优先进行搜索 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 14 结点9是叶子结点同时结点9的目标函数值是表PT中的极大值 结点9对应的解即是问题的最优解 搜索结束在图9 1的0 1背包问题中 为了在搜索过程中构建搜索经过的树结构 设一个表PT 记录搜索过程 如图9 2 再设计了一表ST 从PT中取出最大值结点进行扩充时 将最大值结点存储到表ST中 表PT和表ST的数据结构为 物品i 1的选择结果 ub 在搜索过程中表PT和表ST的状态如图9 2所示 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 15 c 扩展结点5后 d 扩展结点6后 最优解为 1 0 1 0 65图9 2方法 确定0 1背包问题最优解的各分量 3 7 9 2 5 6 7 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 16 基本思想分支限界法常以广度优先或以最小耗费 最大效益 优先的方式搜索问题的解空间树 在分支限界法中 每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点 就一次性产生其所有儿子结点 在这些儿子结点中 导致不可行解或导致非最优解的儿子结点被舍弃 其余儿子结点被加入活结点表中 此后 从活结点表中取下一结点 使目标函数取得极值的结点 成为当前扩展结点 并重复上述结点扩展过程 这个过程一直持续到找到所需的解或活结点表为空时为止 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 17 分支限界法的一般过程1 根据限界函数计算目标函数的 down up 2 将待处理结点表PT初始化为空 3 对根结点的每个孩子结点x执行下列操作3 1估算结点x的目标函数值value 3 2若 value down 则将结点x加入表PT中 4 循环直到某个叶子结点的目标函数值在表PT中最大4 1i 表PT中值最大的结点 4 2对结点i的每个孩子结点x执行下列操作4 2 1估算结点x的目标函数值value 4 2 2若 value down 则将结点x加入表PT中 4 2 3若 结点x是叶子结点且value值在表PT中最大 则将结点x对应的解输出 算法结束 4 2 4若 结点x是叶子结点但value值在表PT中不是最大 则令down value 并且将表PT中所有小于value的结点删除 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 18 目标函数 界 的特性问题的解向量为X x1 x2 xn 其中 xi的取值范围为某个有穷集合Si Si ri 1 i n 是部分解 是相应的界对最小值问题 称为下界 意思是向下搜索所可能取得的值最小不会小于这些下界 若X x1 x2 xn 是所得到的部分解 满足 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 19 对最大值问题 称为上界 意思是向下搜索所可能取得的值最大不会大于这些上界 若是所得到的部分解 满足 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 20 两种分支方法设解向量X x1 x2 xn xi的取值范围为有穷集Si Si n 1 i n每棵子树都有ni个分支最坏情况下 结点表的空间为O n1 n2 nn 若状态空间树是完全n叉树 n1 n2 nn n 结点表的空间为O nn 每棵子树只有两个分支xi取特定值的分支 及不取特定值的分支 状态空间树是完全二叉树 最坏情况下结点表的空间为O 2n 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 21 用分支限界法求解问题的关键如何确定合适的限界函数限界函数用于估算结点的目标函数的可能取值 好的限界函数不仅计算简单 还要保证最优解在搜索空间中 更重要的是能尽早对超出目标函数界的结点进行剪枝 减少搜索空间 有时需要对具体的问题实例进行大量实验才能确定一个合理的限界函数 如何组织待处理结点表为提高查找极值的效率 待处理结点表PT可采用堆或优先队列的形式存储 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 22 用分支限界法求解问题的关键 续 如何确定最优解中的各个分量分支限界法对问题的解空间树中结点的处理是跳跃式的 回溯也不是单纯地沿着双亲结点一层一层向上回溯 因此当搜索到最优解 叶子结点 时 却无法求得该叶子结点对应的最优解中的各个分量 解决方法 对每个扩展结点保存根结点到该结点的路径 在搜索过程中构建搜索经过的树结构 在求得最优解时 从叶子结点不断回溯到根结点 以确定最优解中的各个分量 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 23 c 扩展结点5后 d 扩展结点6后 最优解为 1 0 1 0 65图9 3方法 确定0 1背包问题最优解的各分量 3 7 9 2 5 6 7 分支限界法的设计思想 2020 3 27 BranchandBoundMethod 24 9 1概述 9 1 1分支限界法的设计思想 9 1 2分支限界法的时间性能 2020 3 27 BranchandBoundMethod 25 与回溯法相同点分支限界法和回溯法实际上都是基于蛮力法 遍历具有指数阶个结点的解空间树在最坏情况下 时间复杂性肯定为指数阶2n或nn与回溯法不同点分支限界法首先扩展解空间树中的上层结点 并用限界函数大范围剪枝根据限界函数不断调整搜索方向 选择最有可能取得最优解的子树优先进行搜索如果选择了结点的合理扩展顺序以及设计好的限界函数 分支界限法可以快速得到问题的解 9 1 2分支限界法的时间性能 2020 3 27 BranchandBoundMethod 26 分支限界法的代价首先 设计一个好的限界函数通常需要花费更多的时间计算相应的目标函数值 而且对于具体的问题实例 通常需要进行大量实验 才能确定一个好的限界函数 其次 分支限界法对解空间树中结点的处理是跳跃式的 因此 在搜索到某个叶子结点得到最优值时 为了从该叶子结点求出对应的最优解中的各个分量 需要对每个扩展结点保存该结点到根结点的路径 或者在搜索过程中构建搜索经过的树结构 这使得算法的设计较为复杂 再次 分支限界法为维护PT表需要较大的存储空间 在最坏情况下 分支限界法需要的空间复杂性是指数阶 9 1 2分支限界法的时间性能 2020 3 27 BranchandBoundMethod 27 第9章分支限界法 9 1概述 9 2图问题中的分支限界法 9 3组合问题中的分支限界法 算法设计与分析 BranchandBoundMethod 28 9 2图问题中的分支限界法 9 2 1TSP问题 9 2 2多段图的最短路径问题 2020 3 27 BranchandBoundMethod 29 9 2 1TSP问题 TSP问题是指旅行家要旅行n个城市 要求各个城市经历且仅经历一次然后回到出发城市 并要求所走的路程最短 C 31583 67916 42574 38923 a 一个无向图 b 无向图的代价矩阵图9 4无向图及其代价矩阵 2020 3 27 BranchandBoundMethod 30 确定上界ub采用贪心法求得近似解为 1 3 5 4 2 1ub 1 2 3 7 3 16这可以作为TSP问题的上界确定下界lb把矩阵中每一行最小的元素相加 可以得到一个简单的下界 lb 1 3 1 3 2 10一个信息量更大的下界 把矩阵中每一行最小的两个元素相加再除以2 再对这个结果向上取整 就得到了一个合理的下界 lb 1 3 3 6 1 2 3 4 2 3 2 14则 目标函数的界 lb ub 14 16 注意 该解并不是一个合法的选择 即没构成哈密顿回路 仅给出了一个参考下界 9 2TSP问题 2020 3 27 BranchandBoundMethod 31 部分解的目标函数值的计算方法假设当前已确定的路径为U r1 r2 rk 则 例如图10 4所示无向图 如果部分解包含顶点U 1 4 则该部分解的下界是 lb 2 5 1 3 3 6 1 2 2 3 2 16 分支限界法求解TSP问题示例 2020 3 27 BranchandBoundMethod 32 TSP问题的搜索过程根结点1 加入表PT 为扩展结点目标函数 lb 1 3 3 6 1 2 3 4 2 3 2 14考察孩子结点 结点2 C1 C2 路径长度为3目标函数 lb 2 3 1 6 1 2 3 4 2 3 2 14将结点2加入待处理结点表PT中 在结点3 C1 C3 路径长度为1目标函数 lb 2 1 3 2 3 6 3 4 2 3 2 14将结点3加入表PT中在结点4 C1 C4 路径长度为5目标函数 lb 2 5 1 3 3 6 1 2 2 3 2 16将结点4加入表PT中 31583 67916 42574 38923 2020 3 27 BranchandBoundMethod 33 在结点5 C1 C5 路径长度为8目标函数 lb 2 8 1 2 3 6 1 2 3 4 2 19超出目标函数的界 将结点5丢弃 处理结点2的孩子结点 结点6 C1 C2 C3 路径长度为3 6目标函数 lb 2 9 1 1 3 4 2 3 2 16将结点6加入表PT中在结点7 C1 C2 C4 路径长度为3 7目标函数lb 2 10 1 3 1 2 2 3 2 16将结点7加入表PT中 分支限界法求解TSP问题示例 在表PT中选取目标函数值极小的结点2优先进行搜索 31583 67916 42574 38923 2020 3 27 BranchandBoundMethod 34 在结点8 C1 C2 C5 路径长度为3 9目标函数 lb 2 12 1 2 1 2 3 4 2 19超出目标函数的界 将结点8丢弃处理结点3的孩子 结点9 C1 C3 C2 路径长度为1 6目标函数值 lb 2 7 3 3 3 4 2 3 2 16将结点9加入表PT中在结点10 C1 C3 C4 路径长度为1 4目标函数 lb 2 5 3 3 3 6 2 3 2 15将结点10加入表PT中 分支限界法求解TSP问题示例 在表PT中选取目标函数值极小的结点3优先进行搜索 31583 67916 42574 38923 2020 3 27 BranchandBoundMethod 35 在结点11 C1 C3 C5 路径长度为1 2目标函数值 lb 2 3 3 3 3 6 3 4 2 14将结点11加入表PT中 在表PT中选取目标函数值极小的结点11优先进行搜索 处理结点11的孩子 结点12 C1 C3 C5 C2 路径长度为1 2 9 目标函数值 lb 2 12 3 3 3 4 2 19超出目标函数的界 将结点12丢弃在结点13 C1 C3 C5 C4 路径长度为1 2 3目标函数值 lb 2 6 3 4 3 6 2 14 将结点13加入表PT中 在表PT中选取目标函数值极小的结点13优先进行搜索 31583 67916 42574 38923 2020 3 27 BranchandBoundMethod 36 在表PT中选取目标函数值极小的结点10优先进行搜索 处理结点13的孩子 结点14 C1 C3 C5 C4 C2 路径长度为1 2 3 7 目标函数值 lb 2 13 3 3 2 16由于结点14为叶子结点 得到一个可行解其路径长度为16 31583 67916 42574 38923 分支限界法求解TSP问题示例 2020 3 27 BranchandBoundMethod 37 分支限界法求解TSP问题示例 在表PT中选取目标函数值极小的结点16优先进行搜索 处理结点10的孩子 结点15 C1 C3 C4 C2 长度12 目标函数 lb 2 12 3 3 2 3 2 18超出目标函数的界 将结点15丢弃结点16 C1 C3 C4 C5 长度8目标函数 lb 2 8 3 2 3 6 2 15将结点16加入表PT中 处理结点16的孩子 结点17 C1 C3 C4 C5 C2 长度17 目标函数 lb 2 17 3 3 2 20 超目标函数的界 结点17丢弃表PT中目标函数值均为16 且已找到叶子结点14的长度是16 故这是最优解 搜索过程结束 31583 67916 42574 38923 2020 3 27 BranchandBoundMethod 38 分支限界法求解TSP问题示例 C2 C1 C3 C5 C4 C3 C5 C4 C2 C4 C5 C4 C2 C2 31583 67916 42574 38923 2020 3 27 BranchandBoundMethod 39 2020 3 27 BranchandBoundMethod 40 9 2TSP问题 算法设计与分析 BranchandBoundMethod 41 9 2图问题中的分支限界法 9 2 1TSP问题 9 2 2多段图的最短路径问题 算法设计与分析 BranchandBoundMethod 42 9 2 2多段图的最短路径问题 设图G V E 是一个带权有向连通图 如果把顶点集合V划分成k个互不相交的子集Vi 2 k n 1 i k 使得E中的任何一条边 u v 必有u Vi v Vi m 1 i k 1 i m k 则称图G为多段图 称s V1为源点 t Vk为终点 多段图的最短路径问题是求从源点到终点的最小代价路径 算法设计与分析 BranchandBoundMethod 43 对图9 7所示多段图应用贪心法求得近似解为0 2 5 8 9 其路径代价为2 7 6 3 18 这可以作为多段图最短路径问题的上界 把每一段最小的代价相加 可以得到一个非常简单的下界 其路径长度为2 4 5 3 14 于是 得到了目标函数的界 14 18 由于多段图将顶点划分为k个互不相交的子集 所以 多段图划分为k段 一旦某条路径的一些段被确定后 就可以并入这些信息并计算部分解的目标函数值的下界 一般情况下 对于一个正在生成的路径 假设已经确定了i段 1 i k 其路径为 r1 r2 ri ri 1 此时 该部分解的目标函数值的计算方法即限界函数如下 算法设计与分析 BranchandBoundMethod 44 应用分支限界法求解图9 7所示多段图的最短路径问题 其搜索空间如图9 8所示 具体的搜索过程如下 加黑表示该路径上已经确定的边 1 在根结点1 计算目标函数的值为14 将根结点加入表PT 2 处理根结点每个孩子结点 结点2 第1段选择边 目标函数值为lb 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优先进行搜索 算法设计与分析 BranchandBoundMethod 45 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 处理结点5的每个孩子结点 结点7 已确定路径是0 3 5 7 可直接确定第4段的边 目标函数值为lb 3 4 8 7 22 超界丢弃 在结点8 已确定路径是0 3 5 8 可直接确定第4段的边 目标函数值为lb 3 4 6 3 16 为一个可行解 由于结点8是叶子结点 并且其目标函数值是PT中最小的 所以它是最优解 搜索结束 算法设计与分析 BranchandBoundMethod 46 2020 3 27 BranchandBoundMethod 47 第9章分支限界法 9 1概述 9 2图问题中的分支限界法 9 3组合问题中的分支限界法 2020 3 27 BranchandBoundMethod 48 9 3组合问题中的分支限界法 9 3 2任务分配问题 9 3 3批处理作业调度问题 9 3 10 1背包问题 2020 3 27 BranchandBoundMethod 49 问题描述任务分配问题要求把n项任务分配给n个人 每个人完成每项任务的成本不同 要求分配总成本最小的最优分配方案 如图9 10所示是一个任务分配的成本矩阵 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 50 如何求最优分配成本的上界Up和下界Down获得上界UP如考虑以矩阵的对角线作为一个可行解 任务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 1414是一个更好的上界 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 51 获得下界Down考虑人员a 所有任务的最小代价是2人员b 执行所有任务的最小代价是3人员c 执行所有任务的最小代价是1人员d 执行所有任务的最小代价是4每行取最小元素 其成本下界 2 3 1 4 10则上下界为 10 14 注意 这个解并不是一个合法的选择因为 3 1来自于矩阵同一列 仅给出一个参考下界 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 52 设当前已对人员1 i分配了任务 并且获得了成本v 则限界函数可以定义为 式9 4 搜索过程在根结点1没有分配任务 限界函数函数值为 lb 2 3 1 4 10在结点2将J1 人员a 获得的成本为9目标函数值为 lb 9 3 1 4 17超出目标函数的界 10 14 将结点2丢弃 9 3 2任务分配问题 C 9278643758187694 人员a人员b人员c人员d 2020 3 27 BranchandBoundMethod 53 图9 11分支限界法求解任务分配问题示例 表示该结点被丢弃 结点上方的数组表示搜索顺序 C 任务1 任务4 任务2 任务1 任务3 任务4 任务1 任务4 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 54 搜索过程在结点3将J2 人员a 获得的成本为2目标函数值 lb 2 3 1 4 10将结点3 PT表中在结点4将J3 人员a 获得的成本为7目标函数值 lb 7 3 1 4 15超出目标函数的界 10 14 将结点4丢弃 9 3 2任务分配问题 C 2020 3 27 BranchandBoundMethod 55 在结点5将J4 人员a 获得的成本为8目标函数值 lb 8 3 1 4 16超出目标函数的界 10 14 将结点5丢弃 在结点6将J2 人员a J1 人员b 获得的成本为2 6 8目标函数值 lb 8 1 4 13将结点6加入表PT中 在表PT中选取目标函数值极小的结点3优先进行搜索 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 56 在结点7将J2 人员a J3 人员b 获得的成本为2 3 5目标函数值 lb 5 1 4 10将结点7加入表PT中在结点8将J2 人员a J4 人员b 获得的成本为2 7 9目标函数值 lb 9 1 4 14将结点8加入表PT中 在表PT中选取目标函数值极小的结点7优先进行搜索 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 57 在结点9将J2 人员a J3 人员b J1 人员c 获得的成本为5 5 10目标函数值 lb 10 4 14将结点9加入表PT中在结点10将J2 人员a J3 人员b J4 人员c 获得的成本为5 8 13目标函数值 lb 13 4 17超出目标函数的界 10 14 将结点10丢弃 在表PT中选取目标函数值极小的结点6优先进行搜索 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 58 在结点11将J2 人员a J1 人员b J3 人员c 获得的成本为8 1 9目标函数值 lb 9 4 13将结点11加入表PT中在结点12将J2 人员a J1 人员b J4 人员c 获得的成本为8 8 16目标函数值 lb 16 4 20超出目标函数的界 10 14 将结点12丢弃 在表PT中选取目标函数值极小的结点11优先进行搜索 9 3 2任务分配问题 9278643758187694 任务1任务2任务3任务4 2020 3 27 BranchandBoundMethod 59 在结点13将J2 人员a J1 人员b J3 人员c J4 人员d获得的成本为9 4 13目标函数值为 lb 13由于结点13是叶子结点 同时结点13的目标函数值是表PT中的极小值 所以 结点13对应的解即是问题的最优解搜索结束 构建搜索经过的树结构取出表PT中最小值结点进行扩充时 并将最小值结点存储到ST中 表PT和表ST的数据结构为 人员i 1分配的任务 lb 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 60 人员i 1分配的任务 lb e 扩展结点11后的状态 最优解为2 a 1 b 3 c 4 d 0 10 2 13 2 10 2 14 0 10 2 13 2 14 3 14 0 10 2 10 2 14 3 14 1 13 0 10 2 10 2 13 0 10 2 10 2 13 1 13 a 扩展根结点后的状态 b 扩展结点3后的状态 PTSTPTSTPTST c 扩展结点7后的状态 d 扩展结点6后的状态 2 14 3 14 3 13 PTSTPTST 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 61 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 62 9 3 2任务分配问题 2020 3 27 BranchandBoundMethod 63 9 3组合问题中的分支限界法 9 3 2任务分配问题 9 3 3批处理作业调度问题 9 3 10 1背包问题 2020 3 27 BranchandBoundMethod 64 问题描述n个作业的集合J J1 J2 Jn 每个作业都有3项任务分别在3台机器上完成Ji需要机器j的处理时间为tij 1 i n 1 j 3 作业处理顺序 机器1处理 机器2处理 机器3处理批处理作业调度问题 要求确定这n个作业的最优处理顺序使得从第1个作业在机器1上处理开始 到最后一个作业在机器3上处理结束所需的时间最少 最优调度原则使机器1没有空闲时间 且机器2和3的空闲时间最小 9 3 3批处理作业调度问题 2020 3 27 BranchandBoundMethod 65 设J J1 J2 J3 J4 是4个待处理的作业 每个作业的处理顺序相同 机器1上处理 机器2上处理 机器3上处理需要的处理时间如下矩阵所示 9 3 3批处理作业调度问题 2020 3 27 BranchandBoundMethod 66 上界 随机产生几个方案 从中选取最短完成时间为问题的上界 如若处理顺序为 J4 J1 J3 J2 调度方案 J4 7J1 5J3 9J2 10 机器1机器2机器3 图9 13批处理调度问题的调度方案 空闲 7J4 8J1 7J3 9J2 5 空闲 15J4 10J1 9J3 5J2 2 9 3 3批处理作业调度问题 上界 41 2020 3 27 BranchandBoundMethod 67 批处理作业调度问题的限界函数down理想情况机器1和机器2开始作业后无空闲 最后处理的恰好是在机器3上处理时间最短的作业 例如 以作业Ji开始的处理顺序 估算处理所需的最短时间是 tij 表示Ji需要机器j的处理时间 1 i n 1 j 3 9 3 3批处理作业调度问题 作业Ji在机器1上的处理时间 作业1 作业n在机器2上的处理时间总和 在机器3上处理时间最短的作业 2020 3 27 BranchandBoundMethod 68 目标函数下界计算lb若已安排了k 1个作业集合 即 M 1 2 k 1 M k 1sum1 k 1 机器1完成k 1个作业的处理时间sum2 k 1 机器2完成k 1个作业的处理时间现要处理作业k 此时 该部分解的目标函数值的下界lb计算方法如下 1 sum1 k sum1 k 1 tk1 2 3 sum2 k max sum1 k sum2 k 1 tk2 9 3 3批处理作业调度问题 2020 3 27 BranchandBoundMethod 69 分支限界法搜索过程在根结点将sum1 0 和s