Application of Ant Colony Algorithm to Job-Shop Scheduling Problem

Abstract:

Production sequence of workpieces on machines, also called job-shop scheduling problem (JSP), is a focus both in academics and in practices. The research on the problem can promote theoretical progress, shorten the production cycles, improve efficiency in using resources, and strengthen market response in actual production. Ant colony optimization (ACO) is very suitable for the solving of the problem. In the paper, a disjunctive graph model of JSP is set up, which transforms the problem into a natural expression that is suitable for ACO. Then, realization steps of ACO for JSP are discussed. Finally, a 3×3 JSP problem is solved in Jbuilder X. The obtained optimal solution verifies the feasibility and effectiveness of ACO in solving JSP.

• Periodical: Advanced Materials Research (Volume 411)
• Pages: 407-410
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.411.407
• Online since: November 2011
• Authors: Yan Cao, Lei Lei, Ya Dong Fang
• Keywords: Ant Colony Algorithm (ACA), JBuilder X, Job-Shop Scheduling Problem

References

[1] F. Liu, Y.L. Ma, and H. Yang, The study of job-shop scheduling problem, Chinese Journal of Mechanical Engineering. 36 (2000) 97-102.

[2] X. Wang, A rapid algorithm in resolving large-scale production scheduling, Combined Machine & Automatic Manufacturing Technique. 36 (2008) 39-42.

[3] J.G. Xu, G.Z. Dai, H.G. Wang, An overview of theories and methods of production scheduling, Journal of Computer Research and Development. 41 (2004) 258~267.

[4] D. Marco, Blum Christian, Ant colony optimization theory: A Survey, Theoretical Computer Science. 344 (2005) 243-278.

DOI: 10.1016/j.tcs.2005.05.020

[5] H.B. Duan, The Principle and Application of Ant Colony Algorithm, Beijing: Science Press, 2005.