Journal Home > Volume 3 , Issue 4
Complex System Modeling and Simulation 2023, 3(4): 282-306 https://doi.org/10.23919/CSMS.2023.0016
Open Access | Issue | Published: 07 December 2023

Intelligent Optimization Under Multiple Factories: Hybrid FlowShop Scheduling Problem with Blocking ConstraintsUsing an Advanced Iterated Greedy Algorithm

Show Author's Information Yong Wang1,  Yuting Wang1( ),  Yuyan Han1( ),  Junqing Li2,  Kaizhou Gao3,  Yusuke Nojima4
School of Computer Science, Liaocheng University, Liaocheng 252000, China
School of Computer Science, Shandong Normal University, Jinan 252000, China
Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China
Department of Computer Science and Intelligent Systems, Osaka Prefecture University, Osaka 599-8531, Japan
Keywords:
distributed hybrid flow shop, blocking, neighborhood search, iterated greedy algorithm
Cite this article:
Wang Y, Wang Y, Han Y, et al. Intelligent Optimization Under Multiple Factories: Hybrid FlowShop Scheduling Problem with Blocking ConstraintsUsing an Advanced Iterated Greedy Algorithm. Complex System Modeling and Simulation, 2023, 3(4): 282-306. https://doi.org/10.23919/CSMS.2023.0016
Download citation
EndNote(RIS)
BibTeX

328

Views

61

Downloads

Citations

0

Crossref

N/A

WoS

0

Scopus

N/A

CSCD

Abstract Full text About this article

The distributed hybrid flow shop scheduling problem (DHFSP), which integrates distributed manufacturing models with parallel machines, has gained significant attention. However, in actual scheduling, some adjacent machines do not have buffers between them, resulting in blocking. This paper focuses on addressing the DHFSP with blocking constraints (DBHFSP) based on the actual production conditions. To solve DBHFSP, we construct a mixed integer linear programming (MILP) model for DBHFSP and validate its correctness using the Gurobi solver. Then, an advanced iterated greedy (AIG) algorithm is designed to minimize the makespan, in which we modify the Nawaz, Enscore, and Ham (NEH) heuristic to solve blocking constraints. To balance the global and local search capabilities of AIG, two effective inter-factory neighborhood search strategies and a swap-based local search strategy are designed. Additionally, each factory is mutually independent, and the movement within one factory does not affect the others. In view of this, we specifically designed a memory-based decoding method for insertion operations to reduce the computation time of the objective. Finally, two shaking strategies are incorporated into the algorithm to mitigate premature convergence. Five advanced algorithms are used to conduct comparative experiments with AIG on 80 test instances, and experimental results illustrate that the makespan and the relative percentage increase (RPI) obtained by AIG are 1.0% and 86.1%, respectively, better than the comparative algorithms.


menu
Abstract
Full text
Outline
About this article

Intelligent Optimization Under Multiple Factories: Hybrid FlowShop Scheduling Problem with Blocking ConstraintsUsing an Advanced Iterated Greedy Algorithm

Show Author's information Yong Wang1, Yuting Wang1( ), Yuyan Han1( ), Junqing Li2, Kaizhou Gao3, Yusuke Nojima4
School of Computer Science, Liaocheng University, Liaocheng 252000, China
School of Computer Science, Shandong Normal University, Jinan 252000, China
Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China
Department of Computer Science and Intelligent Systems, Osaka Prefecture University, Osaka 599-8531, Japan

Abstract

The distributed hybrid flow shop scheduling problem (DHFSP), which integrates distributed manufacturing models with parallel machines, has gained significant attention. However, in actual scheduling, some adjacent machines do not have buffers between them, resulting in blocking. This paper focuses on addressing the DHFSP with blocking constraints (DBHFSP) based on the actual production conditions. To solve DBHFSP, we construct a mixed integer linear programming (MILP) model for DBHFSP and validate its correctness using the Gurobi solver. Then, an advanced iterated greedy (AIG) algorithm is designed to minimize the makespan, in which we modify the Nawaz, Enscore, and Ham (NEH) heuristic to solve blocking constraints. To balance the global and local search capabilities of AIG, two effective inter-factory neighborhood search strategies and a swap-based local search strategy are designed. Additionally, each factory is mutually independent, and the movement within one factory does not affect the others. In view of this, we specifically designed a memory-based decoding method for insertion operations to reduce the computation time of the objective. Finally, two shaking strategies are incorporated into the algorithm to mitigate premature convergence. Five advanced algorithms are used to conduct comparative experiments with AIG on 80 test instances, and experimental results illustrate that the makespan and the relative percentage increase (RPI) obtained by AIG are 1.0% and 86.1%, respectively, better than the comparative algorithms.

