Multi-stage hybrid evolutionary algorithm for multiobjective distributed fuzzy flow-shop scheduling problem

Wenqiang Zhang; Xiaoxiao Zhang; Xinchang Hao; Mitsuo Gen; Guohui Zhang; Weidong Yang; Wenqiang Zhang; Xiaoxiao Zhang; Xinchang Hao; Mitsuo Gen; Guohui Zhang; Weidong Yang

doi:10.3934/mbe.2023224

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 3: 4838-4864. doi: 10.3934/mbe.2023224

Previous Article Next Article

Research article Special Issues

Multi-stage hybrid evolutionary algorithm for multiobjective distributed fuzzy flow-shop scheduling problem

1.
College of Information Science and Engineering, Henan University of Technology, China
2.
School of Art and Design, Changzhou Institute of Technology, China
3.
Fuzzy Logic Systems Institute, Tokyo University of Science, Japan
4.
School of Management Engineering, Zhengzhou University of Aeronautics, China
5.
Henan Key Laboratory of Grain Photoelectric Detection and Control, Henan University of Technology, China

Academic Editor: Danilo Pelusi

Received: 18 November 2022 Revised: 18 December 2022 Accepted: 21 December 2022 Published: 04 January 2023

In the current global cooperative production mode, the distributed fuzzy flow-shop scheduling problem (DFFSP) has attracted much attention because it takes the uncertain factors in the actual flow-shop scheduling problem into account. This paper investigates a multi-stage hybrid evolutionary algorithm with sequence difference-based differential evolution (MSHEA-SDDE) for the minimization of fuzzy completion time and fuzzy total flow time. MSHEA-SDDE balances the convergence and distribution performance of the algorithm at different stages. In the first stage, the hybrid sampling strategy makes the population rapidly converge toward the Pareto front (PF) in multiple directions. In the second stage, the sequence difference-based differential evolution (SDDE) is used to speed up the convergence speed to improve the convergence performance. In the last stage, the evolutional direction of SDDE is changed to guide individuals to search the local area of the PF, thereby further improving the convergence and distribution performance. The results of experiments show that the performance of MSHEA-SDDE is superior to the classical comparison algorithms in terms of solving the DFFSP.
- hybrid evolutionary algorithms,
- sequence difference,
- multi-stage strategies,
- distributed fuzzy flow-shop scheduling,
- multiobjective optimization
Citation: Wenqiang Zhang, Xiaoxiao Zhang, Xinchang Hao, Mitsuo Gen, Guohui Zhang, Weidong Yang. Multi-stage hybrid evolutionary algorithm for multiobjective distributed fuzzy flow-shop scheduling problem[J]. Mathematical Biosciences and Engineering, 2023, 20(3): 4838-4864. doi: 10.3934/mbe.2023224

Related Papers:

Abstract

In the current global cooperative production mode, the distributed fuzzy flow-shop scheduling problem (DFFSP) has attracted much attention because it takes the uncertain factors in the actual flow-shop scheduling problem into account. This paper investigates a multi-stage hybrid evolutionary algorithm with sequence difference-based differential evolution (MSHEA-SDDE) for the minimization of fuzzy completion time and fuzzy total flow time. MSHEA-SDDE balances the convergence and distribution performance of the algorithm at different stages. In the first stage, the hybrid sampling strategy makes the population rapidly converge toward the Pareto front (PF) in multiple directions. In the second stage, the sequence difference-based differential evolution (SDDE) is used to speed up the convergence speed to improve the convergence performance. In the last stage, the evolutional direction of SDDE is changed to guide individuals to search the local area of the PF, thereby further improving the convergence and distribution performance. The results of experiments show that the performance of MSHEA-SDDE is superior to the classical comparison algorithms in terms of solving the DFFSP.

References

