Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

A random flight–follow leader and reinforcement learning approach for flexible job shop scheduling problem

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

This paper proposes a hybrid search algorithm that integrates random flight, follow leader policy, and reinforcement learning, aiming to efficiently solve the flexible job shop scheduling problems. The algorithm adopts a two-stage encoding policy and a random-key-based encoding conversion mechanism, effectively establishing a mapping relationship between individual positions and the flexible job shop scheduling problem solutions. By introducing a reinforcement learning mechanism, the flexible job shop scheduling problem is transformed into a Markov decision process. Furthermore, a carefully designed system of state space, action space, and reward is utilized to achieve precise and efficient exploration of the local search space. This algorithm framework combines the extensive exploration capabilities of global search with the fine optimization capabilities of local search, significantly enhancing solution efficiency and algorithm performance. Empirical analysis demonstrates that the results on multiple authoritative benchmark datasets outperform current state-of-the-art algorithms, verifying the algorithm's outstanding performance and broad applicability in solving the flexible job shop scheduling problems.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Data availability

No datasets were generated or analysed during the current study. The data presented in this study are available upon request from the corresponding.

References

  1. Cheng Y, Cao Z, Zhang X, Cao Q, Zhang D (2024) Multi objective dynamic task scheduling optimization algorithm based on deep reinforcement learning. J Supercomput 80(5):6917–6945.https://doi.org/10.1007/s11227-023-05714-1

    Article MATH  Google Scholar 

  2. Chen R, Li W, Yang H (2022) A deep reinforcement learning framework based on an attention mechanism and disjunctive graph embedding for the job-shop scheduling problem. IEEE Trans Industr Inf 19(2):1322–1331.https://doi.org/10.1109/TII.2022.3167380

    Article MATH  Google Scholar 

  3. Lim KC, Wei L-P, Chin JF (2023) Simulated-annealing-based hyper-heuristic for flexible job-shop scheduling. Eng Optim 55(10):1635–1651.https://doi.org/10.1080/0305215X.2022.2106477

    Article MATH  Google Scholar 

  4. Kong J, Wang Z (2024) Research on flexible job shop scheduling problem with handling and setup time based on improved discrete particle swarm algorithm. Appl Sci 14(6):2586.https://doi.org/10.3390/app14062586

    Article MATH  Google Scholar 

  5. Xu Y et al (2024) Hybrid quantum particle swarm optimization and variable neighborhood search for flexible job-shop scheduling problem. J Manuf Syst 73:334–348.https://doi.org/10.1016/j.jmsy.2024.02.007

    Article MATH  Google Scholar 

  6. Han X et al (2024) A dual population collaborative genetic algorithm for solving flexible job shop scheduling problem with AGV. Swarm Evol Comput 86:101538.https://doi.org/10.1016/j.swevo.2024.101538

    Article  Google Scholar 

  7. Fan C, Wang W, Tian J (2024) Flexible job shop scheduling with stochastic machine breakdowns by an improved tuna swarm optimization algorithm. J Manuf Syst 74:180–197.https://doi.org/10.1016/j.jmsy.2024.03.002

    Article MATH  Google Scholar 

  8. Mei Z, Lu Y, Lv L (2024) Research on multi-objective low-carbon flexible job shop scheduling based on improved NSGA-II. Machines 12(9):590.https://doi.org/10.3390/machines12090590

    Article MATH  Google Scholar 

  9. Zhou K, Tan C, Zhao Y, Yu J, Zhang Z, Wu Y (2024) Research on solving flexible job shop scheduling problem based on improved GWO algorithm SS-GWO. Neural Process Lett 56(1):26.https://doi.org/10.1007/s11063-024-11488-1

    Article  Google Scholar 

  10. Ding H, Gu X (2020) Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem. Comput Oper Res 121:104951.https://doi.org/10.1016/j.cor.2020.104951

    Article MathSciNet MATH  Google Scholar 

  11. Zhang Y, Zhu H, Tang D (2020) An improved hybrid particle swarm optimization for multi-objective flexible job-shop scheduling problem. Kybernetes 49(12):2873–2892.https://doi.org/10.1108/K-06-2019-0430

    Article MATH  Google Scholar 

  12. Sriboonchandr P, Kriengkorakot N, Kriengkorakot P (2019) Improved differential evolution algorithm for flexible job shop scheduling problems. Math Comput Appl 24(3):80.https://doi.org/10.3390/mca24030080

    Article MathSciNet  Google Scholar 

  13. Martínez Y, et al (2011) A reinforcement learning approach for the flexible job shop scheduling problem. In: International Conference on Learning and Intelligent Optimization. Berlin, Heidelberg: Springer Berlin Heidelberg.https://doi.org/10.1007/978-3-642-25566-3_19

  14. Zhao L et al (2023) A drl-based reactive scheduling policy for flexible job shops with random job arrivals. IEEE Trans Autom Sci Eng.https://doi.org/10.1109/TASE.2023.3271666

    Article MATH  Google Scholar 

  15. Lei K et al (2023) Large-scale dynamic scheduling for flexible job-shop with random arrivals of new jobs by hierarchical reinforcement learning. IEEE Trans Industr Inf 20(1):1007–1018.https://doi.org/10.1109/TII.2023.3272661

    Article MATH  Google Scholar 

  16. Lei K et al (2022) A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem. Expert Syst Appl 205:117796.https://doi.org/10.1016/j.eswa.2022.117796

    Article MATH  Google Scholar 

  17. Zeng Z, Li X, Bai C (2022) A deep reinforcement learning approach to flexible job shop scheduling. In: 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC). IEEE.https://doi.org/10.1109/SMC53654.2022.9945107

  18. Jing X et al (2024) Multi-agent reinforcement learning based on graph convolutional network for flexible job shop scheduling. J Intell Manuf 35(1):75–93.https://doi.org/10.1007/s10845-022-02037-5

    Article MATH  Google Scholar 

  19. Saqlain M, Ali S, Lee JY (2023) A Monte-Carlo tree search algorithm for the flexible job-shop scheduling in manufacturing systems. Flex Serv Manuf J 35(2):548–571.https://doi.org/10.1007/s10696-021-09437-4

    Article MATH  Google Scholar 

  20. Wang R et al (2023) Flexible job shop scheduling via dual attention network-based reinforcement learning. IEEE Trans Neural Netw Learn Syst.https://doi.org/10.1109/TNNLS.2023.3306421

    Article MATH  Google Scholar 

  21. Song W et al (2022) Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Trans Industr Inf 19(2):1600–1610.https://doi.org/10.1109/TII.2022.3189725

    Article MATH  Google Scholar 

  22. Yuan M et al (2023) A multi-agent double deep-Q-network based on state machine and event stream for flexible job shop scheduling problem. Adv Eng Inform 58:102230.https://doi.org/10.1016/j.aei.2023.102230

    Article MATH  Google Scholar 

  23. Zhang W et al (2024) A novel collaborative agent reinforcement learning framework based on an attention mechanism and disjunctive graph embedding for flexible job shop scheduling problem. J Manuf Syst 74:329–345.https://doi.org/10.1016/j.jmsy.2024.03.012

    Article MATH  Google Scholar 

  24. Du Yu et al (2022) Knowledge-based reinforcement learning and estimation of distribution algorithm for flexible job shop scheduling problem. IEEE Trans Emerg Top Comput Intell 74.https://doi.org/10.1109/TETCI.2022.3145706

    Article MATH  Google Scholar 

  25. Yuan E et al (2024) Solving flexible job shop scheduling problems via deep reinforcement learning. Expert Syst Appl 245:123019.https://doi.org/10.1016/j.eswa.2023.123019

    Article MATH  Google Scholar 

  26. Wan L et al (2024) An effective deep actor-critic reinforcement learning method for solving the flexible job shop scheduling problem. Neural Comput Appl.https://doi.org/10.1007/s00521-024-09654-6

    Article MATH  Google Scholar 

  27. Wan L et al (2024) Flexible job shop scheduling via deep reinforcement learning with meta-path-based heterogeneous graph neural network. Knowl-Based Syst 296:111940.https://doi.org/10.1016/j.knosys.2024.111940

    Article MATH  Google Scholar 

  28. Liu W, Chen H, Zhang J, Wang Y (2024) A multiobjective flexible job shop scheduling method based on deep reinforcement learning. In: Ninth international symposium on sensors, mechatronics, and automation system (ISSMAS 2023) Vol. 12981, pp. 1195–1201. SPIE.https://doi.org/10.1117/12.3014960

  29. Xu S, Li Y, Li Q (2024) A deep reinforcement learning method based on a transformer model for the flexible job shop scheduling problem. Electronics 13(18):3696.https://doi.org/10.3390/electronics13183696

    Article MATH  Google Scholar 

  30. He J, Li J (2024) Deep reinforcement learning based on graph neural network for flexible job shop scheduling problem with lot streaming. In: International conference on intelligent computing (pp. 85–95). Singapore: Springer Nature Singapore.https://doi.org/10.1007/978-981-97-5675-9_8

  31. Zhuang M, Zhang W, Tang H, Li X, Wang K (2024) A multi-objective genetic algorithm based on two-stage reinforcement learning for green flexible shop scheduling problem considering machine speed. Expert Syst Appl 258:125189.https://doi.org/10.1016/j.eswa.2024.125189

    Article  Google Scholar 

  32. Li Y, Liao C, Wang L, Xiao Y, Cao Y, Guo S (2023) A reinforcement learning-artificial bee colony algorithm for flexible job-shop scheduling problem with lot streaming. Appl Soft Comput 146:110658.https://doi.org/10.1016/j.asoc.2023.110658

    Article  Google Scholar 

  33. Chen R et al (2020) A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Comput Ind Eng 149:106778.https://doi.org/10.1016/j.cie.2020.106778

    Article MATH  Google Scholar 

  34. Long X et al (2022) A self-learning artificial bee colony algorithm based on reinforcement learning for a flexible job-shop scheduling problem. Concurr Comput: Pract Exp 34(4):e6658.https://doi.org/10.1002/cpe.6658

    Article MATH  Google Scholar 

  35. Chen R, Wu B, Wang H, Tong H, Yan F (2024) A Q-Learning based NSGA-II for dynamic flexible job shop scheduling with limited transportation resources. Swarm Evol Comput 90:101658.https://doi.org/10.1016/j.swevo.2024.101658

    Article MATH  Google Scholar 

  36. Dauzère-Pérès S et al (2024) The flexible job shop scheduling problem: a review. Eur J Oper Res 314(2):409–432.https://doi.org/10.1016/j.ejor.2023.05.017

    Article MathSciNet MATH  Google Scholar 

  37. Yuan HX, Yang J (2013) A hybrid harmony search algorithm for the flexible job shop scheduling problem. Appl Soft Comput 13(7):3259–3272.https://doi.org/10.1016/j.asoc.2013.02.013

    Article MATH  Google Scholar 

  38. Wang L (2008) Particle Swarm optimization and scheduling algorithms. Tsinghua University Press, Beijing

    MATH  Google Scholar 

  39. Geist M, Scherrer B, Pietquin O (2019) A theory of regularized markov decision processes. In: International conference on machine learning (pp. 2160–2169). PMLR.https://doi.org/10.48550/arXiv.1901.11275

  40. Zhao D, et al (2016) Deep reinforcement learning with experience replay based on SARSA. In: 2016 IEEE symposium series on computational intelligence (SSCI). IEEE.https://doi.org/10.1109/SSCI.2016.7849837

  41. Moradimaryamnegari H, Frego M, Peer A (2022) Model predictive control-based reinforcement learning using expected sarsa. IEEE Access 10:81177–81191.https://doi.org/10.1109/ACCESS.2022.3195530

    Article  Google Scholar 

  42. Shahrabi J, Adibi MA, Mahootchi M (2017) A reinforcement learning approach to parameter estimation in dynamic job shop scheduling. Comput Ind Eng 110:75–82.https://doi.org/10.1016/j.cie.2017.05.026

    Article MATH  Google Scholar 

  43. Behnke D, Geiger MJ (2012) Test instances for the flexible job shop scheduling problem with work centers.https://doi.org/10.24405/436

  44. Cai X, Xiao Y, Li M, Hu H, Ishibuchi H, Li X (2020) A grid-based inverted generational distance for multi/many-objective optimization. IEEE Trans Evol Comput 25(1):21–34.https://doi.org/10.1109/TEVC.2020.2991040

    Article MATH  Google Scholar 

  45. Shang K, Ishibuchi H, He L, Pang LM (2020) A survey on the hypervolume indicator in evolutionary multiobjective optimization. IEEE Trans Evol Comput 25(1):1–20.https://doi.org/10.1109/TEVC.2020.3013290

    Article  Google Scholar 

  46. Marzouki B, Driss OB, Ghédira K (2017) Multi agent model based on chemical reaction optimization with greedy algorithm for flexible job shop scheduling problem. Procedia Computer Science 112:81–90.https://doi.org/10.1016/j.procs.2017.08.174

    Article MATH  Google Scholar 