Keywords: distributed hybrid flow shop, blocking, neighborhood search, iterated greedy algorithm

References(49)

[1]

Z. Shao, W. Shao, and D. Pi, Effective heuristics and metaheuristics for the distributed fuzzy blocking flow-shop scheduling problem, Swarm Evol. Comput., vol. 59, p. 100747, 2020.
DOI Google Scholar
[2]
Q. -K. Pan, L. Gao, L. Wang, J. Liang, and X. -Y. Li, Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem, Expert Syst. Appl., vol. 124, pp. 309–324, 2019.
DOI
[3]
Y. -D. Kim, S. -O. Shim, B. Choi, and H. Hwang, Simplification methods for accelerating simulation-based real-time scheduling in a semiconductor wafer fabrication facility, IEEE Trans. Semicond. Manuf., vol. 16, no. 2, pp. 290–298, 2003.
DOI
[4]

M. K. Marichelvam, T. Prabaharan, and X. S. Yang, A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems, IEEE Trans. Evol. Comput., vol. 18, no. 2, pp. 301–305, 2014.
DOI Google Scholar
[5]
K. Peng, Q. -K. Pan, L. Gao, B. Zhang, and X. Pang, An improved artificial bee colony algorithm for real-world hybrid flowshop rescheduling in steelmaking-refining-continuous casting process, Comput. Ind. Eng., vol. 122, pp. 235–250, 2018.
DOI
[6]

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
[7]

Y. Li, X. Li, L. Gao, and L. Meng, An improved artificial bee colony algorithm for distributed heterogeneous hybrid flowshop scheduling problem with sequence-dependent setup times, Comput. Ind. Eng., vol. 147, p. 106638, 2020.
DOI Google Scholar
[8]
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
[9]

M. K. Marichelvam, M. Geetha, and Ö. Tosun, An improved particle swarm optimization algorithm to solve hybrid flowshop scheduling problems with the effect of human factors–a case study, Comput. Oper. Res., vol. 114, p. 104812, 2020.
DOI Google Scholar
[10]

G. Zhang, K. Xing, and F. Cao, Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion, Eng. Appl. Artif. Intell., vol. 76, pp. 96–107, 2018.
DOI Google Scholar
[11]

V. Fernandez-Viagas, P. Perez-Gonzalez, and J. M. Framinan, The distributed permutation flow shop to minimise the total flowtime, Comput. Ind. Eng., vol. 118, pp. 464–477, 2018.
DOI Google Scholar
[12]

R. Ruiz and T. Stützle, A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, Eur. J. Oper. Res., vol. 177, no. 3, pp. 2033–2049, 2007.
DOI Google Scholar
[13]
R. Ruiz, Q. -K. Pan, and B. Naderi, Iterated greedy methods for the distributed permutation flowshop scheduling problem, Omega, vol. 83, pp. 213–222, 2019.
DOI
[14]
H. Öztop, M. F. Tasgetiren, D. T. Eliiyi, and Q. -K. Pan, Metaheuristic algorithms for the hybrid flowshop scheduling problem, Comput. Oper. Res., vol. 111, pp. 177–196, 2019.
DOI
[15]
S. -Y. Wang and L. Wang, An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem, IEEE Trans. Syst. Man Cybern.: Syst., vol. 46, no. 1, pp. 139–149, 2016.
DOI
[16]
J. Wang, L. Wang, and J. Shen, A hybrid discrete cuckoo search for distributed permutation flowshop scheduling problem, in Proc. 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, Canada, 2016, pp. 2240–2246.
DOI
[17]

W. Shao, D. Pi, and Z. Shao, Optimization of makespan for the distributed no-wait flow shop scheduling problem with iterated greedy algorithms, Knowl. Based Syst., vol. 137, pp. 163–181, 2017.
DOI Google Scholar
[18]

