两类平行机排序问题的在线算法

发布时间：2017-08-13 15:26

  本文关键词：两类平行机排序问题的在线算法

  更多相关文章： 在线排序 服务等级 最坏情况界 总完工时间 最大完工时间

【摘要】：本文主要研究两类平行机在线排序问题：第一类是带服务等级约束的m台机在线排序，目标是极小化总完工时间。第二类是带单台服务器的两台机在线排序，目标是极小化最大完工时间。 全文共分四章。 第一章简要的介绍排序的基本理论。 第二章主要研究带两个服务等级的m台平行机在线排序，其中加工的工件均是单位长度。本章分两种情形，目标均是极小化总完工时间。情形一：机器为m台，其中第1台机器服务等级为1，剩余的m1台的等级为2，本章提出一个比贪婪算法更好的近似算法，并证明其竞争比为1+√2(m1)(16m+19)(m1)2+1+3m2；情形二：考虑更一般的情况，机器为m台，其中前k台服务等级为1，剩余m k台机器的服务等级为2，我们证明其贪婪算法的竞争比为1+√2k(m k)m(4km3k2+k)。最后，我们对问题的后续研究做出一些预测。 第三章主要研究带一台服务器的两台平行机在线排序，具体分两种情形考虑，目标均是极小化最大完工时间。第一种，同时考虑装载、加工和卸载的情形，本章提出一个竞争比为5/3的在线算法；第二，对只考虑装载和加工的情形，，我们首先证明这个问题的贪婪算法的竞争比至少是8/5，接下来提出一个竞争比为11/7的在线算法。最后证明这两个问题的下界均至少为3/2。此外，对第一种情形，本章还说明当满足某个特殊限制条件时，它的下界至少为8/5。 第四章总结全文并提出相关问题进一步的研究方向。
【关键词】：在线排序 服务等级 最坏情况界 总完工时间 最大完工时间
【学位授予单位】：浙江理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要4-5
• Abstract5-7
• 第1章 绪论7-11
• 1.1 排序问题概述7-8
• 1.2 在线算法8-9
• 1.3 两类平行机排序问题在线排序模型9
• 1.4 论文结构9-11
• 第2章 带服务等级的m台平行机排序的在线算法11-22
• 2.1 引言11-12
• 2.2 相关知识12-13
• 2.3 问题P_m|1,m-1,Gos|∑C_j的在线算法13-17
• 2.4 问题P_m|k,m-k,Gos|∑C_j的贪婪算法17-20
• 2.5 小结20-22
• 第3章 带服务器的2台平行机排序的在线算法22-35
• 3.1 引言22-23
• 3.2 相关知识23-24
• 3.3 问题P_2,S_1|s_j=t_j=1|C_(max)的在线算法24-29
• 3.4 问题P_2,S_1|s_j=1|C_(max)的在线算法29-32
• 3.5 问题P_1和P_2的下界32-34
• 3.6 小结34-35
• 第4章 总结与展望35-36
• 参考文献36-42
• 附录42-43
• 致谢43

【参考文献】

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

1 蒋义伟;何勇;唐春梅;;Optimal online algorithms for scheduling on two identical machines under a grade of service[J];Journal of Zhejiang University Science A(Science in Engineering);2006年03期

本文编号：668000