Adaptive memetic algorithm for the job shop scheduling problem

Solving the job shop scheduling problem (JSP) is a vital research topic due to its wide practical applicability. It is an NP-hard discrete optimization problem which was transformed into a plethora of variants reflecting other real-life scenarios. In this paper, we propose an adaptive memetic algorithm (MA) to solve the JSP. It consists in determining a schedule for completing jobs (divided into operations) on a set of available machines. MAs, which are the hybrids of genetic algorithms and refinement procedures, were shown to be very efficient in tackling complex problems in many fields of science and engineering. In the proposed algorithm (AMXMA), a number of children are generated for each pair of parents to exploit them intensively. We keep three solution representations (if necessary) within each individual to avoid the necessity of transforming one representation into another required by various crossover operators. In addition, we introduce the adaptive selection scheme which is dynamically controlled on the fly to effectively balance the exploration and exploitation of the search space. An extensive experimental study performed on a widely-used benchmark set of problems with various sizes shows that AMXMA is extremely efficient in terms of the computation time and allows for fast convergence to very high-quality solutions. We show that AMXMA is highly competitive compared with other state-of-the-art algorithms.