Design And Analysis Of Predictive Scheduling Algorithms For Minimizing Total Completion Time Problem

Performance analysis of scheduling algorithms has attracted much attention of scholars for its great influence of improving production efficiency in the practical manufacture. Predictive scheduling algorithms, which fully utilize the task information during the producing process, can surely obtain more efficient schedules than online algorithms which only consider the current information. Comparing with offline algorithms which must know all the information in advance, predictive algorithms are more flexible to the information constraints in the producing environment. However, the research results about the performance analysis of predictive scheduling algorithms so far are still quite scarce.Then this dissertation mainly refers the measures in the performance analysis of online scheduling algorithms, and develops a new analysis method of instance transformation as well, to investigate the design and performance analysis of predictive scheduling algorithms for the minimizing total completion time problems. First, we obtain the competitive ratio lower bound of predictive scheduling algorithms for problem 1|r_j|∑C_j, by means of dividing the algorithms set and constructing the corresponding extreme instances. Afterward, we design three single-step predictive scheduling algorithms respectively for 1|r_j|∑C_j and P |r_j|∑C_j problem. From our analysis results which focus on both competitive ratio and average performance ratio, we find that our algorithms outperform the online ones.Summarily, the main research work of this dissertation lies on the aspects as follow:1) Two single-step predictive scheduling algorithms are designed for 1|r_j|∑C_j problem by modifying the online algorithm D-SPT and better performance is obtained.2) This dissertation raises the thought of instance transformation to solve the competitive ratio, and applies it in the solution of competitive ratio of algorithm P-SPT1 with great success. It's an important theoretical contribution of this dissertation.3) The competitive ratio lower bound of predictive scheduling algorithms for problem 1|r_j|∑C_jis obtained, by means of dividing the algorithms set and constructing the corresponding extreme instances. This result describes the performance limit of predictive scheduling algorithms with the predictive step.4) A single-step predictive scheduling algorithm for the more complicated P |r_j|∑C_j problem is designed by referring the two level schedule structure of online algorithm OMPR and utilizing the known P-SPT1 rule. And it also outperforms to OMPR.5) This dissertation also tries to extend the instance transformation method into the solution of competitive ratio of P-SPT2 and P-PSA, but some difficulties are faced. Here we describe the difficulties in the actual derivation in detail and present some potential thoughts to conquer them. This part of work is helpful for the further research in the future.