一些现代排序问题的算法设计与分析

发布时间：2017-08-15 22:23

  本文关键词：一些现代排序问题的算法设计与分析

  更多相关文章： 排序 近似算法 可拒绝 不可用时间约束 自动仓储系统

【摘要】：本论文主要研究了一些现代排序问题,包括带有拒绝的排序问题、带有不可用时间约束的排序问题以及烟草制造行业中产生的自动仓储系统一轨双车排序调度问题。我们研究了这些问题的性质,对这些问题分别设计了算法,分析了算法的性能比或竞争比,并对一些问题使用数值模拟验证了算法的有效性,全文共分六章。第一章介绍了组合优化问题和排序问题的研究背景,引入了本文涉及的基本概念和定义。对经典排序问题、在线排序问题、带有拒绝的排序问题和带有不可用时间约束的排序问题,分别介绍了目前的研究现状和研究结果。第二章研究了带有拒绝的单机和同型机排序问题。对于带有拒绝的单机排序问题,我们研究了惩罚费用是对应工件加工时间α倍的情形。当工件有不同的到达时间时,目标函数为时间表长与惩罚费用之和的问题是可解的；当所有工件在零时刻到达时,目标函数为总完工时间与惩罚费用之和的问题也是可解的。对于带有拒绝的同型机排序问题,我们研究了至多有两个到达时间的在线情形,对机器台数是2和m的情形,分别给出了竞争比为2和4—2/m的在线算法。第三章研究了带有拒绝的两机流水作业排序问题。每个工件有两个操作,每个操作可以被接受并安排到机器上加工,或者被拒绝并支付一定的惩罚费用。两台机器上操作的惩罚费用分别为对应加工时间的α1倍和α2倍。目标函数是最小化时间表长和惩罚费用之和。对于此问题min{α1,α2}1且max{α1,α2}≥1的情形,我们给出了性能比为4/3的近似算法。对于α1和α2的一般情形,我们给出了两个时间复杂度不同的动态规划算法,并设计了完全多项式时间近似方案(FPTAS)。第四章研究了带有不可用时间约束的单机半在线排序问题。在此问题中,机器由于维修或故障等原因,有一个不可用时间段,工件无法在此时间段内进行加工。工件是在线实时到达的,目标函数是最小化时间表长。我们研究了这个问题的半在线形式,即工件的某些信息在初始时刻是已知的。对于已知最大工件的加工时间、所有工件的加工时间和、最后工件的到达时间、最优时间表长这四个半在线问题,我们分别研究了问题的下界,给出了半在线算法,并证明了这些算法的竞争比。第五章研究了由烟草制造行业提出的自动仓储系统一轨双车排序调度问题。在这个系统中有两台堆垛机运行于同一轨道上,两台堆垛机之间需要保持一定的安全距离。轨道两侧分别有高层货架,多个出／入货口位于高层货架的底部。运送货箱的请求由成型机与发射机在线实时产生,堆垛机在机器与高层货架之间运送货箱。问题的目标是保证系统安全运行,满足生产要求,最小化完成所有请求时所需要的时间。这个问题可以看成是一个在线排序与路线问题。在给定系统的物理布局下,我们证明了问题的复杂性。对于一轨单车模型与一轨双车模型两种情形,我们给出了四个在线控制策略,形成在线算法,并用实例与数值模拟验证了在线算法的有效性。算法已经投入实际使用并取得了良好的效果。第六章对本论文进行了总结,介绍了未来可以研究的方向及问题。
【关键词】：排序 近似算法 可拒绝 不可用时间约束 自动仓储系统
【学位授予单位】：华东理工大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要5-7
• Abstract7-11
• 第1章 绪论11-27
• 内容提要11
• 1.1 组合优化问题11
• 1.2 算法和复杂性11-15
• 1.3 离线问题与在线问题15-16
• 1.4 排序问题16-18
• 1.5 文献综述18-24
• 1.5.1 经典排序问题和在线排序问题19-20
• 1.5.2 带有拒绝的排序问题20-22
• 1.5.3 带有不可用时间约束的排序问题22-24
• 1.6 论文概述24-27
• 第2章 带有拒绝的单机和同型机排序问题27-37
• 内容提要27
• 2.1 引言27-28
• 2.2 两个单机可解的情形28-30
• 2.3 m台同型机的情形30-37
• 第3章 带有拒绝的两机流水作业排序问题37-53
• 内容提要37
• 3.1 引言37-38
• 3.2 问题性质38-39
• 3.3 4/3-近似算法39-43
• 3.4 动态规划算法43-50
• 3.5 FPTAS50-53
• 第4章 带有不可用时间约束的单机半在线排序问题53-73
• 内容提要53
• 4.1 引言53-55
• 4.2 问题1,h_1|nr-a,r_j,online,p_(max)|C_(max)55-62
• 4.3 问题1,h_1|nr-a,r_j,online,sum|C_(max)62-65
• 4.4 问题1,h_1|nr-a,r_j,online,r_(max)|C_(max)65-68
• 4.5 问题1,h_1|nr-a,r_j,online,opt|C_(max)68-73
• 第5章 一轨双车自动仓储系统的在线算法设计与分析73-91
• 内容提要73
• 5.1 引言73-75
• 5.2 问题描述75-77
• 5.3 一轨单车模型77-84
• 5.3.1 指派策略77-78
• 5.3.2 排序策略78-84
• 5.4 一轨双车模型84-86
• 5.4.1 分配策略84
• 5.4.2 安全策略84-86
• 5.5 实例与数值模拟86-91
• 5.5.1 应用实例86-87
• 5.5.2 数值模拟87-91
• 第6章 结论与展望91-93
• 参考文献93-101
• 致谢101-103
• 附录：博士在读期间完成的论文103

