PDF (2.1 MB)
Collect
Submit Manuscript
Open Access

Improved Dynamic Q-Learning Algorithm to Solve the Lot-Streaming Flowshop Scheduling Problem with Equal-Size Sublots

School of Computer Sciences and Mathematics, University of Camerino, Camerino 62032, Italy
School of Computer Science, Liaocheng University, Liaocheng 252000, China
Show Author Information

Abstract

The lot-streaming flowshop scheduling problem with equal-size sublots (ELFSP) is a significant extension of the classic flowshop scheduling problem, focusing on optimize makespan. In response, an improved dynamic Q-learning (IDQL) algorithm is proposed, utilizing makespan as feedback. To prevent blind search, a dynamic ε-greedy search strategy is introduced. Additionally, the Nawaz-Enscore-Ham (NEH) algorithm is employed to diversify solution sets, enhancing local optimality. Addressing the limitations of the dynamic ε-greedy strategy, the Glover operator complements local search efforts. Simulation experiments, comparing the IDQL algorithm with other intelligent algorithms, validate its effectiveness. The performance of the IDQL algorithm surpasses that of its counterparts, as evidenced by the experimental analysis. Overall, the proposed approach offers a promising solution to the complex ELFSP, showcasing its capability to efficiently minimize makespan and optimize scheduling processes in flowshop environments with equal-size sublots.

References

[1]

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.

[2]

M. Avci, M. G. Avci, and A. Hamzadayı, A branch-and-cut approach for the distributed no-wait flowshop scheduling problem, Comput. Oper. Res., vol. 148, p. 106009, 2022.

[3]

M. Rohaninejad and Z. Hanzálek, Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches, Int. J. Prod. Econ., vol. 263, p. 108958, 2023.

[4]

Y. Lu, Q. Tang, Q. Pan, L. Zhao, and Y. Zhu, A heuristic-based adaptive iterated greedy algorithm for lot-streaming hybrid flow shop scheduling problem with consistent and intermingled sub-lots, Sensors, vol. 23, no. 5, p. 2808, 2023.

[5]

Y. Pan, K. Gao, Z. Li, and N. Wu, Improved meta-heuristics for solving distributed lot-streaming permutation flow shop scheduling problems, IEEE Trans. Autom. Sci. Eng., vol. 20, no. 1, pp. 361–371, 2023.

[6]

G. Tian, W. Wang, H. Zhang, X. Zhou, C. Zhang, and Z. Li, Multi-objective optimization of energy-efficient remanufacturing system scheduling problem with lot-streaming production mode, Expert Syst. Appl., vol. 237, p. 121309, 2024.

[7]
R. Liu, C. Wang, H. Ouyang, and Z. Wu, Exact algorithm and machine learning-based heuristic for the stochastic lot streaming and scheduling problem, IISE Trans., doi: 10.1080/24725854.2023.2294816.
[8]

K. Lei, P. Guo, W. Zhao, Y. Wang, L. Qian, X. Meng, and L. Tang, A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem, Expert Syst. Appl., vol. 205, p. 117796, 2022.

[9]

C. J. C. H. Watkins and P. Dayan, Technical Note: Q-learning, Machine Learning, vol. 8, pp. 279–292, 1992.

[10]

N. J. Mukherjee, S. C. Sarin, and D. A. Neira, Lot streaming for a two-stage assembly system in the presence of handling costs, J. Sched., vol. 26, no. 4, pp. 335–351, 2023.

[11]

W. Shao, Z. Shao, and D. Pi, Modelling and optimization of distributed heterogeneous hybrid flow shop lot-streaming scheduling problem, Expert Syst. Appl., vol. 214, p. 119151, 2023.

[12]
R. Rouhbakhsh, E. Mehdizadeh, and M. A. Adibi, Presenting a model for solving lot-streaming hybrid flow shop scheduling problem by considering independent setup time and transportation time, Journal of Decisions and Operations Research, vol. 8, no. 2, pp. 307–332, 2023.
[13]

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, pp. 106–125, 2024.

[14]

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.

[15]

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.

[16]

H. Li, K. Gao, P. Y. Duan, J. Q. Li, and L. Zhang, An improved artificial bee colony algorithm with Q-learning for solving permutation flow-shop scheduling problems, IEEE Trans. Syst. Man Cybern. Syst., vol. 53, no. 5, pp. 2684–2693, 2023.

[17]

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. Inform., vol. 19, no. 7, pp. 8427–8440, 2023.

[18]

J. Zhang and J. Cai, A dual-population genetic algorithm with Q-learning for multi-objective distributed hybrid flow shop scheduling problem, Symmetry, vol. 15, no. 4, p. 836, 2023.

[19]
H. Wang, M. Emmerich, A. Plaat, Monte Carlo Q-learning for general game playing, arXiv preprint arXiv: 1802.05944, 2018.
[20]

J. Clifton and E. Laber, Q-learning: Theory and applications, Annu. Rev. Stat. Appl., vol. 7, pp. 279–301, 2020.

[21]

Z. He, K. Wang, H. Li, H. Song, Z. Lin, K. Gao, and A. Sadollah, Improved Q-learning algorithm for solving permutation flow shop scheduling problems, IET Collab. Intell. Manuf., vol. 4, no. 1, pp. 35–44, 2022.

[22]

R. Puka, I. Skalna, J. Duda, and A. Stawowy, Deterministic constructive vN-NEH + algorithm to solve permutation flow shop scheduling problem with makespan criterion, Comput. Oper. Res., vol. 162, p. 106473, 2024.

[23]

Q. Wu, Q. Gao, W. Liu, and S. Cheng, Improved NEH-based heuristic for the blocking flow-shop problem with bicriteria of the makespan and machine utilization, Eng. Optim., vol. 55, no. 3, pp. 399–415, 2023.

[24]
F. S. Madenoğlu, Solving optimization problem with particle swarm optimization: Solving hybrid flow shop scheduling problem with particle swarm optimization algorithm, in Applying Particle Swarm Optimization: New Solutions and Cases for Optimized Portfolios, B. A. Mercangöz, ed. Cham, Switzerland: Springer, 2021, pp. 263–277.
[25]

T. L. Chen, C. Y. Cheng, and Y. H. Chou, Multi-objective genetic algorithm for energy-efficient hybrid flow shop scheduling with lot streaming, Ann. Oper. Res., vol. 290, no. 1, pp. 813–836, 2020.

[26]
J. Mao, X. Hu, Q. K. Pan, Z. Miao, C. He, and M. F. Tasgetiren, An improved discrete artificial bee colony algorithm for the distributed permutation flowshop scheduling problem with preventive maintenance, in Proc. 39th Chinese Control Conf. (CCC), Shenyang, China, 2020, pp. 1679–1684.
[27]

H. Y. Sang, Q. K. Pan, J. Q. Li, P. Wang, Y. Y. Han, K. Z. Gao, and P. Duan, Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion, Swarm Evol. Comput., vol. 44, pp. 64–73, 2019.

[28]

G. Deng, M. Wei, S. Zhang, M. Xu, T. Jiang, and F. Wang, A simple migrating birds optimization algorithm with two search modes to solve the no-wait job shop problem, Expert Syst. Appl., vol. 238, p. 122112, 2024.

Complex System Modeling and Simulation
Pages 223-235
Cite this article:
Wang P, De Leone R, Sang H. Improved Dynamic Q-Learning Algorithm to Solve the Lot-Streaming Flowshop Scheduling Problem with Equal-Size Sublots. Complex System Modeling and Simulation, 2024, 4(3): 223-235. https://doi.org/10.23919/CSMS.2024.0010
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return