The Research And Performance Analysis Of Predictive Scheduling Algorithms

With the economy globalization, today manufacturers are facing more pressure than ever. They have higher requirement on production scheduling, which means an optimized assignment of rare resources. A well-planned schedule can raise efficiency, save cost and thus help to increase the profit of the company.Most scheduling problems are NP-hard. A general way to solve these problems is to design a heuristic algorithm that can give good result at acceptable computation cost. In the past most researches focused on off-line algorithms and on-line algorithms, with little consideration of such condition that future information can be partly predicted. In this dissertation, we introduce the essence of predictive control into scheduling problems. We propose predictive scheduling algorithms for three typical problems and study the improvement of performance. In summary, the main research work of this dissertation lies in three aspects as follows:For minimizing total weighted completion time for single machine problem with release time, we design a predictive scheduling algorithm. We also prove that the lower bound of predictive scheduling algorithms is 2, which is the same as the competitive ratio of on-line algorithms. This suggests predictive scheduling algorithms works the same as on-line algorithms in performance guarantee. For more general instances, we simulate a lot and show that the predictive scheduling algorithm is better than on-line algorithms.For minimizing makespan on identical parallel machine problem with release dates, we design a predictive scheduling algorithm. By simulation we find that in worst cases its performance ratio is smaller than the best on-line algorithms. This suggests it might outperform on-line algorithms in performance guarantee. For general cases, the predictive scheduling algorithm is better than on-line ones as well.For one kind of job shop problem with inaccurate information, we design a predictive scheduling algorithm. In predictive window, shifting bottleneck method is taken to solve the sub-problem. Outside the predictive window, we use general rule as imaginative scheduling. Compared with original algorithm, the prediction and rolling strategy help to improve performance.