Investigating Memetic Algorithm for Solving the Job Shop Scheduling Problems

The job shop scheduling problem (JSP) is well known as one of the most complex optimization problems due to its very large search space and many constraint between machines and jobs. Memetic algorithm (MA) is a hybrid evolutionary algorithm that combines the global search strategy and local search strategy. In this paper, an efficient MA combined with a novel local search strategy by exchanging and inserting based on the critical path is proposed to solve the JSP. The objective of minimizing make span is considered while satisfying a number of hard constraints. The computational results demonstrate the proposed MA is significantly superior to the other reported approaches in the literature.