Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 39, Issue 10, Pages 2291-2299Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2011.12.005
Keywords
Genetic algorithm; Job shop scheduling problem; Crossover operator; Mutation operator; Local search
Categories
Funding
- National Natural Science Foundation of China [60873099]
- Ph.D. Programs Foundation of Ministry of Education of China [20090203110005]
Ask authors/readers for more resources
Job shop scheduling problem is a typical NP-hard problem. To solve the job shop scheduling problem more effectively, some genetic operators were designed in this paper. In order to increase the diversity of the population, a mixed selection operator based on the fitness value and the concentration value was given. To make full use of the characteristics of the problem itself, new crossover operator based on the machine and mutation operator based on the critical path were specifically designed. To find the critical path, a new algorithm to find the critical path from schedule was presented. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed and its convergence was proved. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm. (C) 2011 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available