[1]	L. Wang, W. Shen, Process Planning and Scheduling for Distributed Manufacturing, Springer Science & Business Media, 2007. https://doi.org/10.1007/978-1-84628-752-7
[2]	X. Chen, V. Chau, P. Xie, M. Sterna, J. Błażewicz, Complexity of late work minimization in flow shop systems and a particle swarm optimization algorithm for learning effect, Comput. Ind. Eng., 111 (2017), 176–182. https://doi.org/10.1016/j.cie.2017.07.016 doi: 10.1016/j.cie.2017.07.016
[3]	X. Yu, M. Gen, Introduction to Evolutionary Algorithms, Springer Science & Business Media, 2010. https://doi.org/10.1007/978-1-84996-129-5
[4]	Y. Abdi, M. Feizi-Derakhshi, Hybrid multi-objective evolutionary algorithm based on search manager framework for big data optimization problems, Appl. Soft Comput., 87 (2020), 105991. https://doi.org/10.1016/j.asoc.2019.105991 doi: 10.1016/j.asoc.2019.105991
[5]	W. Zhang, D. Yang, G. Zhang, M. Gen, Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for VRPTW, Expert Syst. Appl., 145 (2020), 113151. https://doi.org/10.1016/j.eswa.2019.113151 doi: 10.1016/j.eswa.2019.113151
[6]	K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6 (2002), 182–197. https://doi.org/10.1109/4235.996017 doi: 10.1109/4235.996017
[7]	E. Zitzler, M. Laumanns, L. Thiele, SPEA2: Improving the strength Pareto evolutionary algorithm, TIK Rep., 103 (2001). https://doi.org/10.3929/ETHZ-A-004284029
[8]	Q. Zhang, H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11 (2007), 712–731. https://doi.org/10.1109/TEVC.2007.892759 doi: 10.1109/TEVC.2007.892759
[9]	W. Zhang, J. Lu, H. Zhang, C. Wang, M. Gen, Fast multi-objective hybrid evolutionary algorithm for flow shop scheduling problem, in Proceedings of the Tenth International Conference on Management Science and Engineering Management, Springer, Singapore, (2017), 383–392. https://doi.org/10.1007/978-981-10-1837-4_33
[10]	W. Zhang, Y. Wang, Y. Yang, M. Gen, Hybrid multiobjective evolutionary algorithm based on differential evolution for flow shop scheduling problems, Comput. Ind. Eng., 130 (2019), 661–670. https://doi.org/10.1016/j.cie.2019.03.019 doi: 10.1016/j.cie.2019.03.019
[11]	H. A. E. Khalifa, F. Smarandache, S. S. Alodhaibi, A fuzzy approach for minimizing machine rental cost for a specially-structured three-stages flow-shop scheduling problem in a fuzzy environment, in Handbook of Research on Advances and Applications of Fuzzy Sets and Logic, IGI Global, (2022), 105–119. https://doi.org/10.4018/978-1-7998-7979-4.ch005
[12]	B. Goyal, S. Kaur, Specially structured flow shop scheduling models with processing times as trapezoidal fuzzy numbers to optimize waiting time of jobs, in Soft Computing for Problem Solving, Springer, Singapore, (2021), 27–42. https://doi.org/10.1007/978-981-16-2712-5_3
[13]	V. Vinoba, N. Selvamalar, Improved makespan of the branch and bound solution for a fuzzy flow-shop scheduling problem using the maximization operator, Malaya J. Mat., 7 (2019), 91–95. https://doi.org/10.26637/MJM0701/0018 doi: 10.26637/MJM0701/0018
[14]	M. Li, B. Su, D. Lei, A novel imperialist competitive algorithm for fuzzy distributed assembly flow shop scheduling, J. Intell. Fuzzy Syst., 40 (2021), 4545–4561. https://doi.org/10.3233/JIFS-201391 doi: 10.3233/JIFS-201391
[15]	B. Xi, D. Lei, Q-learning-based teaching-learning optimization for distributed two-stage hybrid flow shop scheduling with fuzzy processing time, Complex Syst. Model. Simul., 2 (2022), 113–129. https://doi.org/10.23919/CSMS.2022.0002 doi: 10.23919/CSMS.2022.0002
[16]	J. Li, J. Li, L. Zhang, H. Sang, Y. Han, Q. Chen, Solving type-2 fuzzy distributed hybrid flowshop scheduling using an improved brain storm optimization algorithm, Int. J. Fuzzy Syst., 23 (2021), 1194–1212. https://doi.org/10.1007/S40815-021-01050-9 doi: 10.1007/S40815-021-01050-9
[17]	J. Cai, D. Lei, A cooperated shuffled frog-leaping algorithm for distributed energy-efficient hybrid flow shop scheduling with fuzzy processing time, Complex Intell. Syst., 7 (2021), 2235–2253. https://doi.org/10.1007/S40747-021-00400-2 doi: 10.1007/S40747-021-00400-2
[18]	L. Wang, D. Li, Fuzzy distributed hybrid flow shop scheduling problem with heterogeneous factory and unrelated parallel machine: A shuffled frog leaping algorithm with collaboration of multiple search strategies, IEEE Access, 8 (2020), 214209–214223. https://doi.org/10.1109/ACCESS.2020.3041369 doi: 10.1109/ACCESS.2020.3041369
[19]	J. Cai, R. Zhou, D. Lei, Fuzzy distributed two-stage hybrid flow shop scheduling problem with setup time: collaborative variable search, J. Intell. Fuzzy Syst., 38 (2020), 3189–3199. https://doi.org/10.3233/JIFS-191175 doi: 10.3233/JIFS-191175
[20]	K. Ying, S. Lin, C. Cheng, C. He, Iterated reference greedy algorithm for solving distributed no-idle permutation flowshop scheduling problems, Comput. Ind. Eng., 110 (2017), 413–423. https://doi.org/10.1016/j.cie.2017.06.025 doi: 10.1016/j.cie.2017.06.025
[21]	M. E. Baysal, A. Sarucan, K. Büyüközkan, O. Engin, Distributed fuzzy permutation flow shop scheduling problem: a bee colony algorithm, in International Conference on Intelligent and Fuzzy Systems, Springer, Cham, (2020), 1440–1446. https://doi.org/10.1007/978-3-030-51156-2_167
[22]	J. Lin, Z. Wang, X. Li, A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem, Swarm Evol. Comput., 36 (2017), 124–135. https://doi.org/10.1016/j.swevo.2017.04.007 doi: 10.1016/j.swevo.2017.04.007
[23]	M. E. Baysal, A. Sarucan, K. Büyüközkan, O. Engin, Artificial bee colony algorithm for solving multi-objective distributed fuzzy permutation flow shop problem, J. Intell. Fuzzy Syst., 42 (2022), 439–449. https://doi.org/10.3233/JIFS-219202 doi: 10.3233/JIFS-219202
[24]	K. Wang, Y. Huang, H. Qin, A fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown, J. Oper. Res. Soc., 67 (2016), 68–82. https://doi.org/10.1057/jors.2015.50 doi: 10.1057/jors.2015.50
[25]	Z. Shao, W. Shao, D. Pi, Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem, Swarm Evol. Comput., 59 (2020), 100747. https://doi.org/10.1016/j.swevo.2020.100747 doi: 10.1016/j.swevo.2020.100747
[26]	J. Wang, L. Wang, A cooperative memetic algorithm with feedback for the energy-aware distributed flow-shops with flexible assembly scheduling, Comput. Ind. Eng., 168 (2022), 108126. https://doi.org/10.1016/j.cie.2022.108126 doi: 10.1016/j.cie.2022.108126
[27]	C. Lu, L. Gao, J. Yi, X. Li, Energy-efficient scheduling of distributed flow shop with heterogeneous factories: A real-world case from automobile industry in China, IEEE Trans. Ind. Inf., 17 (2020), 6687–6696. https://doi.org/10.1109/TII.2020.3043734 doi: 10.1109/TII.2020.3043734
[28]	F. Zhao, H. Zhang, L. Wang, A pareto-based discrete jaya algorithm for multiobjective carbon-efficient distributed blocking flow shop scheduling problem, IEEE Trans. Ind. Inf., 2022 (2022), 1–10. https://doi.org/10.1109/TII.2022.3220860 doi: 10.1109/TII.2022.3220860
[29]	F. Zhao, S. Di, L. Wang, A hyperheuristic with q-learning for the multiobjective energy-efficient distributed blocking flow shop scheduling problem, IEEE Trans. Cybern., 2022 (2022), 1–14. https://doi.org/10.1109/TCYB.2022.3192112 doi: 10.1109/TCYB.2022.3192112
[30]	Z. Pan, D. Lei, L. Wang, A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling, IEEE Trans. Cybern., 52 (2022), 5051–5063. https://doi.org/10.1109/TCYB.2020.3026571 doi: 10.1109/TCYB.2020.3026571
[31]	F. Zhao, T. Jiang, L. Wang, A reinforcement learning driven cooperative meta-heuristic algorithm for energy-efficient distributed no-wait flow-shop scheduling with sequence-dependent setup time, IEEE Trans. Ind. Inf., 2022 (2022), 1–12. https://doi.org/10.1109/TII.2022.3218645 doi: 10.1109/TII.2022.3218645
[32]	C. Lu, Q. Liu, B. Zhang, L. Yin, A pareto-based hybrid iterated greedy algorithm for energy-efficient scheduling of distributed hybrid flowshop, Expert Syst. Appl., 204 (2022), 117555. https://doi.org/10.1016/j.eswa.2022.117555 doi: 10.1016/j.eswa.2022.117555
[33]	J. Zheng, L. Wang, J. Wang, A cooperative coevolution algorithm for multi-objective fuzzy distributed hybrid flow shop, Knowledge-Based Syst., 194 (2020), 105536. https://doi.org/10.1016/j.knosys.2020.105536 doi: 10.1016/j.knosys.2020.105536
[34]	W. Zhang, W. Hou, D. Yang, Z. Xing, M. Gen, Multiobjective particle swarm optimization with directional search for distributed permutation flow shop scheduling problem, in International Conference on Bio-Inspired Computing: Theories and Applications, Springer, Singapore, (2019), 164–176. https://doi.org/10.1007/978-981-15-3425-6_14
[35]	S. Chanas, A. Kasperski, On two single machine scheduling problems with fuzzy processing times and fuzzy due dates, Eur. J. Oper. Res., 147 (2003), 281–296. https://doi.org/10.1016/S0377-2217(02)00561-1 doi: 10.1016/S0377-2217(02)00561-1
[36]	M. Sakawa, R. Kubota, Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms, Eur. J. Oper. Res., 120 (2000), 393–407. https://doi.org/10.1016/S0377-2217(99)00094-6 doi: 10.1016/S0377-2217(99)00094-6
[37]	B. Liu, Y. Liu, Expected value of fuzzy variable and fuzzy expected value models, IEEE Trans. Fuzzy Syst., 10 (2002), 445–450. https://doi.org/10.1109/TFUZZ.2002.800692 doi: 10.1109/TFUZZ.2002.800692
[38]	J. J. Palacios, I. G. Rodriguez, C. R. Vela, J. Puente, Robust multiobjective optimisation for fuzzy job shop problems, Appl. Soft Comput., 56 (2017), 604–616. https://doi.org/10.1016/j.asoc.2016.07.004 doi: 10.1016/j.asoc.2016.07.004
[39]	J. D. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms, in Proceedings of the First International Conference of Genetic Algorithms and Their Application, Psychology Press, (1985), 93–100. https://doi.org/10.4324/9781315799674
[40]	W. Zhang, M. Gen, J. Jo, Hybrid sampling strategy-based multiobjective evolutionary algorithm for process planning and scheduling problem, J. Intell. Manuf., 25 (2014), 881–897. https://doi.org/10.1007/s10845-013-0814-2 doi: 10.1007/s10845-013-0814-2
[41]	W. Li, J. Li, K. Gao, Y. Han, B. Niu, Z. Liu, et al., Solving robotic distributed flowshop problem using an improved iterated greedy algorithm, Int. J. Adv. Rob. Syst., 16 (2019), 1729881419879819. https://doi.org/10.1177/1729881419879819 doi: 10.1177/1729881419879819
[42]	W. Xu, Y. Wang, D. Yan, Z. Ji, Flower pollination algorithm for multi-objective fuzzy flexible job shop scheduling, J. Syst. Simul., 30 (2018), 4403. https://doi.org/10.16182/j.issn1004731x.joss.201811042 doi: 10.16182/j.issn1004731x.joss.201811042
[43]	D. Lei, X. Guo, An effective neighborhood search for scheduling in dual-resource constrained interval job shop with environmental objective, Int. J. Prod. Econ., 159 (2015), 296–303. https://doi.org/10.1016/j.ijpe.2014.07.026 doi: 10.1016/j.ijpe.2014.07.026
[44]	W. Zhang, C. Li, M. Gen, W. Yang, Z. Zhang, G. Zhang, Multiobjective particle swarm optimization with direction search and differential evolution for distributed flow-shop scheduling problem, Math. Biosci. Eng., 19 (2022), 8833–8865. https://doi.org/10.3934/mbe.2022410 doi: 10.3934/mbe.2022410

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)