Online Scheduling On Parallel Batch Machines To Minimize The Maximum Flow-time

Batch scheduling is an important problem of scheduling research. There are m ma-chines in the parallel machine online scheduling. The jobs come one by one, before the jobs coming we know nothing or little of the information of the jobs. We need to schedule the jobs that have been come, that is putting a job on which machine and which jobs should be scheduled as a batch. A batch machine can schedule some jobs simultaneously on some machine and the jobs that are in a same batch have the same starting times and finishing times. There are two different kinds of the capacity of a batch, one is that a batch can only schedule finite number of jobs simultaneously, and the other is that a batch can schedule infinite number of jobs simultaneously. In this paper, we mainly study the parallel batch scheduling with the objective function to minimize the maximum flowtime.This paper is organized as followss:In chapter1, we introduce some definitions, notations and basic information about scheduling.In chapter2, we consider the problem of online scheduling where the jobs coming with the processing time nonincreasing. There is only one machine with the objective of minimize the maximum flowtime. Using the3-field notation of Graham et al.(1979), the problem is denoted by l|online, p-batch, b<n,p1≥p2≥…≥pn|Fmax. For the problem, we present a lower bound1+α. where a is a positive solution of the equation α(1+α)=1. And we give an algorithm with competitive ratio1+α, and the algorithm is the best possible. For the problem,1|online, p-batch, b=n.p1≥p2≥…≥pn|Fmax, we present a lower bound1+β, where β=(?)-1. And we give an algorithm with competitive ratio1+β, and the algorithm is the best possible. In chapter3, we consider the parallel machine scheduling that all the jobs have the same processing times, using the3-field notation of Graham et al.(1979), the problem is denoted by Pm|online,p-batch, b<n.pj=p|Fmax. For the problem, we present a lower bound1+α, where α is a positive solution of the equation α(1+α)=1. And we give an algorithm with competitive ratio1+α, and the algorithm is best possible.In chapter4, we consider the parallel machine scheduling that all the jobs have the same processing times and there are at most two arriving times. Using the3-field notation of Graham et al.(1979), the problem is denoted by Pm|online,p-batch,b<n,pj=p,r1; r2|Fmax, For the problem, we present a lower bound3/2. And we give an algorithm with competitive ratio3/2, and the algorithm is best possible.Finally, we summarize the dissertation and put forward some problems which we will consider further.