学位论文 > 优秀研究生学位论文题录展示
多目标排序问题
作 者: 梁天娟
导 师: 唐国春
学 校: 重庆师范大学
专 业: 运筹学与排序论
关键词: 多目标排序 约束解 启发式算法 分支定界算法 优势准则
分类号: O223
类 型: 硕士论文
年 份: 2008年
下 载: 100次
引 用: 0次
阅 读: 论文下载
内容摘要
多目标排序是研究多个优化目标的排序问题,它在解决经济、管理、工程、军事和社会等领域出现的复杂问题中起着越来越重要的作用。以往对单台机器排序问题的研究大都限于单目标排序,追求某一个目标的优化时往往以劣化其他目标为代价。然而在实际的生产调度和计划管理中,绝大多数情况需要综合考虑一个作业排序的许多性能指标,即需要求解多个目标函数的最优或近似最优加工顺序或在某目标函数约束范围下求其它一些函数的最优或近似最优解的排序。如果研究这些问题提出他们的解决方案,并进一步有效地、恰当地将这种方法应用于经济、管理、工程及社会相关领域,那么对于提高生产率、增加利润、扩大生产都是非常有益的。当γ1和γ2∈{Tmax,∑Cj,∑wjCj,∑Tj,∑wjTj,∑Uj,∑wjUj},可以提出P72=42个不同的多重目标排序问题,对应有42个约束多目标排序问题。本文着力研究了其中的7个约束解问题,相应问题的多重解可视为约束解的一种特例。第一章:综述了排序的研究意义与研究现状;引入排序问题的常用参数及记号;介绍了单机多目标排序问题的已知结果。第二章:针对在实际问题中往往是允许工件误工的,也就是说,工件可以在交货期之后完工,即允许工件有延迟或者延误,只是对于不同的问题对工件的延迟或者延误有不同的要求。本章节研究以延迟和延误为第1目标的四个约束多目标排序问题,在最大延迟Lmax、总延迟∑Lj、最大延误Tmax或者总延误∑Tj不超过给定的量的约束条件下,寻找使平均完工时间为最小的排序,给出前三个问题相应的最优算法,由于最后一个问题是NP难题,本文提出了分支定界算法、启发式算法及其加速搜索的方法,并找到了启发式算法为最优时,工件的加工时间和交货期之间必须满足的条件。第三章:考虑n个工件在单台机器上加工在误工工件个数少于某个确定数的条件下使总完工时间(或平均完工时间)最小的多目标排序问题,即问题1‖(∑Cj/∑Uj≤k)。首先,对于某些工件必须不误工使总完工时间(平均完工时间)为最小排序问题,提出简单的算法。与Moore算法结合利用简单的启发式方法,给出分支定界算法,借助优势规则删掉许多分支,能够有效地得到最优解。第四章:本章节研究了以总完工时间为第一目标的两个约束多目标排序问题,在总完工时间不超过给定量的约束条件下,寻找使带权完工时间或最大延误为最小的排序,分别给出了相应的启发式算法和分支定界算法;
|
全文目录
中文摘要 3-4 英文摘要 4-7 1 绪论 7-13 1.1 排序研究意义与研究现状 7-9 1.2 一般排序问题的常用参数及记号 9-11 1.3 单机多目标排序问题的已知结果 11-13 2 以延迟和延误为第1目标的约束多目标排序问题 13-23 2.1 以最大延迟为第1目标 13-15 2.2 以总延迟为第一目标 15 2.3 以最大延误为第一目标 15 2.4 以总延误为第一目标 15-23 2.4.1 问题1‖(∑C_j/∑T_j≤T)的分支定界算法 15-17 2.4.2 分支定界算法的上界 17-21 2.4.3 优势条件 21-23 3 在误工个数受限的条件下使总完工时间最小的排序问题 23-27 4 以总完工时间为第一目标的多目标排序问题 27-33 4.1 问题1‖(∑w_jC_j/∑C_j≤C) 27-30 4.1.1 问题1‖(∑w_jC_j/∑C_j≤C)的一个启发式算法 27-29 4.1.2 分支定界算法 29-30 4.2 问题1‖(T_(max)/∑C_j≤C) 30-32 4.3问题1‖(L_(max)/∑C_j≤C) 32-33 5 结束语 33-35 5.1 总结全文 33 5.2 后续工作 33-35 参考文献 35-37 附:作者在攻读硕士学位期间发表的论文目录 37-38 致谢 38-39
|
相似论文
- 太原市嘉乡生态食品加盟店选址研究,F426.82
- 基于蚁群算法的车辆调度问题研究,TP301.6
- MIMO系统信号检测方法及球检测改进算法的研究,TN919.3
- 基于磁滞优化的车辆路径问题研究,O224
- 多订单并行分拣问题的优化研究,F224
- 飞机总装移动装配线作业调度优化研究,V262.43
- 柔性资源动态组合生产调度算法研究与实现,F426.8
- 基于资源需求分析的准时生产工厂物流优化研究,F426.471
- 蚁群优化算法及其应用研究,TP301.6
- 订单生产方式下基于人员因素的混合装配线平衡研究,F273;F224
- 关键链管理在工程项目进度管理中的运用研究,F224
- 基于供应链环境下的配送中心选址研究,F224
- 网络选址中的若干模型和算法研究,O221.4
- 带参数的平行机和流水作业排序问题的复杂性及算法研究,O223
- 基于粗糙集的属性约简算法研究,TP18
- 110出警线路优化系统的设计与实现,TP301.6
- 多输出函数逻辑综合的理论研究与程序实现,TN47
- 基于分支定界算法的三层决策模型与应用研究,C934
- 两类双目标排序问题研究,O223
- 经典误工排序问题及其在多重目标排序中的进展,O223
- 基于鲁棒优化方法的一体化炼钢炉次批量计划研究,TF758
中图分类: > 数理科学和化学 > 数学 > 运筹学 > 统筹方法
© 2012 www.xueweilunwen.com
|