Online Batch Sorting Problem On Similar Machines

Scheduling,as a branch of the operations research and applied science,has wide practical and applied prospect.Online scheduling is one kind of the most important optimization problem.It is applied in management,commercial manufacture,production manufacture,combined with Mathematics,Management,Computer Science and Algorithms.Which at home and abroad has very important value to study.Online scheduling has much to offer in its vitality and freshness.The combination of which and reality has become close in recent years.There has been a lot of research work about online scheduling during these years.Which is very important to study.In this paper we study the online problem of dynamic job release times on 2 uniform machines subject to minimize the makespan.On uniform machines,the processing time of a job is the processing length of a job divides the speed of the machine it is scheduled,we study the two machines with the speed of one is S times the other one.S ≥ 1.Jobs arrive over time and characteristics of jobs are unknown until their arrival times.Jobs can be processed in a common batch,in a same batch,jobs start at the same time and finish together.A batch processing machine can handle up to B jobs simultaneously.The objective is to minimize the time by which the last job is finished.We study the problem Q2|rj,pj,B=∞,on-line|Cmax the unrestricted model which the capacity of a batch is infinite.Three chapters are included in this thesis.In the first chapter,some notations and definitions and basic background information about the subject are introduced.In chapter 2,we provided an online algorithm of Q2|rj,pj,B=∞,on-lineCmax,with competitive no larger than 2.In chapter 3,we use an adversary to show a lower bound of Q2|rj,pj,B=∞.on—lineCmax,which is no less thanαs+1,when αs2+1+1Sαs-1S=1S,0<αs<1.