若干代理排序问题的近似算法研究

发布时间：2017-04-16 16:22

  本文关键词：若干代理排序问题的近似算法研究，由笔耕文化传播整理发布。

【摘要】：代理排序问题是近十年来发展的一类新兴排序问题,与传统排序问题不同,代理排序问题中的工件分别属于两个或多个不同的代理人,所有代理人有各自的目标,但共享加工资源。这类排序问题有许多实际应用,所以受到越来越多研究者的关注。本文主要考虑一些代理排序问题的复杂性,近似算法以及在线算法,并分析算法的近似比或竞争比。 第一章主要介绍了组合优化问题和排序问题的一些概念,以及代理排序问题的研究现状。 第二章中,考虑同速机上两代理排序问题的两个模型。在这两个模型中,其目标分别为极小化代理A的时间表长和总完工时间和,同时代理B的时间表长不超过一个目标值。证明了这两个问题是NP-难的,并且可以在拟多项式时间内解决。进一步,分别对这两个问题设计了完全多项式时间近似方案。 在第三章中,进一步研究了第二章中的第一个模型,即极小化代理A的时间表长同时代理B的时间表长不超过一个目标值,并且设计了两个近似算法。当机器台数m任意时,设计了一个O(n)的算法,其性能比为2-1/m,即由该算法给出的代理A的时间表长不超过最优值的2-1/m倍,同时代理B的时间表长不超过阀值的2-1/m倍,并且证明了这个比值证明是紧的。进一步,当m=2时,设计了一个O(n log n)算法,其性能比为(1+√17)/4≈1.28,小于3/2,并且该比值是弱紧的。 第四章研究了一个两台同速机上的多代理排序问题,每个代理的目标为极小化时间表长。对于该问题,设计了一个(1+1/6,2+1/6,…,g+1/6)-近似算法。该算法可以得到一个时间表,它的第i个完成的代理的时间表长与其最小时间表长的比不超过i+1/6,并且证明了这个性能比向量是紧的。 第五章考虑了一个单机在线两代理排序问题,两个代理的工件适时到达,其目标为极小化两代理的时间表长的线性组合,即CmaxA+θCmaxB,其中θ≥1。对于该问题,设计了一个竞争比为1+(2θ+θ2)/(2+2θ+θ2)在线算法。对于θ≤(1+√5)/2乎的特殊情形,设计了一个最好可能的在线算法。 最后,在第六章对本文做了总结和展望。
【关键词】：代理排序 近似算法 性能比 在线算法 竞争比
【学位授予单位】：华东理工大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要5-6
• Abstract6-10
• 第1章 绪论10-24
• 1.1 组合最优化10
• 1.2 算法和计算复杂性10-14
• 1.3 排序问题简介14-17
• 1.4 文献综述17-22
• 1.4.1 单机两代理排序问题18-21
• 1.4.2 平行机与车间作业两代理排序问题21-22
• 1.4.3 多代理排序问题22
• 1.5 论文概述22
• 1.6 文献注记22-24
• 第2章 平行机上两代理排序问题的近似方案24-34
• 2.1 引言24
• 2.2 两代理的目标都为极小化时间表长的模型24-29
• 2.2.1 动态规划25-26
• 2.2.2 完全多项式时间近似方案26-29
• 2.3 两代理的目标分别为极小化总完工时间和时间表长的模型29-33
• 2.3.1 动态规划30-31
• 2.3.2 完全多项式时间近似方案31-33
• 2.4 结论与讨论33-34
• 第3章 极小化时间表长的平行机上两代理排序问题的近似算法34-50
• 3.1 引言34
• 3.2 准备工作34-35
• 3.3 一般情形的近似算法35-36
• 3.4 m=2情形下的近似算法36-49
• 3.5 结论与讨论49-50
• 第4章 两台机上的多代理排序问题的近似算法50-62
• 4.1 引言50
• 4.2 近似算法50-53
• 4.3 性能分析53-61
• 4.4 结论与讨论61-62
• 第5章 带到达时间的单机两代理排序问题的在线算法62-92
• 5.1 引言62
• 5.2 一般情形的在线算法62-76
• 5.3 θ≤((?)+1)/2情形下最好可能的在线算法76-92
• 第6章 总结与展望92-94
• 参考文献94-102
• 致谢102-104
• 博士期间完成论文104

