Online Scheduling On Uniform Machines To Minimize Makespan

Identical parallel machines mean the speeds of machines are identical and the pro-cessing time of job only relates to itself. Uniform parallel machines are defined as parallel machines which have different speeds. In this case, the actual processing time of a job is closely related to the speed of machine on which it is scheduled.In the second chapter we discuss online scheduling on m uniform machines with un-bounded parallel-batch and jobs with unit length. The objective is to minimize makespan,i.e., QM|online,p-batch, b=?,pj=1|Cmax (m?2). The speed of the first m-a machines is 1 and the following m - a machines is v (0 < v < 1). Online scheduling means that jobs have their release times which are irrelevant to each other and all the information of a job is unknown before the job arrives. Parallel-batch shows that one machine can process b jobs at the same time. The processing time of a batch equals to the longest processing time of jobs which were scheduled in it. According to the limit on the sizes of each batch, there are two distinct models. One is the restrictive model in which the bound b on each batch size is effective, i.e. b < n. The other is the unrestrictive model in which there is effectively on limit on the size of batches, i.e. b > n. In this chapter we consider unbounded version and provide a best possible online algorithm of competitive ratio where a is the positive root of equation (1 + ?)?+1 = 2 + ?, and ? is the positive root of equation (1 + ?)(m+1)=(1/v-1)1+?/?((1 + ?)m-?-1) + 2 + ?.In the third chapter, we study online scheduling on two uniform machines with bound-ed parallel-batch to minimize the makespan, i.e., Q2|online, p-batch,2 ? b < n,pj=1|Cmax where the speed of M1 is 1 and the speed of M2 is v (0 < v < 1). Jobs have its release time which is irrelevant to each other and all the information of a job is unknown before the job arrives. Here all the jobs Jj with the processing time pj = 1, while the speed of the two machines is not the same. Furthermore, the practical time to process job Jj which is arranged to M1 equals to its normal processing time pj = 1, and the practical time to process job Jj which is scheduled on machine M2 with speed v (0 < v < 1) is pj/v=1/v We proved the lower bound of the competitive rario where, ?1 is the positive root of equation ?2/1+?1=1,?2 is the positive root of equation?2/2+2?2=1 and a3 is the positive root of equation ?2/3+(1+?3) 1/v = 2. When 0 <v < 2,we provide a best possible online algorithm with competitive ratio is 1 + ?1, when 1/2?v< 1,we establish an online algorithm with the competitive ratio is 1 +?, where ? is the positive root of equation (1 + ?)2 = 2 + ?.