Online Scheduling Of Parallel Jobs On Several Problems

This thesis focuses on several online parallel jobs scheduling problems. The scheduling problems studied in the thesis can be described as follows:given a set of machines and a list of jobs arriving one by one, assigning each job to required machines irrevocably and satisfying all constraints such that the measure-Lp norm-is minimized, preemption is not allowed during the schedule.The thesis includes six chapters. In chapter one, we give a detailed introduction of online scheduling and related knowledge of algorithm analysis. Then, we analyze the competitive ratio of LS algorithm for two semi-online models on two identical machines in chapter two. When jobs arrive in non-increasing order of processing time, we show that the competitive ratio of LS algorithm is either p(?)2or4/3, for each distinct case. For the problem with jobs arrive in non-decreasing order of processing time, the behavior of LS algorithm is similar to the previous one, it also has two cases, the competitive ratio of the first one is p(?)(2p+3p)/2p+1, the other one is4/3, both of them are tight bound.In chapter three, we consider the lower bound for online scheduling of parallel jobs on two identical machines. We show that the lower bound is at least4/3by constructing an instance.Next, we generalize the result to m identical machines in chapter four. We proposed a semi-online algorithm with competitive ratio at most12for known longest process time,At last we consider online scheduling of parallel jobs on m identical machines. First, we show that LS algorithm has competitive ratio m and then an improved on-line algorithm with competitive ratio at most16is proposed in chapter five. In last chapter, we give a summary for the thesis, and give some suggestions for further researches.