An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem

摘要

An improved adaptive genetic algorithm (IAGA) for solving the minimum makespan problem of job-shop scheduling problem (JSP) is presented. Though the traditional genetic algorithm (GA) exhibits implicit parallelism and can retain useful redundant information about what is learned from previous searches by its representation in individuals in the population, yet GA may lose solutions and substructures due to the disruptive effects of genetic operators and is not easy to regulate GA’s convergence. The proposed IAGA is inspired from hormone modulation mechanism, and then the adaptive crossover probability and adaptive mutation probability are designed. The proposed IAGA is characterized by simplifying operations, high search precision, overcoming premature phenomenon and slow evolution. The proposed method by employing operation-based encoding is effectively applied to solve a dynamic job-shop scheduling problem (DJSP) and a complicated contrastive experiment of JSP in manufacturing system. Meanwhile, in order to ensure to create a feasible solution, a new method for crossover operation is adopted, named, partheno-genetic operation (PGO). The computational results validate the effectiveness of the proposed IAGA, which can not only find optimal or close-to-optimal solutions but can also obtain both better and more robust results than the existing genetic algorithms reported recently in the literature. By employing IAGA, machines can be used more efficiently, which means that tasks can be allocated appropriately, production efficiency can be improved, and the production cycle can be shortened efficiently.