The Harmony Search Algorithm Theory Of Evolutionary Computation And Its Complex Application In The Shop Scheduling Problems

The shop scheduling problem is a key of manufacturing system, and scheduling execution efficiency determines whether the manufacturing system can complete production task as planned. The effective and complete scheduling methods are capable to improve the quality of enterprise products and management efficiency and shorten the production cycle of products, and enhance the comprehensive strength of the manufacturing industry. The scheduling problems are complicated, which are typical NP-hard combinatorial optimization problems. Traditional methods and the existing scheduling strategies have been unable to meet various needs in the actual productions. Therefore, whether in the scheduling research theory or the actual manufacturing production, exploring effective scheduling scheme is still a focus in the research of this field.Harmony search algorithm(HSA), which mimics the process of the musicians’ improvisation, is a meta-heuristic optimization algorithm. The principle of HS is simple, there are few parameters to be tuned and it is easy to implement. Besides, it owns a particular way of exploring and exploiting the search space as well as powerful global searching ability. In this thesis, the comprehensive performance of the algorithm is improved by studying on the properties of HS and making a great improvement on HS, and the improved algorithm is applied to tackle two kinds of typical shop scheduling problem. The main research contents are as follows:1. In view of poor robustness and no direction of HS, as well as the weak local search ability of the HS, a self-adaptive harmony PSO search algorithm and its performance analysis(SHPSOS) is presented in this paper. In the SHPSOS, to improve the solution quality of the initial population and enhance the robustness of algorithm, the PSO algorithm and mutation strategy are respectively introduced.Meanwhile, a new effective improvisation scheme based on differential evolution and the best harmony(best individual) is developed to accelerate convergence performance and to improve solution accuracy. The global convergence performance of the SHPSOS algorithm is analyzed with the Markov model. The performance of the SHPSOS algorithm is evaluated through a large number of experiments on standard benchmark functions, and the simulation results demonstrate that SHPSOS algorithm on the solution accuracy and robustness outperforms other compared intelligent algorithms.2. For the permutation flow shop scheduling problems with objective of minimizingthe maximum completion time, an effective hybrid harmony search algorithm based on variable neighborhood search for the permutation flow shop scheduling problems is proposed. In the HHS algorithm, Firstly, the encoding scheme based on job sorting and SOV mapping rule are adopted. In order to guarantee the quality and diversity of initial population, the NEH algorithm and chaotic traverse are adopted to cooperatively complete the initialization. Meanwhile, the parameter sensitivity is studied and the combinatorial parameters selection criteria which is suitable for the algorithm is suggested. Finally, the neighborhood search which is used as the main body of local search algorithm is incorporated into the HHS to boost search accuracy of the algorithm. The performance of HHS algorithm is tested through a set of standard Flow Shop test instances and the simulation results show that HHS algorithm is effective on the PFSSP.3. For the job shop scheduling problems with the criterion to minimize makespan,an enhanced harmony search algorithm based on neighborhood search for the job shop scheduling problem is proposed. In the EHS algorithm, an efficient coding rule based on job sequences and activity decoding strategy are firstly adopted, and a specific enhanced mechanism, which borrows the idea from differential evolution algorithm for a new harmony vector, is introduced. Meanwhile, the neighborhood search algorithm based on critical path is embedded into EHS algorithm to boost the solutions quality. Finally, the performance of the EHS algorithm is evaluated through a set of standard job shop instances and the simulation results show that EHS algorithm can effectively solve JSSP.