Improved Genetic Algorithm Based on Operation Order Matrix Encoding for Job Shop Scheduling Problem
This paper presents an improved genetic algorithm for the job shop scheduling problem. We designed a new encoding method based on operation order matrix, a matrix correspond to a chromosome, the value of elements is not repetitive, that means a processing order number in all operations of all jobs. Aiming at the features of the matrix encoding, we designed the crossover and mutation methods based on jobs, and the infeasible solutions are avoided. Through adjusting the computing method of fitness value, the improved genetic algorithm takes on some self adapting capability. The proposed approach is tested on some standard instances and compared with two other approaches. The computation results validate the algorithm is efficient.
Zhengyi Jiang, Shanqing Li, Jianmin Zeng, Xiaoping Liao and Daoguo Yang
H. Zhan et al., "Improved Genetic Algorithm Based on Operation Order Matrix Encoding for Job Shop Scheduling Problem", Advanced Materials Research, Vols. 189-193, pp. 4212-4215, 2011