F. Zhao, L. Zhang, J. Cao, and J. Tang, A cooperative water wave optimization algorithm with reinforcement learning for the distributed assembly no-idle flowshop scheduling problem, Comput. Ind. Eng., vol. 153, p. 107082, 2021.
DOI Google Scholar
[19]
J. -J. Wang and L. Wang, A cooperative memetic algorithm with feedback for the energy-aware distributed flow-shops with flexible assembly scheduling, Comput. Ind. Eng., vol. 168, p. 108126, 2022.
DOI
[20]

F. Zhao, T. Jiang, and 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., vol. 19, no. 7, pp. 8427–8440, 2023.
DOI Google Scholar
[21]
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
[22]
S. -Y. Wang, L. Wang, M. Liu, and Y. Xu, An enhanced estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machines, Int. J. Adv. Manuf. Technol., vol. 68, no. 9, pp. 2043–2056, 2013.
DOI
[23]

M. Li, D. Lei, and J. Cai, Two-level imperialist competitive algorithm for energy-efficient hybrid flow shop scheduling problem with relative importance of objectives, Swarm Evol. Comput., vol. 49, pp. 34–43, 2019.
DOI Google Scholar
[24]

X. Wu, Z. Cao, and S. Wu, Real-time hybrid flow shop scheduling approach in smart manufacturing environment, Complex System Modeling and Simulation, vol. 1, no. 4, pp. 335–350, 2021.
DOI Google Scholar
[25]
K. -C. Ying and S. -W. Lin, Minimizing makespan for the distributed hybrid flowshop scheduling problem with multiprocessor tasks, Expert Syst. Appl., vol. 92, pp. 132–141, 2018.
DOI
[26]

B. Xi and D. Lei, Q-learning-based teaching-learning optimization for distributed two-stage hybrid flow shop scheduling with fuzzy processing time, Complex System Modeling and Simulation, vol. 2, no. 2, pp. 113–129, 2022.
DOI Google Scholar
[27]
J. Zheng, L. Wang, and J. -J. Wang, A cooperative coevolution algorithm for multi-objective fuzzy distributed hybrid flow shop, Knowl. Based Syst., vol. 194, p. 105536, 2020.
DOI
[28]

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
[29]
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. Comput., vol. 26, no. 3, pp. 461–475, 2022.
DOI
[30]

Z. Pan, D. Lei, and L. Wang, A knowledge-based two-population optimization algorithm for distributed energy-efficient parallel machines scheduling, IEEE Trans. Cybern., vol. 52, no. 6, pp. 5051–5063, 2022.
DOI Google Scholar
[31]

W. Shao, Z. Shao, and D. Pi, A network memetic algorithm for energy and labor-aware distributed heterogeneous hybrid flow shop scheduling problem, Swarm Evol. Comput., vol. 75, p. 101190, 2022.
DOI Google Scholar
[32]

Q. Zhang and Z. Yu, Population-based multi-layer iterated greedy algorithm for solving blocking flow shop scheduling problem, (in Chinese), Comput. Integrated Manufacturing Syst., vol. 22, no. 10, pp. 2315–2322, 2016.
Google Scholar
[33]

Y. Zheng, G. Mo, and J. Zhang, Blocking flow line scheduling of panel block in shipbuilding, (in Chinese), Comput. Integrated Manufacturing Syst., vol. 22, no. 10, pp. 2305–2314, 2016.
Google Scholar
[34]

V. Riahi, M. A. H. Newton, K. Su, and A. Sattar, Constraint guided accelerated search for mixed blocking permutation flowshop scheduling, Comput. Oper. Res., vol. 102, pp. 102–120, 2019.
DOI Google Scholar
[35]

Y. Han, J. Li, H. Sang, Y. Liu, K. Gao, and Q. Pan, Discrete evolutionary multi-objective optimization for energy-efficient blocking flow shop scheduling with setup time, Appl. Soft Comput., vol. 93, p. 106343, 2020.
DOI Google Scholar
[36]

S. Aqil and K. Allali, Two efficient nature inspired meta-heuristics solving blocking hybrid flow shop manufacturing problem, Eng. Appl. Artif. Intell., vol. 100, p. 104196, 2021.
DOI Google Scholar
[37]

