The Analysis Of Algorithm Performance Ratio For Semi-online Scheduling Problems On Parallel Machines

In this thesis,we mainly consider semi-online scheduling model of design-ing algorithm and analyzing the performance ratio of the algorithm.The thesis is divided into four chapters.The first chapter is the introduction.Firstly,the definition of the combinatorial optimization problem and its significance are in-troduced.Then,the typical sorting problem in the combinatorial optimization problem is described in terms of background,classification and research status.Finally,the concept and basic idea of the approximation algorithm are intro-duced.Besides,we introduce Pm and the S-shape algorithm we constructed in this paper.The fourth chapter is a summary of the whole article,and puts forward the possible direction of future research work.The main content will be detailed in Chapters 2 and 3 respectively.Chapter 2:we construct an algorithm named S-shape algorithm for the model which is described as follows:for job list L,the processing times of jobs are non-increasing and similar lengths in[1,r](r ? 1).We show that the tight worst case performance ratio of the algorithm for two parallel machines isOn the basis of Wei-Ping Liu,Jeffrey B.Sidney,Andre van Vlief's model,we add a new constraint that jobs with similar lengths in[1,r](r? 1)and prove that the worst performance ratio of P(2)algorithm is not change.But we get the better results by limiting the processing times of jobs in the S-shape algorithm.Chapter 3:We prove that for any job list L,the release time of each job is zero and the processing times of jobs are non-increasing,the worst performance ratio of the Pm algorithm isThis chapter mainly makes relevant corrections to the literature[11],and optimizes the worst performance ratio of the algorithm Pm to get more accurate results.