Two Improved Cuckoo Search Algorithms for Solving The Flexible Job-Shop Scheduling Problem
DOI:
https://doi.org/10.31436/ijpcc.v2i2.34Abstract
The Cuckoo Search (CS) is heuristic search algorithm which inspired from cuckoo bird behavior. In this paper, we proposed two improvements for the cuckoo search algorithm of solving Flexible Job-Shop Scheduling problem (FJSP); the first one depends on Best Neighbors Generation (CS-BNG) and the second one based on Iterative Levy Flight (CS-ILF). Some adaptation for the key points of CS algorithm has been done to enhance searching in the discrete state space. The proposed algorithms have increased solutions quality and convergence rate. The improved algorithms have been tested on some FJSP benchmark instances for performance examination. The experimental results demonstrate the effectiveness of the improved algorithms in comparison to the basic cuckoo search algorithm.References
[1] M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, 4th ed., Springer-Verlag, 2012.
[2] Yao Wang, LinBo Zhu, Jiwen Wang, and Jianfeng Qiu, “An Improved Social Spider Algorithm for the Flexible Job-Shop Scheduling Problem,†Estimation, Detection and Information Fusion (ICEDIF) International Conference on. IEEE, pp. 157-162, 2015.
[3] Ling Wang, Gang Zhou, Ye Xu, Shengyao Wang, and Min Liu, “An effective artificial bee colony algorithm for the flexible job-shop scheduling problemâ€, The International Journal of Advanced Manufacturing Technology, Springer-Verlag, vol. 60, Issue 1, pp. 303-315, 2012.
[4] Jin Feng Wang, Bi Qiang Du, and Hai Min Ding, “A Genetic Algorithm for the Flexible Job-Shop Scheduling Problem†Advanced Research on Computer Science and Information Engineering International Conference (CSIE) Part I, pp. 332-339, 2011.
[5] Shekhar Singh and Krishna Pratap Singh, “Cuckoo Search Optimization for Job Shop Scheduling Problemâ€, Advances in Intelligent Systems and Computing, Proceedings of Fourth International Conference on Soft Computing for Problem Solving, Springer, pp. 99-111, 2015.
[6] El-Ghazali Talbi, Metaheuristics from Design to Implementation, John Wiley & Sons, 2009.
[7] Hongqing Zheng and Yongquan Zhou, “A Novel Cuckoo Search Optimization Algorithm Base on Gauss Distributionâ€, Journal of Computational Information Systems, vol. 8, no. 10, pp. 4193- 4200, 2012.
[8] Yongquan Zhou, Hongqing Zheng, Qifang Luo, and Jinzhao Wu, “An improved Cuckoo Search Algorithm for Solving Planar Graph Coloring Problemâ€, Applied Mathematics & Information Sciences, vol. 7, no. 2, pp. 785-792, 2013.
[9] Pauline Ong, “Adaptive Cuckoo Search Algorithm for Unconstrained Optimizationâ€, the Scientific World Journal, vol. 2014, 2014.
[10] Thang Trung Nguyena and Dieu Ngoc Vo, “Modified cuckoo search algorithm for short-term hydrothermal schedulingâ€, International Journal of Electrical Power & Energy Systems, Elsevier, vol. 65, pp. 271–281, 2015.
[11] Arit Thammano and Ajchara Phu-ang, “A Hybrid Artificial Bee Colony Algorithm with Local Search for Flexible Job-Shop Scheduling Problemâ€, Procedia Computer Science 20, Elsevier, pp. 96-101, 2013.
[12] Nouiri M., Jemai A., Ammari A. C., Bekrar A., and Niar S., “An effective particle swarm optimization algorithm for flexible job-shop scheduling problemâ€, Industrial Engineering and Systems Management (IESM), Proceedings of 2013 International Conference on. IEEE, pp. 1-6, 2013.
[13] Wei Zhou, Yan-ping Bu, and Ye-qing Zhou, “Combining CA and PSO to solve flexible job shop scheduling problemâ€, Control and Decision Conference (2014 CCDC), The 26th Chinese. IEEE, pp. 1031-1036, 2014.
[14] X. S. Yang and S. Deb, “Cuckoo search via Lévy flightsâ€, World Congress on Nature & Biologically Inspired Computing (NaBIC 2009).IEEE Publications, pp. 210–214, 2009.
[15] Behnke, D., Geiger, M.J, “Test instances for the flexible job shop scheduling problem with work centers,†Helmut-SchmidtUniversit¨at, Hamburg, Germany. Rep. RR-12-01-01, 2012.
[16] M. Mastrolilli, “Flexible Job Shop Problemâ€, Dalle Molle Institute for Artificial Intelligence (IDSIA), The University of Applied Sciences and Arts of Southern Switzerland (SUPSI). [Online]. Available: http://www.idsia.ch/~monaldo/fjsp.html
[2] Yao Wang, LinBo Zhu, Jiwen Wang, and Jianfeng Qiu, “An Improved Social Spider Algorithm for the Flexible Job-Shop Scheduling Problem,†Estimation, Detection and Information Fusion (ICEDIF) International Conference on. IEEE, pp. 157-162, 2015.
[3] Ling Wang, Gang Zhou, Ye Xu, Shengyao Wang, and Min Liu, “An effective artificial bee colony algorithm for the flexible job-shop scheduling problemâ€, The International Journal of Advanced Manufacturing Technology, Springer-Verlag, vol. 60, Issue 1, pp. 303-315, 2012.
[4] Jin Feng Wang, Bi Qiang Du, and Hai Min Ding, “A Genetic Algorithm for the Flexible Job-Shop Scheduling Problem†Advanced Research on Computer Science and Information Engineering International Conference (CSIE) Part I, pp. 332-339, 2011.
[5] Shekhar Singh and Krishna Pratap Singh, “Cuckoo Search Optimization for Job Shop Scheduling Problemâ€, Advances in Intelligent Systems and Computing, Proceedings of Fourth International Conference on Soft Computing for Problem Solving, Springer, pp. 99-111, 2015.
[6] El-Ghazali Talbi, Metaheuristics from Design to Implementation, John Wiley & Sons, 2009.
[7] Hongqing Zheng and Yongquan Zhou, “A Novel Cuckoo Search Optimization Algorithm Base on Gauss Distributionâ€, Journal of Computational Information Systems, vol. 8, no. 10, pp. 4193- 4200, 2012.
[8] Yongquan Zhou, Hongqing Zheng, Qifang Luo, and Jinzhao Wu, “An improved Cuckoo Search Algorithm for Solving Planar Graph Coloring Problemâ€, Applied Mathematics & Information Sciences, vol. 7, no. 2, pp. 785-792, 2013.
[9] Pauline Ong, “Adaptive Cuckoo Search Algorithm for Unconstrained Optimizationâ€, the Scientific World Journal, vol. 2014, 2014.
[10] Thang Trung Nguyena and Dieu Ngoc Vo, “Modified cuckoo search algorithm for short-term hydrothermal schedulingâ€, International Journal of Electrical Power & Energy Systems, Elsevier, vol. 65, pp. 271–281, 2015.
[11] Arit Thammano and Ajchara Phu-ang, “A Hybrid Artificial Bee Colony Algorithm with Local Search for Flexible Job-Shop Scheduling Problemâ€, Procedia Computer Science 20, Elsevier, pp. 96-101, 2013.
[12] Nouiri M., Jemai A., Ammari A. C., Bekrar A., and Niar S., “An effective particle swarm optimization algorithm for flexible job-shop scheduling problemâ€, Industrial Engineering and Systems Management (IESM), Proceedings of 2013 International Conference on. IEEE, pp. 1-6, 2013.
[13] Wei Zhou, Yan-ping Bu, and Ye-qing Zhou, “Combining CA and PSO to solve flexible job shop scheduling problemâ€, Control and Decision Conference (2014 CCDC), The 26th Chinese. IEEE, pp. 1031-1036, 2014.
[14] X. S. Yang and S. Deb, “Cuckoo search via Lévy flightsâ€, World Congress on Nature & Biologically Inspired Computing (NaBIC 2009).IEEE Publications, pp. 210–214, 2009.
[15] Behnke, D., Geiger, M.J, “Test instances for the flexible job shop scheduling problem with work centers,†Helmut-SchmidtUniversit¨at, Hamburg, Germany. Rep. RR-12-01-01, 2012.
[16] M. Mastrolilli, “Flexible Job Shop Problemâ€, Dalle Molle Institute for Artificial Intelligence (IDSIA), The University of Applied Sciences and Arts of Southern Switzerland (SUPSI). [Online]. Available: http://www.idsia.ch/~monaldo/fjsp.html
Downloads
Published
2016-11-22
How to Cite
T. Saadeq Al-Obaidi, A., & Hussein, S. A. (2016). Two Improved Cuckoo Search Algorithms for Solving The Flexible Job-Shop Scheduling Problem. International Journal on Perceptive and Cognitive Computing, 2(2). https://doi.org/10.31436/ijpcc.v2i2.34
Issue
Section
Articles
