A new hybrid genetic algorithm for job shop scheduling problem |
| |
Authors: | Ren Qing-dao-er-ji |
| |
Affiliation: | a School of Science, Xidian University, Xi’an 710071, China b School of Computer Science and Technology, Xidian University, Xi’an 710071, China |
| |
Abstract: | 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. |
| |
Keywords: | Genetic algorithm Job shop scheduling problem Crossover operator Mutation operator Local search |
本文献已被 ScienceDirect 等数据库收录! |
|