The Scheduling Problem For Job With Similar Processing Times

This paper mainly discusses the off-line scheduling problem for jobs with similar processing time on parallel machines.There are n independent jobs J₁,J₂,...,J_n,which are processed on m-processer M₁,M₂,...,M_m with the same performance,each job can be completed only on one of the machines and there is no sequential dependency among J₁,J₂,...,J_n,and the processing time of J_i is p_i,Assuming p₁≥P₂≥...≥P_n,LPT indicates that n jobs shall be processed on M₁,M₂,...,M_n as the following methods:the job with least index,which has not yet been processed,is sent to process on the earliest available machine,we usually name this processing method as LPT,whose objective function is to minimize the maximum completion time of all machines.LPT requires the job to have similar processing time,that is,the job sequence L={J₁,J₂,...,J_n}satisfies （?）,this paper proves the worst performance ratio under the LPT algorithm with the number of machines is 3 or m.In Chapter 1,the paper introduce some preliminary knowledge and basic concept,including Combinatorial OPTimization problem,Model description of scheduling problem,Brief introduction of research background,Algorithms for combinatorial OPTimization problem,these preliminary knowledge and basic concepts enable readers to understand the research field of the text better.In Chapter 2 and 3 of the paper respectively prove the worst performance ratio of LPT algorithm for 3 or m,when the job have similar processing time and the processing time is not increasing.In Chapter 2 and 3,the conclusion is based on of H.kellerer,which obtained the worst performance ratio of m parallel machines of the same type under LPT algorithm.But what he proved is not the tight bound of the complete interval.In this paper,the number of machines is firstly specified,that is,the number of machines is 3,then the paper finds out the worst performance ratio and the minimum tight bound of all intervals,and then analyze m parallel machines of the same type,but the result is only the tight bound of some intervals,However,the range of tight bound for m machines in this paper is larger than that of H.kellerer.In Chapter 4,the paper summarizes the whole thesis and put forward some suggestions for future work.