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

工件有到达时间排序问题的LS算法分析

作　者: 杨丽英
导　师: 李荣珩
学　校: 湖南师范大学
专　业: 基础数学
关键词: 在线排序 订单排序 LS算法 最坏情况性能比 半在线 机器最大完工时间
分类号: O223
类　型: 硕士论文
年　份: 2009年
下　载: 35次
引　用: 0次
阅　读: 论文下载
 

内容摘要


排序问题是组合优化领域中的一类重要问题,它是利用一些处理机、机器或者资源,最优地完成一批给定的任务或作业,在生产管理与调度、网络通信、理论计算机科学等方面有广泛的应用。本文主要研究在m台同型机上工件有到达时间的排序问题的LS算法。目标函数是使机器的最大完工时间（makespan）达到最小。第一章介绍了排序问题,算法的竞争比分析等基本概念,描述了（半）在线排序和工件有任意到达时间的在线排序模型的一些特性。第二章研究了m台同型机上有到达时间工件的LS排序问题,研究了LS算法的最坏性能比。给出了LS算法的紧性能比的一个简单证明。第三章讨论了m台同型机上工件有到达时间且加工时间非增的LS算法问题,得到如下的两个结论,一个是证明了对于任意工件序列L={J1,J2,…,Jn} ,如果r1≤r2≤…≤rn且P1≥P2≥…≥Pn,有R（m,LS）≤（?）;另一个是若到达时间为任意的且加工时间为单调非增序列,则LS算法的最坏性能比不大于2。

全文目录


摘要  3-4
ABSTRACT  4-6
第一章 绪论  6-17
  1.1 排序问题  6-9
  1.2 近似算法与竞争比分析  9-11
  1.3 离线和在线排序  11-12
  1.4 半在线排序  12-14
  1.5 工件有任意到达时间的(半)在线排序  14-15
  1.6 论文概述  15-17
第二章 同型机上有到达时间工件的LS排序  17-23
  2.1 引言  17
  2.2 有关定义及算法  17-19
  2.3 LS算法的最坏性能比  19-22
  2.4 小结  22-23
第三章 工件有到达时间且加工时间为非增序列的LS算法分析  23-29
  3.1 引言  23
  3.2 工件有到达时间且加工时间为非增序列的LS算法分析  23-28
  3.3 小结  28-29
总结与展望  29-31
参考文献  31-34
致谢  34-35

相似论文

  1. 面向智能手机的矢—栅混合地图关键技术研究,P208
  2. 工件可拒绝的在线排序问题的两个模型,O223
  3. 工件带有优先约束的平行机在线排序问题,O223
  4. 最大化按时完工工件个数的单位长度工件的单机在线分批排序问题,O223
  5. 部分机器分批的平行机在线排序,O223
  6. 链组约束下的平行机排序问题,O223
  7. 链组约束下的平行机在线排序,O223
  8. 机器有准备时间的平行机半在线排序,O223
  9. 有服务等级约束的平行机排序问题,O223
  10. 带有运输时间的在线排序问题,O223
  11. 带有不可相容工件组的在线排序问题,O223
  12. 具有前瞻区间的分批在线排序问题,O223
  13. 单模光纤的光正交频分复用系统传输性能研究,TN929.11
  14. OFDM系统中信道估计的研究,TN919.3
  15. 可拒绝平行批平行机与在线平行批两台一致机排序,O223
  16. 工件具有相似长度的半在线排序问题,O223
  17. 一致平行机上在线排序,O223
  18. 关于在线排序的近似算法的若干研究,O223
  19. 平行机上工件有到达时间的在线和半在线排序问题,O223
  20. 单机半在线排序算法竞争比分析,O226

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