【作者】 周昊；

【导师】 何勇；

【作者基本信息】 浙江大学 ， 运筹学与控制论， 2005， 硕士

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

【Abstract】 This paper mainly study two scheduling problems. One is preemptive semi-online scheduling on identical parallel machines, the other is online scheduling on uniform machines. We present optimal algorithms for these two problems. The paper consists of three chapters.The first chapter give some introductions and prelimilaries for scheduling problems.The second chapter investigates the preemptive semi-online scheduling problem on m identical parallel machines, where the total size of all jobs is known in advance. The goal is to minimize the maximum machine completion time and to maximize the minimum machine completion time. For the first objective, we present an optimal semi-online algorithm with competitive ratio 1. For the second objective, we show that the competitive ratio of any semi-online algorithm is at least (2m-3)/(m-1) for any m > 2 and present optimal semi-online algorithms for m = 2,3.The third chapter considers online scheduling on two uniform machines with the objective of minimizing the maximum job starting time. We present an optimal algorithm for any s ≥ 1, where s is the machine speed ratio.更多还原