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 Computers, Materials & Continua Article
PDF (886.3 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Article | Open Access

Q-Learning-Assisted Meta-Heuristics for Scheduling Distributed Hybrid Flow Shop Problems

Qianyao Zhu1, Kaizhou Gao1( ), Wuze Huang1, Zhenfang Ma1, Adam Slowik2
Institute of Systems Engineering, Macau University of Science and Technology, Macau, 99078, China
Department of Electronics and Computer Science, Koszalin University of Technology, Koszalin, 75-453, Poland
Show Author Information

Abstract

The flow shop scheduling problem is important for the manufacturing industry. Effective flow shop scheduling can bring great benefits to the industry. However, there are few types of research on Distributed Hybrid Flow Shop Problems (DHFSP) by learning assisted meta-heuristics. This work addresses a DHFSP with minimizing the maximum completion time (Makespan). First, a mathematical model is developed for the concerned DHFSP. Second, four Q-learning-assisted meta-heuristics, e.g., genetic algorithm (GA), artificial bee colony algorithm (ABC), particle swarm optimization (PSO), and differential evolution (DE), are proposed. According to the nature of DHFSP, six local search operations are designed for finding high-quality solutions in local space. Instead of random selection, Q-learning assists meta-heuristics in choosing the appropriate local search operations during iterations. Finally, based on 60 cases, comprehensive numerical experiments are conducted to assess the effectiveness of the proposed algorithms. The experimental results and discussions prove that using Q-learning to select appropriate local search operations is more effective than the random strategy. To verify the competitiveness of the Q-learning assistedmeta-heuristics, they are compared with the improved iterated greedy algorithm (IIG), which is also for solving DHFSP. The Friedman test is executed on the results by five algorithms. It is concluded that the performance of four Q-learning-assisted meta-heuristics are better than IIG, and the Q-learning-assisted PSO shows the best competitiveness.

Keywords

Distributed schedulinghybrid flow shopmeta-heuristicslocal searchQ-learning

References

[1]

B. T. Wang, Q. -K. Pan, L. Gao, Z. -H. Miao, and H. -Y. Sang, “Modeling and scheduling a constrained flowshop in distributed manufacturing environments,” J. Manuf. Syst., vol. 72, pp. 519–535, 2024.
Crossref Google Scholar
[2]

S. Wang, X. Li, L. Gao, and J. Li, “A multi-disjunctive-graph model-based memetic algorithm for the distributed job shop scheduling problem,” Adv. Eng. Inform., vol. 60, 2024, Art. no. 102401. doi: 10.1016/j.aei.2024.102401.
Crossref Google Scholar
[3]

A. M. Fathollahi-Fard, L. Woodward, and O. Akhrif, “A distributed permutation flow-shop considering sustainability criteria and real-time scheduling,” J. Ind. Inf. Integr., vol. 39, 2024, Art. no. 100598. doi: 10.1016/j.jii.2024.100598.
Crossref Google Scholar
[4]

D. Lei, J. Zhang, and H. Liu, “An adaptive two-class teaching-learning-based optimization for energy-efficient hybrid flow shop scheduling problems with additional resources,” Symmetry, vol. 16, no. 2, 2024, Art. no. 203. doi: 10.3390/sym16020203.
Crossref Google Scholar
[5]

M. Geetha, R. Chandra Guru Sekar, M. K. Marichelvam, and Ö. Tosun, “A sequential hybrid optimization algorithm (SHOA) to solve the hybrid flow shop scheduling problems to minimize carbon footprint,” Processes, vol. 12, no. 1, 2024, Art. no. 143. doi: 10.3390/pr12010143.
Crossref Google Scholar
[6]

C. -C. Lin, Y. -C. Peng, Y. -S. Chang, and C. -H. Chang, “Reentrant hybrid flow shop scheduling with stockers in automated material handling systems using deep reinforcement learning,” Comput. Indus. Eng., vol. 189, no. 3, 2024, Art. no. 109995. doi: 10.1016/j.cie.2024.109995.
Crossref Google Scholar
[7]

O. Moursli and Y. Pochet, “A branch-and-bound algorithm for the hybrid flowshop,” Int. J. Prod. Econ., vol. 64, pp. 113–125, 2000. doi: 10.1016/S0925-5273(99)00051-1.
Crossref Google Scholar
[8]

L. Hidri and A. Gharbi, “New efficient lower bound for the hybrid flow shop scheduling problem with multiprocessor tasks,” IEEE Access, vol. 5, pp. 6121–6133, 2017. doi: 10.1109/ACCESS.2017.2696118.
Crossref Google Scholar
[9]

B. Khurshid, S. Maqsood, Y. Khurshid, K. Naeem, and Q. S. Khalid, “A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems,” Sci. Rep., vol. 14, no. 1, 2024, Art. no. 2376. doi: 10.1038/s41598-023-47729-x.
Crossref Google Scholar
[10]

M. Y. Wang, S. P. Sethi, and S. L. van de Velde, “Minimizing makespan in a class of reentrant shops,” Oper. Res., vol. 45, no. 5, pp. 702–712, 1997. doi: 10.1287/opre.45.5.702.
Crossref Google Scholar
[11]

Y. Zhu, Q. Tang, L. Cheng, L. Zhao, G. Jiang and Y. Lu, “Solving multi-objective hybrid flowshop lot-streaming scheduling with consistent and limited sub-lots via a knowledge-based memetic algorithm,” J. Manuf. Syst., vol. 73, no. 5, pp. 106–125, 2024. doi: 10.1016/j.jmsy.2024.01.006.
Crossref Google Scholar
[12]

Z. Shao, W. Shao, J. Chen, and D. Pi, “A feedback learning-based selection hyper-heuristic for distributed heterogeneous hybrid blocking flow-shop scheduling problem with flexible assembly and setup time,” Eng. Appl. Artif. Intell., vol. 131, no. 4, 2024, Art. no. 107818. doi: 10.1016/j.engappai.2023.107818.
Crossref Google Scholar
[13]

G. Ziadlou, S. Emami, and E. Asadi-Gangraj, “Network configuration distributed production scheduling problem: A constraint programming approach,” Comput. Indus. Eng., vol. 188, no. 10, 2024, Art. no. 109916. doi: 10.1016/j.cie.2024.109916.
Crossref Google Scholar
[14]

B. Khurshid and S. Maqsood, “A hybrid evolution strategies-simulated annealing algorithm for job shop scheduling problems,” Eng. Appl. Artif. Intell., vol. 133, 2024, Art. no. 108016. doi: 10.1016/j.engappai.2024.108016.
Crossref Google Scholar
[15]

J. Wang, H. Tang, and D. Lei, “A feedback-based artificial bee colony algorithm for energy-efficient flexible flow shop scheduling problem with batch processing machines,” Appl. Soft Comput., vol. 153, no. 1, 2024, Art. no. 111254. doi: 10.1016/j.asoc.2024.111254.
Crossref Google Scholar
[16]

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. Indus. Eng., vol. 147, no. 2, 2020, Art. no. 106638. doi: 10.1016/j.cie.2020.106638.
Crossref Google Scholar
[17]

Y. Li et al., “A discrete artificial bee colony algorithm for distributed hybrid flowshop scheduling problem with sequence-dependent setup times,” Int. J. Prod. Res., vol. 59, no. 13, pp. 3880–3899, 2020. doi: 10.1080/00207543.2020.1753897.
Crossref Google Scholar
[18]

X. -R. Tao, Q. -K. Pan, and L. Gao, “An efficient self-adaptive artificial bee colony algorithm for the distributed resource-constrained hybrid flowshop problem,” Comput. Indus. Eng., vol. 169, no. 18, 2022, Art. no. 108200. doi: 10.1016/j.cie.2022.108200.
Crossref Google Scholar
[19]

J. -H. Hao, J. -Q. Li, Y. Du, M. -X. Song, P. Duan and Y. -Y. Zhang, “Solving distributed hybrid flowshop scheduling problems by a hybrid brain storm optimization algorithm,” IEEE Access, vol. 7, pp. 66879–66894, 2019. doi: 10.1109/ACCESS.2019.2917273.
Crossref Google Scholar
[20]

C. Lu, J. Zhou, L. Gao, X. Li, and J. Wang, “Modeling and multi-objective optimization for energy-aware scheduling of distributed hybrid flow-shop,” Appl. Soft Comput., vol. 156, no. 1, 2024, Art. no. 111508. doi: 10.1016/j.asoc.2024.111508.
Crossref Google Scholar
[21]

X. Li, Q. Zhao, H. Tang, S. Yang, D. Lei and X. Wang, “Joint scheduling optimisation method for the machining and heat-treatment of hydraulic cylinders based on improved multi-objective migrating birds optimisation,” Manuf. Syst., vol. 73, pp. 170–191, 2024.
Crossref Google Scholar
[22]

J. Cai, D. Lei, and M. Li, “A shuffled frog-leaping algorithm with memeplex quality for bi-objective distributed scheduling in hybrid flow shop,” Int. J. Prod. Res., vol. 59, no. 18, pp. 5404–5421, 2021. doi: 10.1080/00207543.2020.1780333.
Crossref Google Scholar
[23]

M. Wu, “Application of particle swarm optimisation algorithm incorporating frog-leaping algorithm in optimal scheduling for production management in manufacturing plant,” Int. J. Interact. Des. Manuf., vol. 286, no. 1, 2024, Art. no. 32. doi: 10.1007/s12008-024-01767-5.
Crossref Google Scholar
[24]

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, Jun. 2022. doi: 10.1109/TEVC.2021.3106168.
Crossref Google Scholar
[25]

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 Evol. Comput., vol. 85, no. 1, 2024, Art. no. 101479. doi: 10.1016/j.swevo.2024.101479.
Crossref Google Scholar
[26]

H. Yu, K. Gao, N. Wu, M. Zhou, P. N. Suganthan and S. Wang, “Scheduling multiobjective dynamic surgery problems via Q-learning-based meta-heuristics,” IEEE Trans. Syst. Man, Cyber.: Syst., vol. 54, no. 6, pp. 3321–3333, Jun. 2024.
Crossref Google Scholar
[27]

F. Q. Wang, Y. P. Fu, K. Z. Gao, Y. X. Wu, and S. Gao, “A Q-learning-based hybrid meta-heuristic for integrated scheduling of disassembly and reprocessing processes considering product structures and stochasticity,” Complex Syst. Model. Simul., vol. 4, no. 4, pp. 184–209, 2024. doi: 10.23919/CSMS.2024.0007.
Crossref Google Scholar
[28]

C. Luo, W. Gong, F. Ming, and C. Lu, “A Q-learning memetic algorithm for energy-efficient heterogeneous distributed assembly permutation flowshop scheduling considering priorities,” Swarm Evol. Comput., vol. 85, 2024, Art. no. 101497. doi: 10.1016/j.swevo.2024.101497.
Crossref Google Scholar
[29]

Y. Liu, F. Zhang, Y. Sun, and M. Zhang, “Evolutionary trainer-based deep Q-network for dynamic flexible job shop scheduling,” IEEE T. Evolut. Comput., doi: 10.1109/TEVC.2024.3367181.
Crossref Google Scholar
[30]

F. Zhao, G. Zhou, T. Xu, N. Zhu, and Jonrinaldi, “A knowledge-driven cooperative scatter search algorithm with reinforcement learning for the distributed blocking flow shop scheduling problem,” Expert Syst. App., vol. 230, 2023, Art. no. 120571. doi: 10.1016/j.eswa.2023.120571.
Crossref Google Scholar
[31]

Q. -K. Pan, L. Gao, X. -Y. Li, and K. -Z. Gao, “Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times,” Appl. Math. Comput., vol. 303, pp. 89–112, 2017. doi: 10.1016/j.amc.2017.01.004.
Crossref Google Scholar
[32]

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. 2, pp. 132–141, 2018. doi: 10.1016/j.eswa.2017.09.032.
Crossref Google Scholar
[33]

C. Lu, J. Zheng, L. Yin, and R. Wang, “An improved iterated greedy algorithm for the distributed hybrid flowshop scheduling problem,” Eng. Optim., vol. 56, no. 5, pp. 792–810, 2023. doi: 10.1080/0305215X.2023.2198768.
Crossref Google Scholar
[34]

B. Naderi and R. Ruiz, “The distributed permutation flowshop scheduling problem,” Comput. Oper. Res., vol. 37, pp. 754–768, 2010. doi: 10.1016/j.cor.2009.06.019.
Crossref Google Scholar
[35]

H. Oztop, M. F. Tasgetiren, D. T. Eliiyi, and Q. K. Pan, “Metaheuristic algorithms for the hybrid flowshop scheduling problem,” Comput. Oper. Res., vol. 111, no. 1, pp. 177–196, 2019. doi: 10.1016/j.cor.2019.06.009.
Crossref Google Scholar
[36]

W. S. Shao, D. C. Pi, and Z. S. Shao, “Local search methods for a distributed assembly no-idle flow shop scheduling problem,” IEEE Syst. J., vol. 13, no. 2, pp. 1945–1956, 2019. doi: 10.1109/JSYST.2018.2825337.
Crossref Google Scholar
Computers, Materials & Continua
Volume 80 Issue 3,
September 2024
Pages 3573-3589
DOI: 10.32604/cmc.2024.055244
Cite this article:
Zhu Q, Gao K, Huang W, et al. Q-Learning-Assisted Meta-Heuristics for Scheduling Distributed Hybrid Flow Shop Problems. Computers, Materials & Continua, 2024, 80(3): 3573-3589. https://doi.org/10.32604/cmc.2024.055244

81

Views

3

Downloads

0

Crossref

0

Web of Science

0

Scopus

Altmetrics
Received: 21 June 2024
Accepted: 13 August 2024
Published: 12 September 2024
© The Author 2024.

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Return