【共引文献】

中国期刊全文数据库 前10条

1 陶玉敏;;无向反转排序问题的遗传模拟退火求解[J];辽宁科技大学学报;2009年04期

2 李琳;白运;;大地电磁模拟退火反演研究[J];安阳工学院学报;2011年02期

3 贾煜亮;缪立新;;自动化立体仓库中货位实时分配优化问题研究[J];北京交通大学学报(社会科学版);2007年04期

4 曹守华;袁振洲;韩宝明;李得伟;;基于SOFM神经网络的客运一体化枢纽分类[J];北京交通大学学报;2008年06期

5 黎浩东;何世伟;宋瑞;纪丽君;申永生;;列车编组计划和技术站布局的综合优化[J];北京交通大学学报;2010年06期

6 赵博文;余永刚;潘玉竹;;随行装药退火算法的优化设计及数值模拟[J];火炸药学报;2010年05期

7 夏志安;赵英俊;;基于遗传算法的装备器件更换周期优化模型[J];兵工自动化;2008年08期

8 王文峰;刘亚杰;郭波;;战役装备维修保障网络设计问题研究[J];兵工学报;2008年12期

9 陈云霞;高洁萍;夏华凤;曾声奎;;基于遗传算法的多学科设计优化分解方法[J];北京航空航天大学学报;2009年06期

10 李少保;赵春晓;;基于多Agent遗传算法求解迷宫游戏[J];北京建筑工程学院学报;2011年03期

中国博士学位论文全文数据库 前10条

1 李佳;载人潜器阻力性能的数值和试验预报及外形优化研究[D];哈尔滨工程大学;2010年

2 宋越明;基于粒子滤波的跟踪方法研究[D];解放军信息工程大学;2010年

3 王晓娟;多目标柔性作业车间调度方法研究[D];华中科技大学;2011年

4 程文涛;关节式坐标测量机标定技术研究[D];合肥工业大学;2011年

5 王联国;人工鱼群算法及其应用研究[D];兰州理工大学;2009年

6 陈雪;太阳能热光伏系统机理与实验研究[D];南京理工大学;2010年

7 王筱蓉;冲压增程炮弹进气道型面气动优化方法研究[D];南京理工大学;2010年

8 缪濵;公（铁）工程三维选线的群智能算法研究[D];中南大学;2011年

9 张恒;无线接入网中无线下行覆盖自优化和自主负载均衡方法[D];北京邮电大学;2011年

10 查靓;精益生产方式下U型流水线平衡的优化模型与算法研究[D];华南理工大学;2011年

中国硕士学位论文全文数据库 前10条

1 吴家瑞;服装产品加工成本快速估算方法研究[D];浙江理工大学;2010年

2 周宇龙;基于遗传算法的堤防材料动力特性反演分析[D];郑州大学;2010年

3 王斌;浅层地表缺陷动力探测技术研究[D];郑州大学;2010年

4 石丽丽;智能优化算法对比研究及其在船体双底结构优化中的应用[D];哈尔滨工程大学;2010年

5 王宏云;基于数据挖掘的煤矿安全监测系统研究[D];辽宁工程技术大学;2009年

6 高婷;智能天线系统中的动态信道分配算法研究[D];辽宁工程技术大学;2010年

7 李天赞;神经网络在电力系统谐波分析中的应用研究[D];长沙理工大学;2009年

8 刘子文;改进的粒子群算法在停车场中的应用[D];湘潭大学;2010年

9 余勇;我国建设工程招投标管理机制研究[D];湘潭大学;2010年

10 盛大宁;IMRT逆向计划中的混合多目标梯度算法研究[D];合肥工业大学;2010年

，

本文编号：680207