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

两类双目标排序问题研究

作　者: 史媛媛
导　师: 吕绪华
学　校: 武汉科技大学
专　业: 应用数学
关键词: 多目标排序分支定界算法优势条件启发式算法
分类号: O223
类　型: 硕士论文
年　份: 2010年
下　载: 18次
引　用: 0次
阅　读: 论文下载

内容摘要

排序问题是一类非常重要的组合最优化问题,排序是在一定的约束条件下对工件和机器按时间进行分配和安排次序。在经典的排序问题中,大多数情况都是研究仅一个目标函数的单目标排序问题。然而在生产管理实践中有些情况不仅仅只需要考虑一个方面的性能指标,而是需要综合考虑多个性能指标,即需要求解多个目标函数的最优或近似最优或在某目标函数约束范围下求其它一些函数的最优或近似最优解的排序。多目标排序问题被广泛应用于计算机系统、生产管理等其它各个领域,具有广泛的生产实践背景和应用价值。本论文共分为五个章节:第一章简述排序问题的基本理论。第二章介绍本文主要研究的两类多目标排序问题的研究成果和发展现状。第三章研究以工件总误工数为第一目标,以最小加权总提前完工时间为第二目标的双目标函数排序问题。对该排序问题,在文献[1]的基础上提出分支定界算法,并给出几种特殊情况下的多项式算法;进一步,将单机排序中的所得结论推广到m台平行机的排序中,得到该排序问题在平行机中的相应算法与相关结论。第四章研究以最大延误不超过某个特定值为第一目标,以加权总完工时间为第二目标的约束性双目标函数排序问题。在单机排序中,找到该问题最优解并证明其最优性;在平行机排序中,研究了两台平行机及设定权重恒为一的条件下,找出其相应的算法,最后把该问题推广到m台平行机上,找出其优势条件。第五章是对本论文内容的总结,并提出了对未来的工作设想和努力的方向。

全文目录

摘要  4-5
Abstract  5-8
第一章绪论  8-13
  1.1 排序问题的发展状况  8
  1.2 排序问题的常用记号和参数  8-11
  1.3 排序问题的计算复杂性  11-12
  1.4 本文的主要研究成果和创新  12-13
第二章相关问题的研究现状  13-19
  2.1 单机多目标排序问题  13-14
  2.2 平行机排序问题  14-15
  2.3 与本文相关联的单目标排序问题  15-19
第三章单机多目标排序问题1‖∑a_j E _j / ∑U _j  19-29
  3.1 ∑∑ 1‖ a j Ej/Uj问题的描述  19
  3.2 ∑∑ 1‖ a j Ej/Uj的启发式算法  19-20
  3.3 分支定界算法  20-24
  3.4 几种特殊情况下的多项式算法  24-25
  3.5 ∑∑ Pm ‖ ajEj/Uj问题的描述  25-26
  3.6 求解 ∑∑ Pm ‖ ajEj/Uj的启发式算法  26-29
第四章多目标排序问题1‖∑w_jc_j/L_(max) ≤L  29-36
  4.1 1‖∑w_jc__j/L_(max) ≤L 问题的描述  29
  4.2 1‖∑w_jc_j/L_(max) ≤L 的多项式算法  29-33
  4.3 P_2‖∑C_j/L_(max) ≤L 问题的描述  33
  4.4 P_2‖∑C_j/L_(max) ≤L 的启发式算法  33-34
  4.5 本章小结  34-36
第五章结束语  36-37
参考文献  37-41
致谢  41-42
附录 A 攻读学位期间发表的论文  42

两类双目标排序问题研究

内容摘要

全文目录

相似论文