Download references

Acknowledgements

This work is supported by the Key Project 2020 of the Ministry of Science and Technology of China-Research on Real-Time Operation Optimization Technology of Production Line Driven by Data Intelligence (No. 2020YFB1712202), supported by Basic Research Project of Science and Technology Department of Jilin Province (No. 202002044JC).

Author information

Authors and Affiliations

  1. College of Mechanical and Electrical Engineering, Changchun University of Science and Technology, Changchun, Jilin, China

    Changshun Shao, Zhenglin Yu, Hongchang Ding, Guohua Cao, Jingsong Duan & Bin Zhou

  2. Chongqing Research Institute of Changchun University of Science and Technology, Chongqing, China

    Changshun Shao, Zhenglin Yu, Hongchang Ding, Guohua Cao, Jingsong Duan & Bin Zhou

Authors
  1. Changshun Shao

    You can also search for this author inPubMed Google Scholar

  2. Zhenglin Yu

    You can also search for this author inPubMed Google Scholar

  3. Hongchang Ding

    You can also search for this author inPubMed Google Scholar

  4. Guohua Cao

    You can also search for this author inPubMed Google Scholar

  5. Jingsong Duan

    You can also search for this author inPubMed Google Scholar

  6. Bin Zhou

    You can also search for this author inPubMed Google Scholar

Contributions

All authors contributed to the study conception and design. Material preparation, data collection and analysis were performed by [Changshun Shao], [Zhenglin Yu] and [Hongchang Ding]. The first draft of the manuscript was written by [Changshun Shao], [Guohua Cao], [Jingsong Duan] and [Bin Zhou] All authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence toZhenglin Yu.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Ethical approval

No ethical approval was required for this research.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Below is the link to the electronic supplementary material.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp