Hybrid VNS and memetic algorithm for solving the job shop scheduling problem

The job shop scheduling problem (JSP) is focused by many researchers which is well known as one of the most complex optimization problems due to its very large search space and many constraint between jobs and machines. It is quite difficult to achieve optimal or near-optimal solutions with single traditional optimization approach. Memetic algorithm (MA) is a hybrid algorithm that combines the local search strategy and global search strategy. In this paper, an novel hybrid algorithm combined variable neighborhood search (VNS) algorithm with memetic algorithm is proposed to solve the JSP. The neighborhood functions is generated by exchanging and inserting the key operations which belong to the critical path. The minimizing makespan is considered as optimization objective. Lastly, benchmark problems is computed, and the results demonstrate the proposed hybrid algorithm is effective and efficient for solving the JSP.