Competitive Analysis On Semi-online Scheduling Algorithms For Single-machine Problems

The analysis of competitive ratio on scheduling problems is of great significance in both theory and practice since it is an evaluation and guarantee for the potential risk of an algorithm. Among all kinds of scheduling problems, semi-online scheduling problem is a middle-ground between online and off-line scheduling problems. It fits more closely to the pragmatic world. In recent decades, the research in this area has developed to some extent. Various semi-online scheduling problems and algorithms were investigated. However, the results about the competitive analysis of semi-online algorithms so far are still quite scarce.In this thesis, we present three kinds of semi-online scheduling problems based on the classic online scheduling models, i.e. the single-machine scheduling problem for minimizing total completion time , the single-machine scheduling problem for minimizing total weighted completion time and the single-machine scheduling problem for minimizing total weighted discounted completion time . With some additional information known in advance, we analyze the performance of algorithms by a novel method of instance transformation. We obtain the lower bounds of the three semi-online scheduling problems through the construction of the worst cases, respectively. Accordingly, we know that the competitive ratio of each problem cannot be less than its lower bound. Moreover, we further demonstrate that for with the limitation of the instance space our algorithm outperforms. For the semi-online version of , we figure out one kind of information which does improve the algorithm performance. Afterwards, we design a semi-online algorithm for the semi-online scheduling problem based on and obtain its competitive ratio. For three special cases of such a problem, this algorithm is optimal.Summarily, the main research work of this thesis lies on the aspects as follows:1) The proof of competitive ratio of algorithm P-SPT2 is further developed with the limitation of instance space for the semi-online scheduling problem2) The additional information about future release times and the processing time bounds ? ?pm in ? p j? pmax are introduced into the classic online scheduling problem . It turns out that future release times are invalid information which does not improve the competitive ratio while the processing time bounds are useful information which improves the competitive ratio.3) For the semi-online version based on the traditional scheduling problem , the processing time bounds are introduced. Besides obtaining the lower bound of the semi-online problem, we design a new semi-online algorithm. The competitive ratio of such an algorithm is obtained by the instance transformation. Also, this algorithm is optimal for three special cases of the semi-online scheduling problem.