簡易檢索 / 詳目顯示

回結果列表
研究生： 黃妍綺
Huang, Yen-Chi
論文名稱： 混合派工法則與深度強化學習演算法最佳化彈性零工式排程問題
Hybrid Dispatching Rules and Deep Reinforcement Learning Algorithms for Optimizing the Flexible Job Shop Scheduling Problem
指導教授： 楊大和
Yang, Ta-Ho
王宏鍇
Wang, Hung-Kai
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 製造資訊與系統研究所
Institute of Manufacturing Information and Systems
論文出版年： 2025
畢業學年度： 113
語文別： 英文
論文頁數： 68
中文關鍵詞： 柔性作業車間排程問題 、深度強化學 、深度 Q 網絡 、派工法則
外文關鍵詞： Flexible Job Shop Scheduling Problem (FJSP), Deep Reinforcement Learning (DRL), Deep Q Network (DQN), Dispatching Rules
相關次數： 點閱：39  下載：13 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 柔性作業車間排程問題（Flexible Job Shop Scheduling Problem, FJSP）是一種典型的複雜排程問題，廣泛應用在製造業中的資源分配與生產計劃中。然而，傳統方法在面對規模較大及動態遍化需求的情境下，往往存在效率較低與適應性不足的問題。本研究針對動態 FJSP 問題，提出了一種結合派工法則與深度強化學習（Deep Reinforcement Learning, DRL）的創新方法，通過深度 Q 網絡（Deep Q Network, DQN）算法進行建模與求解。
    本研究在模型訓練中融入基於派工法則的優先級機制，結合作業目標完成時間與機台選擇策略，為動態排程問題提供初始權重指引。派工法則不僅能有效平衡即時加工需求與全局目標，還為 DQN 模型的學習過程奠定了基礎。通過經驗回放與目標網絡同步技術，DQN 模型能穩定學習並適應多變的生產環境，實現準時達交與總延遲最小的目標。
    研究結果表明，結合派工法則的 DQN 方法在資源分配與作業順序優化上展現了卓越性能，能夠有效應對動態環境中的排程挑戰。損失函數的穩定收斂進一步證實了模型的學習穩定性與適應性。本研究驗證了深度強化學習技術在結合傳統排程法則後的應用價值，且嘗試泛化模型擴大生產規模，為製造業中的智慧化排程與資源最佳化提供了新方向。

    The Flexible Job Shop Scheduling Problem (FJSP) is a typical complex scheduling problem widely applied in resource allocation and production planning in the manufacturing industry. However, traditional methods often suffer from low efficiency and poor adaptability when dealing with large-scale and dynamically changing demands. This study proposes an innovative approach that combines dispatching rules with Deep Reinforcement Learning (DRL), using the Deep Q Network (DQN) algorithm for modeling and problem-solving in dynamic FJSP scenarios.
    This study integrates a priority mechanism based on dispatching rules into the model training process. By incorporating job completion deadlines and machine selection strategies, initial weight guidance is provided for dynamic scheduling problems. Dispatching rules effectively balance immediate processing needs and global objectives while laying the foundation for the DQN model’s learning process. With experience in the replay and target network synchronization techniques, the DQN model achieves stable learning and adapts to dynamic production environments, meeting the goals of on-time delivery and minimizing total tardiness.
    The research results demonstrate that the DQN method, combined with dispatching rules, exhibits excellent resource allocation and job sequencing optimization, effectively addressing dynamic environments' scheduling challenges. The stable convergence of the loss function further validates the model’s learning stability and adaptability. This study confirms the application value of Deep Reinforcement Learning techniques when integrated with traditional scheduling rules and explores the model's generalization to larger production scales. It provides new directions for intelligent scheduling and resource optimization in the manufacturing industry.

    Table of Contents III List of Tables V List of Figures VI Chapter 1. Introduction 1 1.1 Background and Motivation 1 1.2 Research Purpose 3 1.3 Research Overview 4 Chapter 2. Literature Review 5 2.1 Flexible Job-Shop Scheduling Problem 5 2.2 Dispatching Rules 6 2.2.1 Earliest Due Date 6 2.2.2 Longest Processing Time Rule 7 2.3 Deep Reinforcement Learning 8 2.3.1 Deep Reinforcement Learning 8 2.3.2 Deep Q-Network 9 Chapter 3. Research Method 11 3.1 Research Framework 11 3.2 Problem Description 14 3.2.1 Characteristics of the Problem 14 3.2.2 Assumptions of the Problem 15 3.2.3 Constraints of the Problem 16 3.3 Dispatching Rules 17 3.3.1 Earliest Due Date 18 3.3.2 Longest Processing Time Rule 19 3.4 Deep Reinforcement Learning 20 3.4.1 Deep Q-Network 21 3.4.2 Initialize the Environment and Network 23 3.4.3 Input State 26 3.4.4 Select Action 28 3.4.5 Execute Action 29 3.4.6 Store Experience 30 3.4.7 Train Neural Network 31 3.4.8 Termination Condition 34 Chapter 4. Empirical Study 35 4.1 Description of System Input Data 35 4.2 Scheduling Algorithm 39 4.3 Parameter Settings and Operational Environment 41 4.3.1 Experimental Parameter Settings 41 4.3.2 Operational Environment 41 4.4 Experimental Results 42 4.4.1 Experimental Scenarios 42 4.4.2 Comparison of Experimental Results 46 Chapter 5. Conclusion and Future Research 56 5.1 Conclusion 56 5.2 Future Research 57 Reference 59

    Blackstone, J. H., Phillips, D. T., & Hogg, G. L. (1982). A STATE-OF-THE-ART SURVEY OF DISPATCHING RULES FOR MANUFACTURING JOB SHOP OPERATIONS [Article]. International Journal of Production Research, 20(1), 27–45. https://doi.org/10.1080/00207548208947745
    Brucker, P., & Schlie, R. (1990). Job-shop scheduling with multipurpose machines. Computing.
    Chang, J. R., Yu, D., Hu, Y., He, W. W., & Yu, H. Y. (2022). Deep Reinforcement Learning for Dynamic Flexible Job Shop Scheduling with Random Job Arrival [Article]. Processes, 10(4), 20, Article 760. https://doi.org/10.3390/pr10040760
    Conway, R. W., Maxwell, W. L., & Miller, L. W. (2003). Theory of Scheduling. Dover. https://books.google.com.tw/books?id=Yr5_kQDa_ssC
    Corrêa, A., Jesus, A., Silva, C., Peças, P., & Moniz, S. (2024). Rainbow Versus Deep Q-Network: A Reinforcement Learning Comparison on The Flexible Job-Shop Problem. IFAC-PapersOnLine, 58(19), 870-875.
    Dauzere-Péres, S., Ding, J. W., Shen, L. J., & Tamssaouet, K. (2024). The flexible job shop scheduling problem: A review [Review]. European Journal of Operational Research, 314(2), 409-432. https://doi.org/10.1016/j.ejor.2023.05.017
    Du, Y., Li, J. Q., Li, C. D., & Duan, P. Y. (2024). A Reinforcement Learning Approach for Flexible Job Shop Scheduling Problem With Crane Transportation and Setup Times. Ieee Transactions on Neural Networks and Learning Systems, 35(4), 5695-5709. https://doi.org/10.1109/tnnls.2022.3208942
    Fuladi, S. K., & Kim, C. S. (2024). Dynamic Events in the Flexible Job-Shop Scheduling Problem: Rescheduling with a Hybrid Metaheuristic Algorithm [Article]. Algorithms, 17(4), 20, Article 142. https://doi.org/10.3390/a17040142
    Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness. Office of Technical Services. https://books.google.com.tw/books?id=4jnPJgAACAAJ
    Karunasingha, D. S. K. (2022). Root mean square error or mean absolute error? Use their ratio as well [Article]. Information Sciences, 585, 609-629. https://doi.org/10.1016/j.ins.2021.11.036
    Kong, X. H., Yao, Y. H., Yang, W. Q., Yang, Z. L., & Su, J. Z. (2022). Solving the Flexible Job Shop Scheduling Problem Using a Discrete Improved Grey Wolf Optimization Algorithm [Article]. Machines, 10(11), 38, Article 1100. https://doi.org/10.3390/machines10111100
    Lei, K., Guo, P., Zhao, W. C., Wang, Y., Qian, L. M., Meng, X. Y., & Tang, L. S. (2022). A multi-action deep reinforcement learning framework for flexible Job-shop scheduling problem. Expert Systems with Applications, 205, Article 117796. https://doi.org/10.1016/j.eswa.2022.117796
    Leung, J. Y. T. (2004). Some basic scheduling algorithms. In Handbook of Scheduling: Algorithms, Models, and Performance Analysis (pp. 3-1). https://www.scopus.com/inward/record.uri?eid=2-s2.0-70450005139&partnerID=40&md5=661c8240c698c43b91049aca63f7bfb5
    Luo, S. (2020). Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning [Article]. Applied Soft Computing, 91, 17, Article 106208. https://doi.org/10.1016/j.asoc.2020.106208
    Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., & Riedmiller, M. A. (2013). Playing Atari with Deep Reinforcement Learning. ArXiv, abs/1312.5602.
    Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M. A., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., & Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518, 529–533.
    Pal, M., Mittal, M. L., Soni, G., Chouhan, S. S., & Kumar, M. (2023). A multi-agent system for FJSP with setup and transportation times [Article]. Expert Systems with Applications, 216, 13, Article 119474. https://doi.org/10.1016/j.eswa.2022.119474
    Serrano-Ruiz, J. C., Mula, J., & Poler, R. (2024). Job shop smart manufacturing scheduling by deep reinforcement learning. Journal of Industrial Information Integration, 38, Article 100582. https://doi.org/10.1016/j.jii.2024.100582
    Shang, X. F. (2023). A Study of Deep Learning Neural Network Algorithms and Genetic Algorithms for FJSP [Article]. Journal of Applied Mathematics, 2023, 13, Article 4573352. https://doi.org/10.1155/2023/4573352
    Shi, R. J., Leng, X. J., Wu, Y. X., Zhu, S. Y., Cai, X. C., & Lu, X. J. (2023). Machine learning regression algorithms to predict short-term efficacy after anti-VEGF treatment in diabetic macular edema based on real-world data [Article]. Scientific Reports, 13(1), 10, Article 18746. https://doi.org/10.1038/s41598-023-46021-2
    Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T. P., Hui, F., Sifre, L., Driessche, G. v. d., Graepel, T., & Hassabis, D. (2017). Mastering the game of Go without human knowledge. Nature, 550, 354-359.
    Sutton, R. S. (2018). Reinforcement learning: An introduction. A Bradford Book.
    Van Hasselt, H., Guez, A., & Silver, D. (2016). Deep reinforcement learning with double q-learning. Proceedings of the AAAI conference on artificial intelligence,

    下載圖示 校內：立即公開
    校外：立即公開
    QR CODE