Online-list Scheduling On A Bounded Batch Machine

Online-list scheduling is an important modern scheduling. We study the problem of online-list scheduling jobs on a batch machine of finite capacity with the objective of minimizing the makespan. So called online-list scheduling on a bounded batch machine, the jobs are presented one by one, and we have to assign each job upon arrival to a scheduled batch before we see the next one. Each batch can accommodate up to b jobs. The paper is organized as follows.In chapter 1, we introduce some definitions, notations and basic information about scheduling.In chapter 2, we consider the problem of online-list scheduling jobs on a batch ma-chine of capacity 2 with the objective of minimizing the makespan, using the 3-parameter notation convention of Graham et al. (1979), the problem is denoted by 1|online-list, p-batch, b=2|Cmax. For the problem, we present a lower bound 1+α, where a is a positive solution of the equation a(1+α)2=1 in (1/2 - 1,1/2). And we give an algorithm with competitive ratio 1/5+1/2. Then, we design an on-line algorithm which may be better for the further research.In chapter 3, we consider the problem of online-list scheduling jobs on a batch ma-chine of capacity 3 with the objective of minimizing the makespan, using the 3-parameter notation convention of Graham et al. (1979), the problem is denoted by 1|online-list, p-batch, b=3|Cmax.For the problem, we present a lower bound 1+α', whereα' is a positive solution of the equation (1+α')(1+(α')2)=2 in (1/2,1/5-1/2)-And we give an algorithm with competitive ratio 2.Finally, we summarize the dissertation and put forward some problems which we will consider further.