The Analysis Of Algorithm Performance Ratio For Two Semi-online Scheduling Problems

This thesis mainly consists of two parts in which the performance ratios of two algorithms for two kinds of semi-online models respectively are analyzed.In the first part:He and Zhang[12] proposed a semi-online parallel schedul-ing model in which a scheduler should assign a job list L of jobs with similar lengths in [1,r](r≥1) on two parallel machines in 1999. They addressed that the worst performance ratio of LS algorithm for the model is In this thesis, we add a new constraint that the release time of jobs are non-decreasing. Compared with the previous model, our model is more complicated. We should consider more factors in the analysis of performance ratio. We give that the tight worst performance ratio of LS algorithm is We also show that the LS algorithm is the best online algorithm for this model. The detailed proof is included in chapter 2.The second part:Wei-Ping Liu, Jeffrey B.Sidney, Andre van Vliet had proposed a model in 1996 ([24]). The model is described as follows:for any job list L, the release time of each job is zero and the processing times of jobs are non-increasing. They designed an algorithm named Pm and showed that the worst performance ratio of the algorithm isIn this thesis, we add a new constraint that the release times of jobs are non-decreasing and show that the worst performance ratio of Pm algorithm is:Although the result is bigger than before, the application scope is more extensive. The detailed proof is given in chapter 3.In Chapter 1 we introduce some basic knowledge about combinatorial op-timization problem、approximation algorithms and the progress of scheduling problem.In Chapter 4 we summarize the whole thesis and give some suggestions for the future work.