Intelligent Optimization Algorithm Research Based On Job Shop Scheduling

Intelligent optimization algorithms is designed for solving optimization problem, by imitating the laws of nature or biosphere, including genetic algorithm, simulated annealing algorithm, artificial neural network method, ant colony algorithm, tabu search algorithm and so on. Intelligent optimization algorithms have incomparable superiority in solving large-scale NP-hard optimization problems. However, applied to specific optimization problem, their search efficiency are still to be improved. In this paper, we will put the JSP (Job Shop Problem) as the research object, and improve the search efficiency of intelligent optimization algorithms in solving the JSP.On the one hand, we improve the search efficiency of intelligent optimization algorithms in solving the JSP by improving the quality of the solution and reducing the search space of the optimal solution. According the research of JSP, PLFA (Full Active based Preference List) algorithm based preference list-based representation and the concept of full active schedule is proposed, which could transform feasible or infeasible solution into full active schedule and improve the quality of the solution. We design the hybrid genetic algorithm and hybrid simulated annealing, formed by combining genetic algorithm and simulated annealing with PLFA. The two hybrid optimization algorithms are both compared with the traditional genetic algorithm and simulated annealing.On the other hand, we improve the search efficiency of intelligent optimization algorithms in solving the JSP by paralleling the intelligent optimization algorithms. we design the coarse grained parallel hybrid genetic algorithm PLFA-PGA based on the Map-Reduce model and study the impact of the number of machines and the number of population on the running time.The paper consists of three parts. Firstly, it gives a briefly introduction research background and current study situation. Secondly, it introduces the PLFA method , the two hybrid algorithms combing the PLFA algorithm with intelligent optimization algorithms, as well as the parallel hybrid genetic algorithm based Map-Reduce model; Finally, summary and outlook.