Improved Genetic Algorithm Based on Operation Order Matrix Encoding for Job Shop Scheduling Problem

Abstract:

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.

• Periodical: Advanced Materials Research (Volumes 189-193)
• Pages: 4212-4215
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.189-193.4212
• Online since: February 2011
• Authors: Hong Zhan, Jian Jun Yang, Lu Yan Ju
• Keywords: Improved Genetic Algorithm (IGA), Job-Shop Scheduling Problem, Matrix Encoding, Operation Order

References

[1] C.Y. Zhang, Y.Q. Rao and P.G. Li: Int J Adv Manuf Technol, Vol. 39(2008), p.965.

[2] J.T. Tsai, T.K. Liu, W.H. Ho and J.H. Chou: Int J Adv Manuf Technol, Vol. 38(2008), p.987.

[3] K.S. Amirthagedeswaran and V.P. Arunachalam: Int J Adv Manuf Technol, Vol. 32(2007), p.780.

[4] F. Croce, R. Tadei and G. Volta: Computersand Operations Research, Vol. 22(1995), p.15.

[5] L. Wang and D.Z. Zheng: Computers & Operations Research, Vol. 28 (2001), p.585.

[6] L. Wang and D.Z. Zheng: Int J Adv Manuf Technol, Vol. 20 (2002), p.72.