Research On Job Shop Scheduling Problem Based On Improved Harmony Search Algorithm

The job shop scheduling problem (JSSP) is a typical production scheduling problem in modern manufacturing system. It has received researchers’widespread attention. It is a NP-hard problem because it has the processing path constraint and the exclusive constraint of resources (machines). This paper studies the hybrid algorithm of improved harmony search and simulated annealing algorithm (IHSSA). The hybrid algorithm is applied to solve the job shop scheduling problem.First of all, the hybrid algorithm called IHSSA algorthm which is based on improved harmony search and simulated annealing algorithm is proposed. Improved harmony search algorithm (IHS) overcomes the drawbacks of the fixed pitch adjusting rate (PAR) and bandwidth (BW). This method not only guarantees the diversity of harmony solutions but it also improves the algorithm convergence speed. However, the IHS algorithm is still not reducing the dependence of traditional harmony search algorithm to the initial solutions. In order to solve this problem, introduce simulated annealing algorithm to the procedure of generating initial harmony solutions. This method improves the fitness of initial harmony solutions. At the same time, use simulated annealing algorithm for generated new harmony solution and the new harmony is replaced by the search result. In this way, the possibility of collecting the global optimal solution and the convergence speed of IHSSA is increased significantly.Then this paper uses encoding based on the stage for the job shop scheduling problem. This encoding method ensures the legitimacy of the generated solutions. But as a kind of discrete encoding, it is not suitable for harmony search algorithm to use. This paper uses the Large Position Value (LPV) rule to realize harmony search algorithm for discrete problem. However, the procedure of generating new harmony solutions may produce illegal solutions. A Ranked Order Job (ROJ) rule is proposed to ensure the legitimacy of new harmony solutions.Finally, the proposed IHSSA algorithm is used for simulation experiments of single machine scheduling systems and complex operations systems. the comparison of the results with the existing algorithms proves that the algorithm is correct and effective for solving job shop shecduling problem.