A new hybrid genetic algorithm for job shop scheduling problem

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 v...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2012-10, Vol.39 (10), p.2291-2299
Main Authors: Qing-dao-er-ji, Ren, Wang, Yuping
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer simulation
Convergence
Critical path
Crossover operator
Exact sciences and technology
Genetic algorithm
Genetic algorithms
Genetics
Job shop scheduling
Job shop scheduling problem
Job shops
Local search
Mutation operator
Operational research and scientific management
Operational research. Management science
Operators
Optimization algorithms
Production scheduling
Scheduling, sequencing
Searching
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2011.12.005