Application of Social Spider Optimization for Permutation Flow Shop Scheduling Problem

Abstract

Permutation flow shop scheduling problem (PFSP) is an NP-complete problem with a wide range of applications in many real-world applications. Social spider optimization (SSO) is a swarm intelligence algorithm proposed for continuous optimization problems. Recently, SSO has received increased interest in the field of combinatorial optimization as well. For this reason, in this paper, SSO algorithm is proposed to solve the PFSP with make span minimization. The proposed algorithm has been tested on 141 well-known benchmark instances and compared against six other conventional and best-so-far metaheuristics. The obtained results show that SSO outperforms some of the compared works although they are hybrid methods.

Keywords

• Metaheuristic
• Optimization
• Flow Shop Scheduling
• Social Spider
• swarm intelligence

References

1. [1] V. Fernandez-Viagas, R. Ruiz, J. M. Framinan, “A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation”, Eur. J. Oper. Res., vol. 257, no. 3, pp. 707-721, Mar. 2017.
2. [2] Q. Lin, L. Gao, X. Li, C. Zhang, ”A hybrid backtracking search algorithm for permutation flow-shop scheduling problem”, Comput. Ind. Eng., vol. 85, pp. 437-446, July. 2015.
3. [3] N. A. Alawad, B. H. Abed-alguni, ”Discrete Jaya with refraction learning and three mutation methods for the permutation flow shop scheduling problem”, J Supercomput, pp. 1-22, July. 2021.
4. [4] P. Wu, Q. Yang, W. Chen, B. Mao, H. Yu, ”An Improved Genetic-Shuffled Frog-Leaping Algorithm for Permutation Flowshop Scheduling”, Complexity, 2020.
5. [5] L. Libralesso, P. A. Focke, A Secardin, V. Jost, “Iterative beam search algorithms for the permutation flowshop”, arXiv preprint arXiv, Sep. 2020.
6. [6] C. Y. Hsu, P. C. Chang, M. H. Chen, “A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem”, Comput. Ind. Eng., vol. 83, pp. 159-171, May. 2015.
7. [7] F. Zhao, J. Zhang, J. Wang, C. Zhang, “A shuffled complex evolution algorithm with opposition-based learning for a permutation flow shop scheduling problem”, Int. J. Computer Integr. Manuf., vol. 28, no. 11, pp. 1220-1235, Oct. 2015.
8. [8] M. Kurdi, ”A memetic algorithm with novel semi-constructive evolution operators for permutation flowshop scheduling problem”, Appl. Soft Comput., vol. 94, Sept. 2020.

