装箱问题和排序问题.ppt_第1页
装箱问题和排序问题.ppt_第2页
装箱问题和排序问题.ppt_第3页
装箱问题和排序问题.ppt_第4页
装箱问题和排序问题.ppt_第5页
已阅读5页，还剩38页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

装箱问题和排序问题 本讲主要内容 装箱问题 BinPacking 最小完工时间安排 排序问题 MinimumMakespanScheduling BinPacking 装箱问题 给定n个物件 大小为用单位体积的箱子来装这些物件 找一个装箱方案使得所用的箱子数目最少 通俗地说 把分成最少的组数 使得每组数的和不超过1 在工业中有许多应用 譬如在下料问题中 箱子代表标准木料的长度 而表示实际问题中需要裁截成的木料长度 当然 需要的标准料越少越好 一个2倍近似算法 证明 一个不可逼近性结果 NP 难问题按照其可逼近性分类 多项式时间近似方案 PolynomialTimeApproximationScheme PTAS 渐近多项式时间近似方案 一个渐进的PTAS 限制装箱问题 限制装箱问题 定理2的证明 算法总结 排序问题 排序问题 MinimumMakespanScheduling 给定n个工件的加工时间以及一个整数m 给工件安排一个在m个相同机器上的加工顺序 使得最后的完工时间 makespan 最小 该问题是排序问题中最简单的问题 在生产调度中有广泛的应用 Graham的2 近似算法 算法描述 ListScheduling Step1 将工件任意排序 Step2 将工件按照上述顺序分配给机器 将下一个工件安排给当前负荷最轻 剩余加工时间最少 的机器 直到所有工件加工完毕 算法分析 上述算法的要点是 让机器不要闲着 只要有机器加工完 就把排在最前面尚待加工的工件让该机器去做 算法分析的要点是 最小makespan取决于最后一个工件的完工时间 在最后一个活开始加工之前 没有机器是空闲的 一个紧的例子 LowestFitDecreasing LFD 算法描述 LFD Step1 将工件按工时从高到低排列 Step2 将工件按照上述顺序分配给机器 将下一个工件安排给当前负荷最轻 剩余加工时间最少 的机器 直到所有工件加工完毕 排序问题的PTAS 排序问题与装箱问题有如下紧密联系 排序问题存在最优解t 当且仅当n个大小分别为的物件可以装入m个容量为t的箱子 因此 可将排序问题自转化为装箱问题 令I表示n个物件大小 令表示能装下n个物件的容量为t的箱子的最少数目 则最小排序问题转化为 基本思想 不同物件型号数目固定的装箱问题 动态规划 动态规划 续 动态规划 续 把排序问题划归为限制装箱问题 基本思想 如果我们能容忍在计算最小makespan问题的一点小的误差 则我们可把该问题在多项式时间内划归为限制装箱问题 主要有两种类型的误差 把物件的尺寸做一些调整 使得不同尺寸的数目有界 终止二分搜索 保证多项式时间算法 每种误差都可以做到任意小 但代价是计算时间的增加 但对固定的误差 我们可以得到多项式时间近似算法 箱子容量固定的装箱算法 核心算法 核心算法 续 二分搜索法 二分搜索 LB 2L
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论