A novel adaptive hybrid framework for job shop scheduling problem

This paper deals with the Job Shop Scheduling Problem (JSP) with the objective of minimizing the makespan criterion, the time elapsed between the start of the first job and end of the last job arranged in a job sequence. We propose a novel multi-population based framework called HADP-JSP to solve the JSP. In the HADP-JSP the main population is divided into several groups. Each group adaptively chooses one algorithm from the algorithm pool and then uses it to find solutions (schedules). The operation of selecting an algorithm is done based on the algorithm fitness. The fitness of the algorithms implies the average improvement which they make on the makespanes of the schedules in a group. The algorithm pool consists of five algorithms developed using the Memetic Algorithm, Genetic Algorithm, and Simulated Annealing Algorithm. We have assessed the efficiency of HADP-JSP by running it on a set of 20 well known instances introduced by Lawrence. We have compared the results obtained with those of the three algorithms established in the literature during the last five years. The results indicate that in 95% of all cases the proposed approach can yield the solutions that their values of the makespan are equal to the Best Known Solution (BKS).