9. [9] M. Bessedik, F. B. S. Tayeb, H. Cheurfi, A. Bliz, ”An immunity-based hybrid genetic algorithms for permutation flowshop scheduling problems”, Int. J. Adv. Manuf. Syst., vol. 85. no 9-12, pp. 2459-2469, Aug. 2016.
10. [10] F. B. S. Tayeb, M. Bessedik, M. Benbouzid, M. Benbouzid, H. Cheurfi, A. Blizak, “Research on Permutation Flow-shop Scheduling Problem based on Improved Genetic Immune Algorithm with vaccinated offspring”, Procedia Comput. Sci., vol. 112, pp. 427-436, 2017.
11. [11] F. Zhao, Y. Liu, Z. Shao, X. Jiang, C. Zhang, J. Wang, “A chaotic local search based bacterial foraging algorithm and its application to a permutation flow-shop scheduling problem”, Int. J. Computer Integr. Manuf., vol. 29, no. 9, pp. 962-981, 2016.
12. [12] Ö. Tosun, M. K. Marichelvam, “Hybrid bat algorithm for flow shop scheduling problems”, Int. J. Math. Oper., vol. 9, no. 1, pp. 125-138, 2016.
13. [13] S. Deb, Z. Tian, S. Fong, R. Tang, R. Wong, N. Dey, “Solving permutation flow-shop scheduling problem by rhinoceros search algorithm”, Soft Comput., vol. 22, no. 18, pp. 6025-6034, 2018.
14. [14] J. Lin, “A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem” Int. J. Prod. Res., vol. 54, no. 16, pp. 4805-4814, 2016.
15. [15] V. Santucci, M. Baioletti, A. Milani, ”Solving permutation flowshop scheduling problems with a discrete differential evolution algorithm”, AI Commun., vol. 29, no. 2, pp. 269-286, 2016.
16. [16] W. Shao, D. Pi, “A self-guided differential evolution with neighborhood search for permutation flow shop scheduling”, Expert Syst. Appl., vol. 51, pp. 161-176, June. 2016.
17. [17] F. Zhao, Y. Liu, Y. Zhang, W. Ma, C. Zhang, “A hybrid harmony search algorithm with efficient job sequence scheme and variable neighborhood search for the permutation flow shop scheduling problems”, Eng. Appl. Artif. Intell., vol. 65, pp. 178-199, Oct. 2017.
18. [18] H. Wang, W. Wang, H. Sun, Z. Cui, S. Rahnamayan, S. Zeng, “A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problems”, Soft Comput., vol. 21, no. 15, pp. 4297-4307, 2017.
19. [19] K .Govindan, R. Balasundaram, N. Baskar, P. Asokan, “A hybrid approach for minimizing makespan in permutation flowshop scheduling”, J. Syst. Sci. Syst. Eng., vol. 26, no. 1, pp. 50-76, 2017.
20. [20] J. Dubois-Lacoste, F. Pagnozzi, T. Stützle, “An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem”, Comput. Oper. Res., vol. 81, pp.160-166, May. 2017.
21. [21] M. K. Marichelvam, Ö. Tosun, M. Geetha, “Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time”, Appl. Soft Comput., vol. 55, no. 82-92, 2017.
22. [22] Y. Zhang, Y. Yu, S. Zhang, Y. Luo, L. Zhang, “Ant colony optimization for Cuckoo Search algorithm for permutation flow shop scheduling problem”, Syst. Sci. Control. Eng., vol. 7, no. 1, pp. 20-27, 2019.
23. [23] S. M. Lim, K. Y. Leong. “A brief survey on intelligent swarm-based algorithms for solving optimization problems”, in Nature-inspired Methods for Stochastic, Robust and Dynamic Optimization, 2018, ch. 4, pp 47–61.
24. [24] S. Kavitha, P. Venkumar, N . Rajini, P. Pitchipoo, “An Efficient Social Spider Optimization for Flexible Job Shop Scheduling Problem”, J. Adv. Manuf. Syst., vol. 17, no. 2, pp. 181-196, 2018.
25. [25] Y. Wang, L. Zhu, J. Wang, J. Qiu, “An improved social spider algorithm for the Flexible Job-Shop Scheduling Problem”, in ICEDIF, Harbin, China, 2015, pp. 157-162.
26. [26] M. Kurdi, “A Social Spider Optimization Algorithm for Hybrid Flow Shop Scheduling with Multiprocessor Task”, in 12th NCMCONFERENCES, Ankara, Turkey, 2018. Available at SSRN 3301792.
27. [27] G. Zhang, K. Xing, “Memetic social spider optimization algorithm for scheduling two-stage assembly flowshop in a distributed environment”, Comput. Ind. Eng., vol. 125, pp. 423-433, Nov. 2018.
28. [28] G. Zhou, Y. Zhou, R. Zhao, “Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem”, J. Ind. Manag., vol. 17, no. 2, pp. 533-548, Mar. 2021.
29. [29] G. I. Zobolas, C. D. Tarantilis and G. Ioannou, “Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm”, Comput. Oper. Res., vol. 36, no. 4, pp. 1249-1267, Apr. 2009.
30. [30] E. Cuevas, M. Cienfuegos, D. Zaldívar, M. Pérez-Cisneros, ”A swarm optimization algorithm inspired in the behavior of the social-spider”, Expert Syst. Appl., vol 40, no. 16, pp. 6374-6384, Nov. 2013.
31. [31] J. C. Bean, “Genetic algorithms and random keys for sequencing and optimization”, ORSA J. Comput., vol. 6. no. 2, pp.154-160, 1994.
32. [32] C. R. Reeves, ”A genetic algorithm for flowshop sequencing”, Comput. Oper. Res., vol. 22, no. 1, pp. 5-13, Jan. 1995.
33. [33] E. Taillard, "Benchmarks for basic scheduling problems”, Eur. J. Oper. Res., vol. 64, no. 2, pp. 278-285, 1993.
34. [34] P. C. Chang, S. H. Chen, C. Y. Fan, C. L. Chan, “Genetic algorithm integrated with artificial chromosomes for multi-objective flowshop scheduling problems”, Appl. Math. Comput., vol. 205, no. 2, pp. 550-561, Nov. 2008.
35. [35] M. Abdel-Basset, G. Manogaran, D. El-Shahat, S. Mirjalili, “A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem”, Future Gener. Comput. Syst. vol. 85, pp. 129-145, Aug. 2018.