| 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. |
PDF Full Text Request