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

• 作 者: 喻凤
• 出 处: 浙江理工大学
• 发表日期: 2004年期
• 关键词: 在线排序 服务等级 最坏情况界 总完工时间 最大完工时间

本文主要研究两类平行机在线排序问题：第一类是带服务等级约束的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。第四章总结全文并提出相关问题进一步的研究方向。