An algorithm for thermal unit maintenance scheduling through combined use of GA SA and TS

This paper describes a method of solving a large scale long term thermal units' maintenance scheduling problem. In the solution algorithm, the genetic algorithms (GA), the simulated annealing (SA) and the tabu search (TS) are cooperatively used. The solution algorithm keeps the advantages of individual algorithm and shows a reasonable combination of local search and global search. It adopts acceptance probability to improve the convergence of the simple GA, and introduces special encoding/ decoding techniques. To strengthen the searching ability, the neighborhood of current solution produced by genetic operations are search by tabu search. The multiyear thermal unit maintenance scheduling problem is a large scale combinatorial optimization problem, and the "curse of dimension" limits the applications of such method as dynamic programming branch and bound method and integer programming, etc. Furthermore, by the recent amendment of law in Japan, thermal unit maintenance can be postponed under the permitted combination of the maintenance class (A:detailed, B:simplified, C:Minor). This makes the problem more complex and larger in scale because the time horizon is extended to several consecutive years and the maintenance class of certain unit could be changed to get feasible or more accurate solutions. The authors also proposed a method which combines the genetic algorithm and the simulated annealing. In this method, the convergence of GA is improved by introducing the probability of SA as the criterion for acceptance of new trial solution. However, it is hard to find the optimum solution by only applying the genetic operators. As a result, the accuracy of this method is not a stable one. In the solution algorithm, the neighborhood of the solutions produced by genetic operations can be searched through the TS in every GA generation. Moreover, to strengthen the searching ability, the intensification and diversification of the searching region can be attained by using the long term and intermediate term memory of the TS. From the numerical results, the calculation results of the proposed method are better than those through any single algorithms or that of GA+SA, and the computation time is significantly smaller than that of the SA method.