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

关于同类机半在线排序问题的若干研究

作　者: 刘嘉诚
导　师: 罗来兴
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 运筹学 排序问题 半在线 竞争比
分类号: O223
类　型: 硕士论文
年　份: 2007年
下　载: 36次
引　用: 1次
阅　读: 论文下载
 

内容摘要


所谓排序，就是在一定的约束条件下对工件和机器按时间进行分配和安排加工次序，使一个或多个目标达到最优。它可以分为经典排序和现代排序。相对于经典排序而言，现代排序是非经典的、新型的排序。近几十年来，有关现代排序的研究有了很大的发展，新的排序模型也不断涌现。常见的现代排序模型有可控排序、成组分批排序、多目标排序、在线排序和半在线排序等等。第一章，主要介绍了排序的产生背景、发展，及其一些符号等相关的基础知识。第二章，考虑已知工件最大加工时间的同类机半在线排序问题，目标为极小化机器最大负载．对于三台特殊同类机问题，当s1=s3=s≥1=s，并且最大加工时间已知时，给出了竞争比不大于4s+2/3s（1＜s≤2）和3s+1/2s（s＞2）的半在线算法。第三章，讨论了两台同类机的半在线问题，目标为极小化工件最大完工时间。对已知所有任务总加工时间和最大任务加工时间的半在线问题，给出了竞争比为4s+2/3s+2的最优半在线算法。

全文目录


摘要  4-5
Abstract  5-7
第一章 绪论  7-20
  第一节 基础知识  7-13
  第二节 排序间题在我国的引入与现状  13-15
  第三节 半在线排序问题  15-18
  第四节 近似算法与竞争比  18-20
第二章 三台同类机的半在线排序问题  20-30
  第一节 相关介绍  20-22
  第二节 主要结果及证明  22-30
第三章 复合两信息的同类机半在线排序问题  30-38
  第一节 相关介绍  30-33
  第二节 主要结果及证明  33-38
参考文献  38-42
致谢  42

相似论文

  1. 工件排序问题的若干研究,O157.5
  2. 面向智能手机的矢—栅混合地图关键技术研究,P208
  3. 带参数的平行机和流水作业排序问题的复杂性及算法研究,O223
  4. 工件可拒绝的在线排序问题的两个模型,O223
  5. 工件带有优先约束的平行机在线排序问题,O223
  6. 部分机器分批的平行机在线排序,O223
  7. 等长工件序约束下分批在线排序,O223
  8. 链组约束下的平行机排序问题,O223
  9. 链组约束下的平行机在线排序,O223
  10. 两类特殊的在线分批排序问题,O223
  11. 机器有准备时间的平行机半在线排序,O223
  12. 工件有到达时间排序问题的LS算法分析,O223
  13. 平行机上工件有到达时间的在线和半在线排序问题,O223
  14. 单机半在线排序算法竞争比分析,O226
  15. 分批排序问题及带机器准备时间的同类机排序问题,O223
  16. 同类机半在线机器覆盖问题研究,O223
  17. 同类平行机半在线排序问题的若干研究,O223
  18. l_p范数下两台同型机排序问题研究,O223
  19. 平行机可中断半在线排序问题的若干研究,O223
  20. （半）在线排序中若干问题的研究,O223
  21. 机器带准备时间的两台同类机半在线排序,O223

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