AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Complex System Modeling and Simulation Article
View PDF
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Two-Stage Adaptive Memetic Algorithm with Surprisingly Popular Mechanism for Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup Time

School of Computer Science, China University of Geosciences, Wuhan 430074, China
Show Author Information

Abstract

This paper considers the impact of setup time in production scheduling and proposes energy-aware distributed hybrid flow shop scheduling problem with sequence-dependent setup time (EADHFSP-ST) that simultaneously optimizes the makespan and the energy consumption. We develop a mixed integer linear programming model to describe this problem and present a two-stage adaptive memetic algorithm (TAMA) with a surprisingly popular mechanism. First, a hybrid initialization strategy is designed based on the two optimization objectives to ensure the convergence and diversity of solutions. Second, multiple population co-evolutionary approaches are proposed for global search to escape from traditional cross-randomization and to balance exploration and exploitation. Third, considering that the memetic algorithm (MA) framework is less efficient due to the randomness in the selection of local search operators, TAMA is proposed to balance the local and global searches. The first stage accumulates more experience for updating the surprisingly popular algorithm (SPA) model to guide the second stage operator selection and ensures population convergence. The second stage gets rid of local optimization and designs an elite archive to ensure population diversity. Fourth, five problem-specific operators are designed, and non-critical path deceleration and right-shift strategies are designed for energy efficiency. Finally, to evaluate the performance of the proposed algorithm, multiple experiments are performed on a benchmark with 45 instances. The experimental results show that the proposed TAMA can solve the problem effectively.

Keywords

memetic algorithmdistributed hybrid flow shopsetup timemultiple populationenergy-awaresurprisingly popular algorithm

References

[1]

L. Wang, Z. Pan, and J. Wang, A review of reinforcement learning based intelligent optimization for manufacturing scheduling, Complex System Modeling and Simulation, vol. 1, no. 4, pp. 257–270, 2021.
DOI Google Scholar
[2]

M. D. F. Morais, M. H. D. M. Ribeiro, R. G. D. Silva, V. C. Mariani, and L. D. S. Coelho, Discrete differential evolution metaheuristics for permutation flow shop scheduling problems, Comput. Ind. Eng., vol. 166, p. 107956, 2022.
DOI Google Scholar
[3]

Z. Zhang, Z. Shao, W. Shao, J. Chen, and D. Pi, MRLM: A meta-reinforcement learning-based metaheuristic for hybrid flow-shop scheduling problem with learning and forgetting effects, Swarm and Evol. Comput., vol. 85, p. 101479, 2024.
DOI Google Scholar
[4]

Y. Kuang, X. Wu, Z. Chen, and W. Li, A two-stage cross-neighborhood search algorithm bridging different solution representation spaces for solving the hybrid flow shop scheduling problem, Swarm Evol. Comput., vol. 84, p. 101455, 2024.
DOI Google Scholar
[5]

X. Wang, L. Wang, C. Dong, H. Ren, and K. Xing, Reinforcement learning-based dynamic order recommendation for on-demand food delivery, Tsinghua Science and Technology, vol. 29, no. 2, pp. 356–367, 2024.
DOI Google Scholar
[6]

C. Lu, L. Gao, J. Yi, and 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., vol. 17, no. 10, pp. 6687–6696, 2021.
DOI Google Scholar
[7]

G. Zhang, B. Liu, L. Wang, and K. Xing, Distributed heterogeneous co-evolutionary algorithm for scheduling a multistage fine-manufacturing system with setup constraints, IEEE Trans. Cybern., vol. 54, no. 3, pp. 1497–1510, 2024.
DOI Google Scholar
[8]

Y. Pan, K. Gao, Z. Li, and N. Wu, Solving biobjective distributed flow-shop scheduling problems with lot-streaming using an improved jaya algorithm, IEEE Trans. Cybern., vol. 53, no. 6, pp. 3818–3828, 2023.
DOI Google Scholar
[9]
L. Meng, Y. Ren, B. Zhang, J. Q. Li, H. Sang, and C. Zhang, MILP modeling and optimization of energy- efficient distributed flexible job shop scheduling problem, IEEE Access, vol. 8, pp. 191191–191203, 2020.
DOI
[10]

G. Wang, X. Li, L. Gao, and P. Li, Energy-efficient distributed heterogeneous welding flow shop scheduling problem using a modified MOEA/D, Swarm Evol. Comput., vol. 62, p. 100858, 2021.
DOI Google Scholar
[11]

C. Lu, Y. Huang, L. Meng, L. Gao, B. Zhang, and J. Zhou, A Pareto-based collaborative multi-objective optimization algorithm for energy-efficient scheduling of distributed permutation flow-shop with limited buffers, Robot. Comput. Integr. Manuf., vol. 74, p. 102277, 2022.
DOI Google Scholar
[12]
K. C. Ying and S. W. Lin, Minimizing makespan for the distributed hybrid flowshop scheduling problem with multiprocessor tasks, Expert Syst. Appl., vol. 92, no. C, pp. 132–141, 2018.
DOI
[13]