【相似文献】

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

1 周泓,张惠民;求解多目标作业排序问题的遗传算法[J];系统工程理论与实践;2001年08期

2 周泓,姬彬;求解作业排序问题的通用混合遗传算法研究[J];系统工程理论与实践;2001年12期

3 陈德伍,张 峰;一类新的可控排序问题(英文)[J];运筹学学报;2001年04期

4 张瑞,刘国珍;单机排序问题最优解方法[J];聊城师院学报(自然科学版);2001年02期

5 黎群;单台机器多目标作业排序问题的探讨[J];系统工程理论方法应用;2001年02期

6 方保昒,徐汉忠;用单亲遗传算法解具有窗口式交货期的多机加工排序问题[J];系统工程理论方法应用;2001年04期

7 宋政芳,孙世杰,吴春燕;一个超前有奖迟后受罚的排序问题(英文)[J];运筹学学报;2002年04期

8 赵传立,唐恒永;具有相关调整时间的排序问题[J];沈阳师范学院学报(自然科学版);2002年01期

9 郑自途;关于"三台以上机床作业排序问题"的算法[J];天津理工学院学报;2002年04期

10 张玉忠,苗翠霞;复制法及其在分批排序问题中的应用[J];曲阜师范大学学报(自然科学版);2004年02期

中国重要会议论文全文数据库 前10条

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

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 谭万达;;二元对比排序中的最少逆序原理[A];中国系统工程学会模糊数学与模糊系统委员会第五届年会论文选集[C];1990年

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

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

10 陈荣军;唐国春;;自由作业环境下的供应链排序问题[A];中国运筹学会第九届学术交流会论文集[C];2008年

中国重要报纸全文数据库 前1条

1 山东 赵玉勇;数组，你的规律机器[N];电脑报;2004年

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

1 仲维亚;供应链管理中的若干排序问题研究[D];浙江大学;2008年

2 尹晓;基因组重组排序问题的算法研究[D];山东大学;2010年

3 余炜;若干网络排序问题的算法和复杂性研究[D];华东理工大学;2010年

4 张安;带服务等级的在线排序问题及相关问题研究[D];浙江大学;2009年

5 郑睿;钢铁生产中的批处理机作业排序问题算法研究[D];复旦大学;2009年

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

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

8 丁国生;多代理竞争排序问题的研究[D];上海大学;2009年

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

10 王成飞;几类新型在线分批排序问题[D];曲阜师范大学;2011年

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

1 董柳毅;与误工有关的多目标排序问题[D];重庆师范大学;2009年

2 王迅娣;成组加工排序和供应链在线排序问题[D];曲阜师范大学;2010年

3 王洁明;有关代理竞争排序问题的研究[D];华东理工大学;2011年

4 刘丽丽;分批排序问题[D];曲阜师范大学;2000年

5 鄢楚楠;2，4-逆序变换的置换排序问题[D];浙江大学;2006年

6 张兵权;单位加工时间的公共时间窗单机分组排序问题[D];浙江大学;2006年

7 姜冠成;分批排序问题和资源约束排序问题[D];苏州大学;2005年

8 胡荣;一类分装式排序问题的计算方法和计算复杂性研究[D];武汉科技大学;2006年

9 马蕾;带传递时间的通信模型中的树约束排序问题[D];兰州大学;2007年

10 王小明;不允许等待的混合流水两车间排序问题[D];清华大学;2002年

  本文关键词：若干代理排序问题的近似算法研究，，由笔耕文化传播整理发布。

本文编号：311208