论文部分内容阅读
本文研究了两类排序问题,一类是同型机上可中断半在线排序问题,一类是同类机上的在线排序问题.并且对这两类问题都给出了最优的(半)在线算法.全文共分为三章.
第一章是绪论部分,主要介绍排序问题相关的一些概念和预备知识.第二章主要研究了m台同型机上已知总和的可中断半在线排序问题.目标是极小化最大的机器完工时间(Cmax)和极大化最小的机器完工时间(Cmin).对于Cmax目标,给出了一个最优的半在线算法,其竞争比为1.对于Cmin目标,当m>2时,证明了任何半在线算法的竞争比至少为2m-3/m-1,并且对于m=2,3的情形分别给出了最优的半在线算法.
第三章主要研究了两台同类机上的在线排序问题,目标函数为极小化最大工件开工时间.首先证明了问题的下界为1+s,然后证明了贪婪(Greedy)算法的上界为1+s,从而是最优的在线算法.这里s是两台机器的速度比.