H. Liu, F. Zhao, L. Wang, J. Cao, J. Tang, and Jonrinaldi, An estimation of distribution algorithm with multiple intensification strategies for two-stage hybrid flow-shop scheduling problem with sequence-dependent setup time, Appl. Intell., vol. 53, no. 5, pp. 5160–5178, 2023.
DOI Google Scholar
[14]

L. Shen, S. Dauzère-Pérès, and J. S. Neufeld, Solving the flexible job shop scheduling problem with sequence-dependent setup times, Eur. J. Oper. Res., vol. 265, no. 2, pp. 503–516, 2018.
DOI Google Scholar
[15]

B. Wang, K. Feng, and X. Wang, Bi-objective scenario-guided swarm intelligent algorithms based on reinforcement learning for robust unrelated parallel machines scheduling with setup times, Swarm Evol. Comput., vol. 80, p. 101321, 2023.
DOI Google Scholar
[16]
F. Zhao, Z. Wang, and L. Wang, A reinforcement learning driven artificial bee colony algorithm for distributed heterogeneous No-wait flowshop scheduling problem with sequence-dependent setup times, IEEE Trans. Automat. Sci. Eng., vol. 20, no. 4, pp. 2305–2320, 2023.
DOI
[17]

F. B. Ozsoydan and M. Sağir, Iterated greedy algorithms enhanced by hyper-heuristic based learning for hybrid flexible flowshop scheduling problem with sequence dependent setup times: A case study at a manufacturing plant, Comput. Oper. Res., vol. 125, p. 105044, 2021.
DOI Google Scholar
[18]

X. Ma, Y. Fu, K. Gao, L. Zhu, and A. Sadollah, A multi-objective scheduling and routing problem for home health care services via brain storm optimization, Complex System Modeling and Simulation., vol. 3, no. 1, pp. 32–46, 2023.
DOI Google Scholar
[19]

R. Li, W. Gong, and C. Lu, Self-adaptive multi-objective evolutionary algorithm for flexible job shop scheduling with fuzzy processing time, Comput. Ind. Eng., vol. 168, p. 108099, 2022.
DOI Google Scholar
[20]

E. Jiang, L. Wang, and J. Wang, Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks, Tsinghua Science and Technology, vol. 26, no. 5, pp. 646–663, 2021.
DOI Google Scholar
[21]
J. J. Wang and L. Wang, A cooperative memetic algorithm with learning-based agent for energy-aware distributed hybrid flow-shop scheduling, IEEE Trans. Evol. Computat., vol. 26, no. 3, pp. 461–475, 2022.
DOI
[22]
J. Q. Li, J. W. Deng, C. Y. Li, Y. Y. Han, J. Tian, B. Zhang, and C. G. Wang, An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times, Knowl. Based Syst., vol. 200, p. 106032, 2020.
DOI
[23]
J. Q. Li, H. Y. Sang, Y. Y. Han, C. G. Wang, and K. Z. Gao, Efficient multi-objective optimization algorithm for hybrid flow shop scheduling problems with setup energy consumptions, J. Clean. Prod., vol. 181, pp. 584–598, 2018.
DOI
[24]

S. Wu and L. Liu, Green hybrid flow shop scheduling problem considering sequence dependent setup times and transportation times, IEEE Access, vol. 11, pp. 39726–39737, 2023.
DOI Google Scholar
[25]

W. Gong, Z. Liao, X. Mi, L. Wang, and Y. Guo, Nonlinear equations solving with intelligent optimization algorithms: A survey, Complex System Modeling and Simulation, vol. 1, no. 1, pp. 15–32, 2021.
DOI Google Scholar
[26]

Y. Han, D. Gong, Y. Jin, and Q. Pan, Evolutionary multiobjective blocking lot-streaming flow shop scheduling with machine breakdowns, IEEE Trans. Cybern., vol. 49, no. 1, pp. 184–197, 2019.
DOI Google Scholar
[27]

C. Luo, W. Gong, R. Li, and C. Lu, Problem-specific knowledge MOEA/D for energy-efficient scheduling of distributed permutation flow shop in heterogeneous factories, Eng. Appl. Artif. Intell., vol. 123, p. 106454, 2023.
DOI Google Scholar
[28]
J. J. Wang and L. Wang, A Bi-population cooperative memetic algorithm for distributed hybrid flow-shop scheduling, IEEE Trans. Emerg. Top. Comput. Intell., vol. 5, no. 6, pp. 947–961, 2021.
DOI
[29]

