Online Scheduling On Uniform Machines To Minimize Makespan

In the off-line scheduling research, the attributes of machines vary diversely. The main models are identical parallel machines、 uniform parallel machines and unrelated parallel machines. Identical parallel machines mean the speeds of machines are identical and the processing time of job is 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. Unrelated parallel machines have the job-dependent speeds.In this paper, we study the problems of online scheduling on uniform machines. All information of jobs is unknown before they arrive. Online scheduling can be divided into online-over-time and online-over-list. If jobs have its release time which is irrelevant to each other, the way is called online-over-time. And if jobs arrive one by one and the next job cannot be released until the current job has been scheduled, the way is called online-over-list. Once a job arrives, its all the information becomes known.In the second chapter we consider online scheduling on m uniform unbounded parallel-batch machines. The objective is to minimize makespan, i.e. Qm|online,p-batch,b= ∞,Pj=|Cmax(m> 2). Here online scheduling means online-over-time. The speed of the first m－1 machines is 1 and the last is v(0<v<1). Jobs with unit length are considered. 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 capacity of batch, parallel-batch can be divided into the bounded model and the unbounded model. We consider unbounded version and provide a best possible (1+α)m=2+α and α2 satisfies (1+α)(m+1)= (1/v-1)(1+α)(m-1)+2+a.In the third chapter we consider the online scheduling of a set of jobs on two uniform machines with the makespan as objective function, i.e. Q2|online-list,g= 2, pmtnlCmax-Jobs arrive over list. The jobs are not known a priori:the next job becomes known only when the current job has already been scheduled. The speed of the first machine is 1 and the second is v. Associated with each job Jj (j= 1, ..., n) is its processing time Pj and a hierarchy gj. If gj= 1, job Jj, can only be processed by machine M1 with speed 1. If gj= 2, both machines can process it. Furthermore, the practical time to process job Jj which is arranged to M equals to its normal processing time pj. The time required to process job Jj which is scheduled on machine M2 with speed v (0< v<∞) is pj/v. At any time, jobs can not overlap. Each machine can handle no more than one job and each job can be processed by one machine at most. Preemption is permitted, a job may be divided into a few pieces and probably assigned to different machines in non-overlapping time slots. We assume that in this chapter, idle time is not allowed to be introduced before the last job is completed. We prove that when v< 1, the lower bound of the competitive rario is 1+v/v+1, when v≤1 and v3+v2≥1, we establish an online algorithm with 1+1/v2+v;when v≥1, we give the lower bound of the competitive ratio is 1+1/v+1 and the competitive ratio of the algorithm is 1+v/v+1.