分枝-限界branchbound内容摘要：
正在展开的子节点 x， 如 ĉ(x)≥U，则停止产生子节点 x， 即不将其放入活节点表 这种限界方法也可用于 FIFO活结点表上，称为 FIFO分枝 限界。 U初始为 ∞ ，其后用新得到的可行解值加以修改 带截止期的作业调度问题（ 1） n个作业， 1台处理机，每个作业 i对应一个三元组(pi,di,ti) pi－ 罚款额 di－ 截止期 ti － 需要的处理机时间 求可行的作业子集 J，使得罚款额 Σpj最小 ,其中 j为不在J中的作业 定长元组表示可行作业子集 :(x(1),┅ ,x(n)) 设 X=(x(1),…x(k)) 为状态空间树的节点 下界 ĉ(x)可估计为已确知的罚款额 : Σ(1x(j))pj ,求和范围为1≤j≤k 带截止期的作业调度问题（ 2） 限界 可行解的必要条件： Σij=1xjtjdi 为能较早地使用 ĉ(x) ≥ U的限界功能 ,可以在每个结点 x计算 c(x)的上界 u(x),并用 u(x)修改 U值 u(x)可取 x为根的子树下包含的任一可行解的值 例如取 x(k+1)=… x(n)=0,或用贪心法快速得到一个可行解 算法每生成一个子节点时就用 u(x)修改 U 调度问题的定长元组表示 已知 4个作业的三元组 (pi,di,ti)分别为 (5,1,1) (10,3,2) (6,2,1) (3,1,1) 调度问题的另一种状态空间树 12543 X1=1876 1015911141312X1=2 X1=3X1=4X2=3X2=316X4=4 X3=3X3=4 X3=4X2=4X2=4 X2=4X3=4LC检索＋限界 689 1 0213 4 51 21 171 3x1= 1x1= 2 x1= 3x1= 4x2。阅读剩余 0%
本站所有文章资讯、展示的图片素材等内容均为注册用户上传(部分报媒/平媒内容转载自网络合作媒体)，仅供学习参考。
用户通过本站上传、发布的任何内容的知识产权归属用户或原始著作权人所有。如有侵犯您的版权，请联系我们反馈本站将在三个工作日内改正。