A. M. Akwasi, X. Wei, and O. A. Duku, Observer controller-based structure for a modified flower pollination algorithm for wind power generation, Int. J. Autom. Contr., vol. 18, no. 1, pp. 53–86, 2024.
DOI Google Scholar
[30]

C. Luo, W. Gong, and C. Lu, Knowledge-driven two-stage memetic algorithm for energy-efficient flexible job shop scheduling with machine breakdowns, Expert Syst. Appl., vol. 235, p. 121149, 2024.
DOI Google Scholar
[31]

F. Ming, W. Gong, H. Zhen, S. Li, L. Wang, and Z. Liao, A simple two-stage evolutionary algorithm for constrained multi-objective optimization, Knowl. Based Syst., vol. 228, p. 107263, 2021.
DOI Google Scholar
[32]

F. Ming, W. Gong, and L. Wang, A two-stage evolutionary algorithm with balanced convergence and diversity for many-objective optimization, IEEE Trans. Syst. Man Cybern, Syst., vol. 52, no. 10, pp. 6222–6234, 2022.
DOI Google Scholar
[33]

R. Li, W. Gong, L. Wang, C. Lu, and S. Jiang, Two-stage knowledge-driven evolutionary algorithm for distributed green flexible job shop scheduling with type-2 fuzzy processing time, Swarm Evol. Comput., vol. 74, p. 101139, 2022.
DOI Google Scholar
[34]

F. Zhao, X. He, and L. Wang, A two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of no-wait flow-shop problem, IEEE Trans. Cybern., vol. 51, no. 11, pp. 5291–5303, 2021.
DOI Google Scholar
[35]

R. Li, W. Gong, C. Lu, and L. Wang, A learning-based memetic algorithm for energy-efficient flexible job-shop scheduling with type-2 fuzzy processing time, IEEE Trans. Evol. Comput., vol. 27, no. 3, pp. 610–620, 2023.
DOI Google Scholar
[36]

R. Li, W. Gong, and C. Lu, A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible job shop scheduling, Expert Syst. Appl., vol. 203, p. 117380, 2022.
DOI Google Scholar
[37]

F. Zhao, R. Ma, and L. Wang, A self-learning discrete Jaya algorithm for multiobjective energy-efficient distributed No-idle flow-shop scheduling problem in heterogeneous factory system, IEEE Trans. Cybern., vol. 52, no. 12, pp. 12675–12686, 2022.
DOI Google Scholar
[38]

R. Li, W. Gong, L. Wang, C. Lu, and X. Zhuang, Surprisingly popular-based adaptive memetic algorithm for energy-efficient distributed flexible job shop scheduling, IEEE Trans. Cybern., vol. 53, no. 12, pp. 8013–8023, 2023.
DOI Google Scholar
[39]
W. Wang, Improved simulated annealing algorithm for the scheduling of hybrid flow-shop problem, in Proc. 3 rd Int. Conf. Computer Vision, Image and Deep Learning & Int. Conf. Computer Engineering and Applications (CVIDL & ICCEA), Changchun, China, 2022, pp. 1176–1179.
DOI
[40]
H. Chen, Z. Fang, and C. Zhong, Research on hybrid flow-shop scheduling based on improved genetic algorithm, in Proc. IEEE 18 th Conf. Industrial Electronics and Applications (ICIEA), Ningbo, China, 2023, pp. 1315–1320.
DOI
[41]

W. Shao, Z. Shao, and D. Pi, Modeling and multi-neighborhood iterated greedy algorithm for distributed hybrid flow shop scheduling problem, Knowl. Based Syst., vol. 194, p. 105527, 2020.
DOI Google Scholar
[42]
J. Q. Li, X. L. Chen, P. Y. Duan, and J. H. Mou, KMOEA: A knowledge-based multiobjective algorithm for distributed hybrid flow shop in a prefabricated system, IEEE Trans. Ind. Inf., vol. 18, no. 8, pp. 5318–5329, 2022.
DOI
[43]

J. Cai, R. Zhou, and D. Lei, Fuzzy distributed two-stage hybrid flow shop scheduling problem with setup time: Collaborative variable search, J. Intell. Fuzzy Syst., vol. 38, no. 3, pp. 3189–3199, 2020.
DOI Google Scholar
[44]

D. Prelec, H. S. Seung, and J. McCoy, A solution to the single-question crowd wisdom problem, Nature, vol. 541, no. 7638, pp. 532–535, 2017.
DOI Google Scholar
[45]
Q. Cui, C. Tang, G. Xu, C. Wu, X. Shi, Y. Liang, L. Chen, H. P. Lee, and H. Huang, Surprisingly popular algorithm-based comprehensive adaptive topology learning PSO, in Proc. IEEE Cong. Evolutionary Computation (CEC). Wellington, New Zealand, 2019, pp. 2603–2610.
DOI
[46]

