学位论文 > 优秀研究生学位论文题录展示

可自由离线批处理机最小化加权完工时间和排序

作　者: 卫志刚
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 批排序 工件可自由离线 总加权完工时间 竞争比
分类号: O223
类　型: 硕士论文
年　份: 2011年
下　载: 7次
引　用: 0次
阅　读: 论文下载
 

内容摘要


批处理排序是排序领域中一类重要问题.批处理是指处理机可以同时将b个工件作为一批,在相同的批开工时间同时加工.对于输入的n个工件,要求将n个工件安排到若干批中,并且决定这些批的开始加工时间：使得给定的目标函数值最小在本文中,工件具有自由离线的性质,目标函数是总加权完工时间.工件可自由离线(item-availability)是指,同一批中的每个工件完工时间等于该批的开工时间与该工件的加工时间之和.本文对完工工件可自由离线的单台批处理机最小化加权完工时间和排序的在线和离线情况分别做了研究.在线情形下,对于批容量无限(b=+∞)的模型,给出了一个竞争比是2+α的柔性算法(α=(?)-1/2),并证明了该竞争比是紧的(tight)对于容量有限(b<n)的模型,给出了一个(4+ε)近似的在线算法.离线情形下,首先证明了批容量无限(b=+∞),且工件到达时间(release-date)不全相同的批排序问题是NP-困难的,然后给出一个全多项式近似方案(FPTAS)对于工件加工时间的种类为固定常数的情形,给出了一个多项式时间的动态规划算法.对于批容量有限的模型,对工件到达时间不全相同且所有的工件加工时间都相同的情形,证明了可在多项式时间找到一个最优排序.对工件到达时间相同且工件权重全相同的情形：设计出一个2-近似的算法.

全文目录


摘要  4-5
Abstract  5-7
第一章 引言  7-15
  1.1 问题的背景和基本定义  7-9
  1.2 预备知识  9-10
  1.3 相关结果  10-13
  1.4 本文主要结果  13-15
第二章 在线排序  15-23
  2.1 引言  15-16
  2.2 批容量无限的模型  16-20
  2.3 批容量有限的模型  20-23
第三章 离线排序  23-46
  3.1 引言  23-24
  3.2 批容量有限模型  24-35
  3.3 批容量无限模型  35-46
参考文献  46-49
致谢  49

相似论文

  1. 工件可拒绝的在线排序问题的两个模型,O223
  2. 不相容工件族的平行批序的一些结果,O223
  3. 链组约束下的平行机在线排序,O223
  4. 带有运输时间的在线排序问题,O223
  5. 带有不可相容工件组的在线排序问题,O223
  6. 批容量有界的单机分批列表在线排序,O223
  7. 单机在线继列分批排序与离线混合分批排序,O223
  8. 同类机半在线机器覆盖问题研究,O223
  9. 具有非交叉维修时间的平行机在线排序,O223
  10. 特殊并行工件排序的研究,O223
  11. 具有机器准备时间的半在线排序问题,O223
  12. 机器有两种不同速度的平行工件在线排序,O223
  13. 含有双重在线限制的排序问题,O223
  14. 允许重启的平行分批在线排序问题,O223
  15. 带有运输的单机平行分批在线排序问题,O223
  16. 一类平行机在线分批排序问题,O223
  17. 机器带准备时间的两台同类机半在线排序,O223
  18. 平行机可中断半在线排序问题的若干研究,O223
  19. l_p范数下两台同型机排序问题研究,O223
  20. 同类平行机半在线排序问题的若干研究,O223

中图分类: > 数理科学和化学 > 数学 > 运筹学 > 统筹方法
© 2012 www.xueweilunwen.com