X. Han, Y. Han, B. Zhang, H. Qin, J. Li, Y. Liu, and D. Gong, An effective iterative greedy algorithm for distributed blocking flowshop scheduling problem with balanced energy costs criterion, Appl. Soft Comput., vol. 129, p. 109502, 2022.
DOI Google Scholar
[38]
H. -X. Qin, Y. -Y. Han, B. Zhang, L. -L. Meng, Y. -P. Liu, Q. -K. Pan, and D. -W. Gong, An improved iterated greedy algorithm for the energy-efficient blocking hybrid flow shop scheduling problem, Swarm Evol. Comput., vol. 69, p. 100992, 2022.
DOI
[39]

F. Zhao, H. Zhang, and L. Wang, A pareto-based discrete jaya algorithm for multiobjective carbon-efficient distributed blocking flow shop scheduling problem, IEEE Trans. Ind. Inform., vol. 19, no. 8, pp. 8588–8599, 2023.
DOI Google Scholar
[40]

F. Zhao, S. Di, and L. Wang, A hyperheuristic with Q-learning for the multiobjective energy-efficient distributed blocking flow shop scheduling problem, IEEE Trans. Cybern., vol. 53, no. 5, pp. 3337–3350, 2023.
DOI Google Scholar
[41]

V. Fernandez-Viagas, J. M. S. Valente, and J. M. Framinan, Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimise total tardiness, Expert Syst. Appl., vol. 94, pp. 58–69, 2018.
DOI Google Scholar
[42]

Y. Wang, X. Li, R. Ruiz, and S. Sui, An iterated greedy heuristic for mixed no-wait flowshop problems, IEEE Trans. Cybern., vol. 48, no. 5, pp. 1553–1566, 2018.
DOI Google Scholar
[43]

X. Han, Y. Han, Q. Chen, J. Li, H. Sang, Y. Liu, Q. Pan, and Y. Nojima, Distributed flow shop scheduling with sequence-dependent setup times using an improved iterated greedy algorithm, Complex System Modeling and Simulation, vol. 1, no. 3, pp. 198–217, 2021.
DOI Google Scholar
[44]
S. Chen, Q. -K. Pan, L. Gao, and H. -Y. Sang, A population-based iterated greedy algorithm to minimize total flowtime for the distributed blocking flowshop scheduling problem, Eng. Appl. Artif. Intell., vol. 104, p. 104375, 2021
DOI
[45]
H. -X. Qin, Y. -Y. Han, Y. -P. Liu, J. -Q. Li, and Q. -K. Pan, A collaborative iterative greedy algorithm for the scheduling of distributed heterogeneous hybrid flow shop with blocking constraints, Expert Syst. Appl., vol. 201, p. 117256, 2022.
DOI
[46]

L. Meng, K. Gao, Y. Ren, B. Zhang, H. Sang, and C. Zhang, Novel MILP and CP models for distributed hybrid flowshop scheduling problem with sequence-dependent setup times, Swarm Evol. Comput., vol. 71, p. 101058, 2022.
DOI Google Scholar
[47]

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
[48]

B. Naderi and R. Ruiz, A scatter search algorithm for the distributed permutation flowshop scheduling problem, Eur. J. Oper. Res., vol. 239, no. 2, pp. 323–334, 2014.
DOI Google Scholar
[49]
J. -P. Huang, Q. -K. Pan, and L. Gao, An effective iterated greedy method for the distributed permutation flowshop scheduling problem with sequence-dependent setup times, Swarm Evol. Comput., vol. 59, p. 100742, 2020.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 07 June 2023
Revised: 04 July 2023
Accepted: 12 July 2023
Published: 07 December 2023
Issue date: December 2023

Copyright

© The author(s) 2023.

Acknowledgements

Acknowledgment

This work was jointly supported by the National Natural Science Foundation of Shandong Province (No. ZR2023MF022); National Natural Science Foundation of China (Nos. 61973203, 62173216, and 62173356); and Guangyue Youth Scholar Innovation Talent Program Support from Liaocheng University (No. LCUGYTD2022-03).

Rights and permissions

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