D. L. Santos, J. L. Hunsucker, and D. E. Deal, Global lower bounds for flow shops with multiple processors, Eur. J. Oper. Res., vol. 80, no. 1, pp. 112–120, 1995.
DOI Google Scholar
[47]

L. Hidri and M. Haouari, Bounding strategies for the hybrid flow shop scheduling problem, Appl. Math. Comput., vol. 217, no. 21, pp. 8248–8263, 2011.
DOI Google Scholar
[48]
J. J. Wang and L. Wang, A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop, IEEE Trans. Syst. Man Cybern, Syst., vol. 50, no. 5, pp. 1805–1819, 2020.
DOI
[49]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Computat., vol. 6, no. 2, pp. 182–197, 2002.
DOI Google Scholar
[50]

M. Abedi, R. Chiong, N. Noman, and R. Zhang, A multi-population, multi-objective memetic algorithm for energy-efficient job-shop scheduling with deteriorating machines, Expert Syst. Appl., vol. 157, p. 113348, 2020.
DOI Google Scholar
[51]

B. Naderi and R. Ruiz, The distributed permutation flowshop scheduling problem, Comput. Oper. Res., vol. 37, no. 4, pp. 754–768, 2010.
DOI Google Scholar
[52]

C. Yu, P. Andreotti, and Q. Semeraro, Multi-objective scheduling in hybrid flow shop: Evolutionary algorithms using multi-decoding framework, Comput. Ind. Eng., vol. 147, p. 106570, 2020.
DOI Google Scholar
[53]

F. Zhao, H. Liu, Y. Zhang, W. Ma, and C. Zhang, A discrete Water Wave Optimization algorithm for no-wait flow shop scheduling problem, Expert Syst. Appl., vol. 91, no. C, pp. 347–363, 2018.
DOI Google Scholar
[54]
Q. K. Pan, L. Wang, J. Q. Li, and J. H. Duan, A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation, Omega, vol. 45, pp. 42–56, 2014.
DOI
[55]

Z. Hong, Z. Zeng, and L. Gao, Energy-efficiency scheduling of multi-cell manufacturing system considering total handling distance and eligibility constraints, Comput. Ind. Eng., vol. 151, p. 106998, 2021.
DOI Google Scholar
[56]

H. Gholami and H. Sun, Toward automated algorithm configuration for distributed hybrid flow shop scheduling with multiprocessor tasks, Knowl. Based Syst., vol. 264, p. 110309, 2023.
DOI Google Scholar
[57]

L. While, P. Hingston, L. Barone, and S. Huband, A faster algorithm for calculating hypervolume, IEEE Trans. Evol. Computat., vol. 10, no. 1, pp. 29–38, 2006.
DOI Google Scholar
[58]

R. Zhang and R. Chiong, Solving the energy-efficient job shop scheduling problem: A multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption, J. Clean. Prod., vol. 112, pp. 3361–3375, 2016.
DOI Google Scholar
[59]

B. Wu, T. Yuan, Y. Qi, and M. Dong, Public opinion dissemination with incomplete information on social network: A study based on the infectious diseases model and game theory, Complex System Modeling and Simulation, vol. 1, no. 2, pp. 109–121, 2021.
DOI Google Scholar
[60]

S. Tian, C. Zhang, J. Fan, X. Li, and L. Gao, A genetic algorithm with critical path-based variable neighborhood search for distributed assembly job shop scheduling problem, Swarm Evol. Comput., vol. 85, p. 101485, 2024.
DOI Google Scholar
[61]
E. Zitzler, M. Laumanns, and L. Thiele, SPEA2: Improving the Strength Pareto Evolutionary Algorithm, TIK-Report.
[62]

Q. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Computat., vol. 11, no. 6, pp. 712–731, 2007.
DOI Google Scholar
[63]

Y. Tian, R. Cheng, X. Zhang, F. Cheng, and Y. Jin, An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility, IEEE Trans. Evol. Computat., vol. 22, no. 4, pp. 609–622, 2018.
DOI Google Scholar
Complex System Modeling and Simulation
Volume 4 Issue 1,
March 2024
Pages 82-108
DOI: 10.23919/CSMS.2024.0003
Cite this article:
Chen F, Luo C, Gong W, et al. Two-Stage Adaptive Memetic Algorithm with Surprisingly Popular Mechanism for Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup Time. Complex System Modeling and Simulation, 2024, 4(1): 82-108. https://doi.org/10.23919/CSMS.2024.0003

120

Views

21

Downloads

0

Crossref

0

Scopus

Altmetrics
Received: 15 February 2024
Accepted: 19 March 2024
Published: 30 March 2024
© The author(s) 2024.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return