A Survey of Recent Developments for JSSP and FJSSP Using ACO

Abstract:

Ant Colony Optimization (ACO) is based on swarm intelligence and it is a constructive meta-heuristic which was first presented in 1991. Job Shop Scheduling Problem (JSSP) is very important problem of the manufacturing industry. JSSP is a combinatorial optimization problem which is NP-hard. The exact solution of NP-hard problem is very difficult to find. Therefore heuristics approach is the best approach for such problems. This paper shall overview the application of ant colony optimization on JSSP and Flexible Job Shop Scheduling problems (FJSSP). This paper shalll cover the major areas in which researchers have worked and it shall also recommend the future area of research in the light of this overview. This paper will also cover the quantitative analysis of the research papers which are considered in this survey. Based upon this survey some conclusions are drawn in the end.The significance of this paper is that it has covered all the efforts and major researches in the area of ACO application on JSSP and FJSSP through the inception of ACO metaheuristics. This enables the researchers and scheduling experts to overview chronologically the development of ACO on JSSP and FJSSP.

• Periodical: Advanced Materials Research (Volumes 816-817)
• Pages: 1133-1139
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.816-817.1133
• Online since: September 2013
• Authors: Nasir Mehmood, Muhammad Umer, Ahmad Riaz
• Keywords: Ant Colony Optimization (ACO), Flexible Job Shop Scheduling Problem, Job Shop Scheduling Problem

References

[1] Alberto Colorni, Marco Dorigo, Vittorio Maniezzo and Marco Trubian Ant system for Job-shop Scheduling.

[2] Sjoerd van der Zwaan and Carlos Marques. Ant Colony Optimisation for Job Shop Scheduling.

[3] Mario Ventresca and Beatrice M. Ombuki. Ant Colony Optimization for Job Shop Scheduling Problem.

[4] De-lin Luo, Shun-xiang Wu, Mao-qing Li and Zhong Yang. Ant Colony Optimization with Local Search Applied to the Flexible Job Shop Scheduling Problems. 978-1-4244-2064-3/08/$25. 00 ©2008 IEEE.

DOI: 10.1109/icccas.2008.4657941

[5] Kuo-Ling Huang and Ching-Jong Liao. Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers & Operations Research 35 (2008) 1030 – 1046.

DOI: 10.1016/j.cor.2006.07.003

[6] James Montgomery, Carole Fayad and Sanja Petrovic. Solution Representation for Job Shop Scheduling Problems in Ant Colony Optimisation. Solution Representation for Job Shop Scheduling Problems in ACO Technical Report SUTICT-TR2006. 05 15 May (2006).

DOI: 10.1007/11839088_49

[7] Masaya Yoshikawa and Hidekazu Terai. A Hybrid Ant Colony Optimization Technique for Job-Shop Scheduling Problems. Proceedings of the Fourth International Conference on Software Engineering Research, Management and Applications (SERA'06) 0-7695-2656-X/06 © (2006).

DOI: 10.1109/sera.2006.17

[8] Noureddine Liouane, Ihsen Saad, Slim Hammadi and Pierre Borne. Ant systems & Local Search Optimization for flexible Job Shop Scheduling Production. International Journal of Computers, Communications & Control Vol. II (2007), No. 2, pp.174-184.

DOI: 10.15837/ijccc.2007.2.2350

[9] Xiao-Lan Zhuo, Jun ZHANG, MIEEE and Wei-neng Cheng. A New Pheromone Design in ACS for Solving JSP. 1-4244-1340-0/07$25. 00 c_2007 IEEE.

[10] J. Heinonen and F. Pettersson. Hybrid ant colony optimization and visibility studies applied to a job-shop scheduling problem. Applied Mathematics and Computation 187 (2007) 989–998.

DOI: 10.1016/j.amc.2006.09.023

[11] Nilgu¨n Fıg˘lalı , Celal O¨ zkale, Orhan Engin and Alpaslan Fıg˘lalı. Investigation of Ant System parameter interactions by using design of experiments for job-shop scheduling problems. Computers & Industrial Engineering 56 (2009) 538–559.

DOI: 10.1016/j.cie.2007.06.001

[12] Andrea Rossi and Gino Dini. Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method. Robotics and Computer-Integrated Manufacturing 23 (2007) 503–516.

DOI: 10.1016/j.rcim.2006.06.004

[13] A. UDOMSAKDIGOOL and V. KACHITVICHYANUKUL. Multiple colony ant algorithm for job-shop scheduling problem. International Journal of Production Research ISSN 0020–7543 print/ISSN 1366–588X online _ 2008 Taylor & Francis.

DOI: 10.1080/00207540600990432

[14] Li-Ning Xing, Ying-Wu Chen and Ke-Wei Yang. Interactive Fuzzy Multi-objective Ant Colony Optimization with Linguistically Quantified Decision Functions for Flexible Job Shop Scheduling Problems. Frontiers in the Convergence of Bioscience and Information Technologies. 0-7695-2999-2/07 $25. 00 © 2007 IEEE DOI 10. 1109/FBIT. 2007. 18.

DOI: 10.1109/fbit.2007.18

[15] Li Li and Keqi Wang. Multi-objective Flexible Job Shop Schedule Based on Improved Ant Colony Algorithm. International Conference on Information and Automation June 22 -25, 2009, Zhuhai/Macau, China. 978-1-4244-3608-8/09/$25. 00 © (2009).

DOI: 10.1109/icinfa.2009.5205096

[16] S. G. Ponnambalam, N. Jawahar and B. S. Girish. An Ant Colony Optimization algorithm for Flexible Job shop scheduling problem.

DOI: 10.5772/9425

[17] Apinanthana Udomsakdigool and Voratas Khachitvichyanukul. Ant colony algorithm for multi-criteria job shop scheduling to minimize makespan, mean flow time and mean tardiness. ISSN 1750-9653, England, UK International Journal of Management Science and Engineering Management, 6(2): 117-123, (2011).

DOI: 10.1080/17509653.2011.10671153

[18] Zhiqiang Zhang, Jing Zhang and Shujuan Li. A Modified Ant Colony Algorithm for the Job Shop Scheduling Problem to Minimize Makespan. 978-1-4244-7739-5/10/$26. 00 ©2010 IEEE.

DOI: 10.1109/mace.2010.5535635

[19] Li Li, Wang Keqi and Zhou Chunnan. An Improved Ant Colony Algorithm Combined with Particle Swarm Optimization Algorithm for Multi-objective Flexible Job Shop Scheduling Problem. International Conference on Machine Vision and Human-machine Interface. 978-0-7695-4009-2/10 $26. 00 © 2010 IEEE DOI 10. 1109/MVHI. 2010. 94.

DOI: 10.1109/mvhi.2010.94

[20] Tian Jing and Murata Tomohiro. Multi-objective flexible job shop scheduling with uncertain processing time and machine available constraint based on hybrid optimization approach. 978-1-4244-8376-1/10/$26. 00 ©(2010).

DOI: 10.1109/ical.2010.5585352

[21] Shih-Pang Tseng, Chun-Wei Tsai, Jui-Le Chen, Ming-Chao Chiang and Chu-Sing Yang. Job Shop Scheduling Based on ACO with a Hybrid Solution Construction Strategy. 978-1-4244-7317-5/11/$26. 00 ©(2011).

DOI: 10.1109/icmlc.2012.6359630

[22] Rong-Hwa Huang, Chang-LinYang and Wei-CheCheng. Flexible job shop scheduling with due window-a two-pheromoneant colony approach. Int. J. Production Economics 141 (2013) 685–697.

DOI: 10.1016/j.ijpe.2012.10.011