在线排序和批排序问题研究

发布时间：2020-07-21 10:28

【摘要】：排序问题是一类重要的组合优化问题,随着实际应用和理论研究的不断深入,产生了各种不同的排序问题模型.本文主要研究经典平行机在线、半在线排序问题和单台机上的批排序问题,侧重于不同模型下近似算法的设计以及最坏情况分析.本文共分为五章.第一章是绪论,主要介绍了组合优化问题、排序问题、算法及计算复杂性、在线问题的基本概念,列举了本文的主要成果.第二章和第三章研究经典的同型机以极小化工件的最大完工时间为目标的在线排序问题.由目前在线算法证明过程中对最优解最大完工时间的估计方式的局限性,引入了伪下界的概念.对于任意的机器数m,给出了该问题的伪下界和一个新的算法.机器台数在4至11之间时,算法是伪最优的,即其竞争比等于伪下界.其中机器台数在7至11之间的伪最优算法为首次得到.第四章研究已知工件总加工时间的两台同型机以极小化工件的最大完工时间为目标的半在线排序问题.给出了一个随机算法,并且证明了它的竞争比不超过5/4.该值小于该问题的确定性下界4/3.第五章研究工件大小不同,但加工时间相同,以极小化工件总完工时间为目标的批排序问题.证明了FFD算法的最坏情况比无界,FFI算法的最坏情况比在109/82和3/2之间.此外,还引入了两个启发式算法,并进行了数值试验和分析.
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O223
【图文】：

由于对于某些实例，通过不同算法给出的排序可能相等，这些百分比的和可能大逡逑于１．逡逑由表５．３和图５．１，图５．２，我们发现算法的优劣和工件大小所在的区间密切相逡逑关．５７？的表现要比ＦＦ域ＦＦＤ的差．很少有实例使得５７？的表现能比ＦＦ１或ＦＦＤ更逡逑好．当工件的大小更接近的时候，ＣＯＭ会明显的比其他算法更好．对于这三组同逡逑样长度的区间而言，ｃｏｍ在区间的表现要比区间更好，区间比逡逑区间好，区间比区间ｈｉ］好．然而，我们对于平均情况界的估计基于逡逑最优解的下界ｒＧ．我们并不知道这种现象是否是由ｒｃｉ和７Ｙ７＊之间的差异产生逡逑的．逡逑关于ＦＦＩ与ＦＦＤ之间的比较也十分有趣，这和最优解下界的选取无关．注意逡逑到即使所有的工件都被限制在很小的情况下，ＦＦＤ仍是无界的，而ＦＨ的最坏情逡逑况比不超过１．５．就这七个区间而言，ＦＦＩ在区间［０，幻和［Ｏ，＾，也就是没有工件逡逑大小超过！的区间中表现明显要优于ＦＦＤ．另一方面，ＦＦＤ在三个以ＬＳ邋＝邋｜作为逡逑左端点的区间

—＃－ＦＦＩ邋－？－ＦＦ0邋＇ＳＲ邋——ＣＯＭ逡逑图５．１：不同ｎ的平均竞争比逡逑—个区间，ＦＦＩ的平均竞争比总是增加．ＦＦＤ的平均竞争比则是在［０，１］增加，其余逡逑的减少．在这两个因素的影响下，区间［０，引的性质更是十分有趣，ＦＦＩ在ｎ邋＝邋２０逡逑时优于ＦＦＤ，而在其他情况下均不如ＦＦＤ邋．逡逑

【相似文献】

相关期刊论文 前10条

1 韩飞;;高中数学一道数列典型题解法的探究[J];数学学习与研究;2016年23期

2 豆俊梅;孙彩贤;;单机排序问题的研究[J];数学学习与研究;2017年24期

3 胡觉亮;杨佳雯;苏晓彤;董建明;;机器带周期性维护时段的加工与运输协同排序问题[J];浙江理工大学学报(自然科学版);2016年06期

4 仲维亚;马晓茹;;带有运输且加工具有灵活性的无等待流水作业排序问题[J];运筹学学报;2016年04期

