Solving the Job-Shop Scheduling Problem Based on Cellular Genetic Algorithm

Abstract:

Cellular genetic algorithm (cGA) is a subclass of genetic algorithm (GA) in which the population diversity and exploration are enhanced thanks to the existence of small overlapped neighborhoods. Such a kind of structured algorithms is specially well suited for complex problems. Shop scheduling problem is a kind of problem with practical significance, and it belongs to a combinational optimization problem called NP-hard problem. In this paper we establish the model of job-shop problem (JSP) and solve the job-shop scheduling problem with cGA and traditional genetic algorithms (sGA).From the experimental results and analysis, we find cGA has better search efficiency and convergence performance than sGA.

• Periodical: Applied Mechanics and Materials (Volumes 433-435)
• Pages: 639-644
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.433-435.639
• Online since: October 2013
• Authors: Ming Yue Wen, Yi Zhang, Fang Jun Hu, Zheng Liu
• Keywords: Cellular Genetic Algorithm, Combinational Optimization, Job-Shop Scheduling, Neighbor Structure

References

[1] Wu Cheng, The theoretical background of contemporary integrated manufacturing, systems: One type of complexity problems and its solutions[J]. CIMS, 2001, 7(3): 1~7.

[2] Dai Shouli, Tan Yuejing, Wang Hao. The system search on production scheduling[J]. System Engineering. 1999, 17(1): 41~45.

[3] Dagli C, Sittisathanchai S. Genetic neuro-scheduler for job shop scheduler[J]. Computer and Industrial Engineering, 1993, 25(1-4): 267~270.

DOI: 10.1016/0360-8352(93)90272-y

[4] E. Alba, B. Dorronsoro, and H. Alfonso, Advanced models of cellular genetic algorithms evaluated on SAT, in Genetic and Evolutionary Computation Conference (GECCO), Washington, D.C. USA, June2005, p.1123–1130.

DOI: 10.1145/1068009.1068197

[5] E. Alba, B. Dorronsoro, F. Luna, A. Nebro, P. Bouvry, and L. Hogie, A cellular multi-objective genetic algorithm for optimal broadcasting strategy in metropolitan manets, Computer Communications, (2006).

DOI: 10.1016/j.comcom.2006.08.033

[6] JOLAI FARIBORZ, ASSADIPOUR GHAZAL. A hybrid cellular genetic algorithm for multi-objective crew scheduling problem[C]. Proceedings of the 5th International Conference on Hybrid Artificial Intelligence Systems (HAIS 2010). 2010: 359-367.

DOI: 10.1007/978-3-642-13769-3_44

[7] LI XUNBO, WANG ZHENLIN. Cellular genetic algorithms for optimizing the area covering of wireless sensor networks[J]. Chinese Journal of Electronics, 2011, 20(2): 352-356.

[8] NIAZY NORA SALAH, BADR AMR. Complexity of capacitated vehicles routing problem using cellular genetic algorithms[J]. International Journal of Computer Science and Network Security, 2012, 12(2): 5-11.

[9] DORRONSORO BERNABE, ARIAS DANIEL, LUNA FRANCISCO, et al. A grid-based hybrid cellular genetic algorithm for very large scale instances of the CVRP[C]. Proceedings of the 21st European Conference on Modelling and Simulation (ECMS 2007). 2007: 759-765.

[10] Dorronsorob, Acbae. A simple cellular genetic algorithm for continuous optimization[C]. Proc. of IEEE congress on evolutionary computation, (2006).

[11] Cheng Runwei, Gen M, Tsujimura Y. A tutorial survey of job-shop scheduling using genetic agorithms: partI[J]. Representation, International Journal of the theory and systems, 1995, 22: 15~24.