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
PDF (2.3 MB)
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

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

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
Show Author Information

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 shopblockingneighborhood searchiterated greedy algorithm

References

[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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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
Crossref
[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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
Complex System Modeling and Simulation
Volume 3 Issue 4,
December 2023
Pages 282-306
DOI: 10.23919/CSMS.2023.0016
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

502

Views

69

Downloads

9

Crossref

7

Scopus

Altmetrics
Received: 07 June 2023
Revised: 04 July 2023
Accepted: 12 July 2023
Published: 07 December 2023
© The author(s) 2023.

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