5 隋楠;罗成新;;具有维护活动及公共工期的加工时间依赖资源的单机排序问题[J];沈阳航空航天大学学报;2016年06期

6 林浩;何程;;关于工期分配与加权误工数的双指标排序问题（英文）[J];工程数学学报;2017年01期

7 赵传立;张蕾;;带有交货期窗口和加工时间可控的排序问题[J];沈阳师范大学学报(自然科学版);2016年04期

8 王申重;杜海龙;;具有学习效应和遗忘效应的单机排序问题研究[J];枣庄学院学报;2017年02期

9 陈蕾;张安;陈永;陈光亭;;资源定时投放的单机排序问题[J];杭州电子科技大学学报(自然科学版);2017年02期

10 窦文卿;范静;;一类资源费用可变的平行机排序问题[J];上海第二工业大学学报;2017年02期

相关会议论文 前10条

1 张莲珠;;关于六角链的极值和排序问题的一些结果[A];中国运筹学会第六届学术交流会论文集（上卷）[C];2000年

2 吕绪华;杨汉兴;;求解装配式排序问题的归并算法及其性能比研究[A];中国运筹学会第六届学术交流会论文集（下卷）[C];2000年

3 周支立;李怀祖;;有重叠区域的两抓钩周期性排序问题的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孙世杰;陈跃;;参数可控的排序问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

5 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

6 张玉忠;;分批排序问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

7 胡荣;吕绪华;;3TMF排序问题的计算复杂性及分支定界法[A];中国运筹学会第八届学术交流会论文集[C];2006年

8 柏孟卓;唐国春;;加工时间可控的同时加工排序问题[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

9 樊保强;;带仓储约束的准时排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

10 吴翠连;;有尺寸的单机分批排序问题的近似算法[A];中国企业运筹学[2011（1）][C];2011年

相关重要报纸文章 前3条

1 杨文波;浅谈方位词“东、西、南、北”的词语排序问题[N];语言文字周报;2018年

2 山东 赵玉勇;小博士编程[N];电脑报;2004年

3 何靖;全国计算机应用技术证书考试（NIT）[N];中国电脑教育报;2003年

相关博士学位论文 前10条

1 李融奇;在线排序和批排序问题研究[D];浙江大学;2018年

2 沈佳煜;不确定情形下若干排序问题的研究[D];南京理工大学;2017年

3 高园;新型排序问题的计算复杂性研究[D];郑州大学;2018年

4 殷娜;依赖于资源分配的排序问题研究[D];上海大学;2015年

5 李好好;若干排序问题研究[D];浙江大学;2014年

6 王吉波;工件加工时间可变的现代排序问题[D];大连理工大学;2005年

7 罗润梓;平行机半在线排序问题[D];上海大学;2005年

8 季敏;当代工业中的若干排序问题研究[D];浙江大学;2006年

9 叶德仕;通讯网络中排序问题的若干在线和高性能算法[D];浙江大学;2005年

10 李文华;关于分批排序问题的研究[D];郑州大学;2006年

相关硕士学位论文 前10条

1 潘婷婷;带资源、学习效应、恶化效应、维护活动和工期窗口的排序问题的研究[D];苏州大学;2018年

2 张洁;按外包工件个数不同折扣率的单机排序问题[D];郑州大学;2018年

3 周松涛;带约束的单机双代理排序问题[D];郑州大学;2018年

4 朱月娟;限选机器上的在线排序问题[D];郑州大学;2018年

5 孙振霞;机器具有不可用区间且工件可拒绝的排序问题[D];郑州大学;2018年

6 陈耀宁;与资源有关的多次维修和加工时间可变的排序问题研究[D];重庆师范大学;2018年

7 孟凡晓;基于退化效应的可拒绝分批排序问题[D];曲阜师范大学;2018年

8 王穆清;同类机上的在线分批排序问题[D];曲阜师范大学;2018年

9 王晓连;模糊数空间上的排序问题[D];杭州电子科技大学;2018年

10 李丹;两类资源受限的排序问题研究[D];杭州电子科技大学;2018年

本文编号：2764290