跳到主要內容

臺灣博碩士論文加值系統

(44.200.101.84) 您好!臺灣時間:2023/10/05 10:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳凱君
研究生(外文):Chen, Kai-Chun
論文名稱:深度強化學習於基於邊緣運算之智慧工廠中有新插單之動態彈性零工生產排程研究
論文名稱(外文):Deep Reinforcement Learning for Dynamic Flexible Job Shop Scheduling with New Job Insertions in Edge Computing Based Factories
指導教授:林春成林春成引用關係
指導教授(外文):Lin, Chun-Cheng
口試委員:陳建良康家榮
口試委員(外文):Chen, Chien-LiangKang, Jia-Rong
口試日期:2022-07-21
學位類別:碩士
校院名稱:國立陽明交通大學
系所名稱:工業工程與管理系所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2022
畢業學年度:110
語文別:中文
論文頁數:52
中文關鍵詞:智慧工廠邊緣運算彈性零工式生產排程新工單插入Deep Q Network
外文關鍵詞:smart factoryedge computingflexible job shop schedulingnew job insertionsDeep Q Network
相關次數:
  • 被引用被引用:0
  • 點閱點閱:97
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著生產過程中產品複雜性和突發事件的急遽增加,能夠快速應對事件發生並且找出最適當生產排程的動態彈性零工式生產排程問題(Dynamic Flexible Job Shop Scheduling Problem, DFJSP)也變得更加重要。在如今的智能工廠中,運算資源的需求暴增,集中式的雲端運算已無法單獨應付,而邊緣運算能以分散式方式來處理生產邊緣的數據,減少決策上的反應和延遲時間。然而在過去的DFJSP中並未考量邊緣運算來解決這類的排程問題。因此,本文提出一個基於結合雲端運算與邊緣運算架構下之智慧工廠,同時考量新工單插入的動態彈性零工式生產排程研究。DFJSP在許多文獻中已經被證明是NP-hard的問題。在近期的發展中,基於Deep Q Network(DQN)方法下AlphaGo的大成功,深度強化學習(Deep Reinforcement Learning)中的DQN成為了現階段解決問題的主流方法。加上DQN同時具備高學習力及高精確度之優點,能夠有效地針對動態事件做出反應。因此,本研究將採用DQN進行排程求解。本模型在神經網路中會將客戶的訂單資訊和新工單資訊當作輸入層的資訊,進行前向傳遞的運算,接著神經網路的輸出層會分別選出一個機台指派法則和機台派工法則,雲端中心會依據所選出的機台指派法則分配工單工序給機台並將機台派工法則傳送至邊緣裝置執行排程,最終,邊緣裝置會將排程結果回傳送至雲端中心,並不斷更新神經網路直到排程結束,而本研究之目標為最小化總延遲時間。根據實驗結果得知,在考慮新工單插入之動態彈性零工式生產排程問題下,本研究的DQN相比於僅用單一派工法則,在最小化總延遲時間的目標下有更好的解。
With the rapid increase of product complexity and unexpected events in the production process. The Dynamic Flexible Job Shop Scheduling Problem (DFJSP), which can quickly respond to events and find the most appropriate production schedule, has also become more important. The demand for computing resources in today's smart factories has skyrocketed, and centralized cloud computing cannot handle it alone. Edge computing can process data at the edge of production in a decentralized manner, reducing response and latency in decision-making. However, in the past DFJSP, edge computing were not considered to solve such scheduling problems. Therefore, this paper proposes a dynamic flexible job shop scheduling study based on a smart factory that combines cloud computing and edge computing architecture while considering the new job insertions. DFJSP has been shown to be NP-hard in many literatures. In recent developments, AlphaGo based on the Deep Q Network (DQN) method has been successful. DQN in Deep Reinforcement Learning (Deep Reinforcement Learning) has become the mainstream method to solve problems at this stage. In addition, DQN has the advantages of high learning ability and high accuracy at the same time, which can effectively respond to dynamic events. Therefore, this study will use DQN for scheduling solution. In this model, the customer's order information and new job information will be used as the information of the input layer in the neural network for forward transfer operations. Then the output layer of the neural network will select a machine assignment rule and a machine dispatching rule respectively. The cloud center will assign operations to the machines according to the selected machine assignment rule and transmit the machine dispatching rule to the edge device for scheduling. Finally, the edge device will send the scheduling result back to the cloud center and continuously update the neural network until the scheduling is over. The goal of this study is to minimize the total tardiness. According to the experimental results, considering the dynamic flexible job shop scheduling problem of new job insertions. Compared with the single dispatch rule, the DQN in this study has a better solution under the goal of minimizing the total tardiness.
摘 要 i
ABSTRACT ii
圖目錄 v
表目錄 vi
第一章 緒論 1
第二章 文獻回顧 5
2.1. 邊緣運算對於智慧工廠的重要性 5
2.2. 考量新工單插入之彈性零工式生產排程問題 6
2.3. 深度強化學習之背景及相關應用 8
第三章 系統架構 10
第四章 研究方法 14
4.1. 深度強化學習(Deep Reinforcement Learning) 14
4.2. 結合雲端中心與邊緣裝置的排程模型設計 18
4.3. 深度Q網路(DQN) 25
第五章 實驗與結果 37
5.1 實驗初始環境 37
5.2 系統特徵資訊間的相關性分析 38
5.3 實驗參數設定 38
5.3.1 超參數調整 39
5.3.2 控制超參數 的敏感度分析 41
5.3.3 softmax跟ε-greedy的比較 41
5.4 實驗結果 42
5.4.1 實驗結果之甘特圖呈現 42
5.4.2 工單總延遲時間的收斂分析 44
5.4.3 DQN與單一派工法則之比較 45
第六章 結論與未來展望 47
參考文獻 48
[1] N. Zribi, I. Kacem, A. El Kamel, and P. Borne, "Assignment and scheduling in flexible job-shops by hierarchical optimization," IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 37, no. 4, pp. 652-661, 2007.
[2] W. Cuiyu, L. Yang, and L. Xinyu, "Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm," Journal of Systems Engineering and Electronics, vol. 32, no. 2, pp. 261-271, 2021.
[3] D. Lei, M. Li, and L. Wang, "A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold," IEEE Transactions on Cybernetics, vol. 49, no. 3, pp. 1097-1109, 2019.
[4] S. Luo, "Dynamic scheduling for flexible job shop with new job insertions by deep reinforcement learning," Applied Soft Computing, vol. 91, 2020.
[5] A. Baykasoğlu, F. S. Madenoğlu, and A. Hamzadayı, "Greedy randomized adaptive search for dynamic flexible job-shop scheduling," Journal of Manufacturing Systems, vol. 56, pp. 425-451, 2020.
[6] J. Q. Li, Z. M. Liu, C. Li, and Z. X. Zheng, "Improved artificial immune system algorithm for type-2 fuzzy flexible job shop scheduling problem," IEEE Transactions on Fuzzy Systems, vol. 29, no. 11, pp. 3234-3248, 2020.
[7] W. Xu, Y. Hu, W. Luo, L. Wang, and R. Wu, "A multi-objective scheduling method for distributed and flexible job shop based on hybrid genetic algorithm and tabu search considering operation outsourcing and carbon emission," Computers & Industrial Engineering, vol. 157, 2021.
[8] F. M. Defersha and D. Rooyani, "An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup, machine release date and lag-time," Computers & Industrial Engineering, vol. 147, 2020.
[9] H. Ding and X. Gu, "Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem," Computers & Operations Research, vol. 121, 2020.
[10] F. Zhang, Y. Mei, S. Nguyen, and M. Zhang, "Evolving scheduling heuristics via genetic programming with feature selection in dynamic flexible job-shop scheduling," IEEE Transactions on Cybernetics, vol. 51, no. 4, pp. 1797-1811, 2020.
[11] F. Zhang, Y. Mei, and M. Zhang, "Evolving dispatching rules for multi-objective dynamic flexible job shop scheduling via genetic programming hyper-heuristics," in Proc.of 2019 IEEE Congress on Evolutionary Computation (CEC), 2019, pp. 1366-1373.
[12] W. Bouazza, Y. Sallez, and B. Beldjilali, "A distributed approach solving partially flexible job-shop scheduling problem with a Q-learning effect," IFAC-PapersOnLine, vol. 50, no. 1, pp. 15890-15895, 2017.
[13] M. Zhao, X. Li, L. Gao, L. Wang, and M. Xiao, "An improved Q-learning based rescheduling method for flexible job-shops with machine failures," in Proc.of 2019 IEEE 15th International Conference on Automation Science and Engineering (CASE), 2019, pp. 331-337.
[14] R. Chen, B. Yang, S. Li, and S. Wang, "A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem," Computers & Industrial Engineering, vol. 149, 2020.
[15] Y. Hao, M. Chen, H. Gharavi, Y. Zhang, and K. Hwang, "Deep reinforcement learning for edge service placement in softwarized industrial cyber-physical system," IEEE Transactions on Industrial Informatics, vol. 17, no. 8, pp. 5552-5561, 2020.
[16] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, "A survey on mobile edge computing: The communication perspective," IEEE Communications Surveys & Tutorials, vol. 19, no. 4, pp. 2322-2358, 2017.
[17] J. Wan, B. Chen, S. Wang, M. Xia, D. Li, and C. Liu, "Fog computing for energy-aware load balancing and scheduling in smart factory," IEEE Transactions on Industrial Informatics, vol. 14, no. 10, pp. 4548-4556, 2018.
[18] X. Wang, Y. Han, V. C. Leung, D. Niyato, X. Yan, and X. Chen, "Convergence of edge computing and deep learning: A comprehensive survey," IEEE Communications Surveys & Tutorials, vol. 22, no. 2, pp. 869-904, 2020.
[19] P. Hu, W. Chen, C. He, Y. Li, and H. Ning, "Software-defined edge computing (SDEC): principle, open IoT system architecture, applications, and challenges," IEEE Internet of Things Journal, vol. 7, no. 7, pp. 5934-5945, 2019.
[20] Q. Luo, S. Hu, C. Li, G. Li, and W. Shi, "Resource scheduling in edge computing: A survey," IEEE Communications Surveys & Tutorials, vol. 23, no. 4, pp. 2131-2165, 2021.
[21] F. Y. Okay and S. Ozdemir, "Routing in fog-enabled IoT platforms: A survey and an SDN-based solution," IEEE Internet of Things Journal, vol. 5, no. 6, pp. 4871-4889, 2018.
[22] J. Xuan, L. Chengyang, and X. Jiang, "Research on Multi-objective Fuzzy Flexible Job-Shop Scheduling Based on Cloud Computinger," in Proc.of 2020 IEEE 8th International Conference on Computer Science and Network Technology (ICCSNT), 2020, pp. 7-10.
[23] X. Chen et al., "A woa-based optimization approach for task scheduling in cloud computing systems," IEEE Systems Journal, vol. 14, no. 3, pp. 3117-3128, 2020.
[24] A. Marahatta, S. Pirbhulal, F. Zhang, R. M. Parizi, K.-K. R. Choo, and Z. Liu, "Classification-based and energy-efficient dynamic task scheduling scheme for virtualized cloud data center," IEEE Transactions on Cloud Computing, vol. 9, no. 4, pp. 1376-1390, 2019.
[25] X. Li, J. Wan, H.-N. Dai, M. Imran, M. Xia, and A. Celesti, "A hybrid computing solution and resource scheduling strategy for edge computing in smart manufacturing," IEEE Transactions on Industrial Informatics, vol. 15, no. 7, pp. 4225-4234, 2019.
[26] S. Deng, C. Zhang, C. Li, J. Yin, S. Dustdar, and A. Y. Zomaya, "Burst load evacuation based on dispatching and scheduling in distributed edge networks," IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 8, pp. 1918-1932, 2021.
[27] J. Moon and J. Jeong, "Smart manufacturing scheduling system: DQN based on cooperative Edge computing," in Proc.of 2021 15th International Conference on Ubiquitous Information Management and Communication (IMCOM), 2021, pp. 1-8.
[28] A. Samanta and J. Tang, "Dyme: Dynamic Microservice Scheduling in Edge Computing Enabled IoT," IEEE Internet of Things Journal, vol. 7, no. 7, pp. 6164-6174, 2020
[29] C. Yang, F. Liao, S. Lan, L. Wang, W. Shen, and G. Q. Huang, "Flexible Resource Scheduling for Software-Defined Cloud Manufacturing with Edge Computing," Engineering, 2021.
[30] S. Meng et al., "Security-aware dynamic scheduling for real-time optimization in cloud-based industrial applications," IEEE Transactions on Industrial Informatics, vol. 17, no. 6, pp. 4219-4228, 2021.
[31] K. Tamssaouet, S. Dauzère-Pérès, S. Knopp, A. Bitar, and C. Yugma, "Multiobjective optimization for complex flexible job-shop scheduling problems," European Journal of Operational Research, vol. 296, no. 1, pp. 87-100, 2022.
[32] J. Fan, C. Zhang, Q. Liu, W. Shen, and L. Gao, "An improved genetic algorithm for flexible job shop scheduling problem considering reconfigurable machine tools with limited auxiliary modules," Journal of Manufacturing Systems, vol. 62, pp. 650-667, 2022.
[33] D. D. C. Bissoli and A. R. S. Amaral, "A hybrid iterated local search metaheuristic for the flexible job shop scheduling problem," in Proc.of 2018 XLIV Latin American Computer Conference (CLEI), 2018, pp. 149-157.
[34] T. Jiang, H. Zhu, L. Liu, and Q. Gong, "Energy-conscious flexible job shop scheduling problem considering transportation time and deterioration effect simultaneously," Sustainable Computing: Informatics and Systems, 2022.
[35] X. Luo, Q. Qian, and Y. F. Fu, "Improved genetic algorithm for solving flexible job shop scheduling problem," Procedia Computer Science, vol. 166, pp. 480-485, 2020.
[36] G. Zhang, Y. Hu, J. Sun, and W. Zhang, "An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints," Swarm and Evolutionary Computation, vol. 54, 2020.
[37] H. Ding and X. Gu, "Hybrid of human learning optimization algorithm and particle swarm optimization algorithm with scheduling strategies for the flexible job-shop scheduling problem," Neurocomputing, vol. 414, pp. 313-332, 2020.
[38] B. J. Joo, Y. C. Choi, and P. Xirouchakis, "Dispatching rule-based algorithms for a dynamic flexible flow shop scheduling problem with time-dependent process defect rate and quality feedback," Procedia CIRP, vol. 7, pp. 163-168, 2013.
[39] H. Xiong, H. Fan, G. Jiang, and G. Li, "A simulation-based study of dispatching rules in a dynamic job shop scheduling problem with batch release and extended technical precedence constraints," European Journal of Operational Research, vol. 257, no. 1, pp. 13-24, 2017.
[40] S. Zhang and S. Wang, "Flexible assembly job-shop scheduling with sequence-dependent setup times and part sharing in a dynamic environment: Constraint programming model, mixed-integer programming model, and dispatching rules," IEEE Transactions on Engineering Management, vol. 65, no. 3, pp. 487-504, 2018.
[41] J. Shahrabi, M. A. Adibi, and M. Mahootchi, "A reinforcement learning approach to parameter estimation in dynamic job shop scheduling," Computers & Industrial Engineering, vol. 110, pp. 75-82, 2017.
[42] C. C. Lin, D. J. Deng, Y. L. Chih, and H. T. Chiu, "Smart manufacturing scheduling with edge computing using multiclass deep Q network," IEEE Transactions on Industrial Informatics, vol. 15, no. 7, pp. 4276-4284, 2019.
[43] S. Luo, L. Zhang, and Y. Fan, "Dynamic multi-objective scheduling for flexible job shop by deep reinforcement learning," Computers & Industrial Engineering, vol. 159, 2021.
[44] L. Hu, Z. Liu, W. Hu, Y. Wang, J. Tan, and F. Wu, "Petri-net-based dynamic scheduling of flexible manufacturing system via deep reinforcement learning with graph convolutional network," Journal of Manufacturing Systems, vol. 55, pp. 1-14, 2020.
[45] L. Wang et al., "Dynamic job-shop scheduling in smart manufacturing using deep reinforcement learning," Computer Networks, vol. 190, 2021.
[46] S. Luo, L. Zhang, and Y. Fan, "Real-Time Scheduling for Dynamic Partial-No-Wait Multiobjective Flexible Job Shop by Deep Reinforcement Learning," IEEE Transactions on Automation Science and Engineering, pp. 1-19, 2021.
[47] Y. Li, W. Gu, M. Yuan, and Y. Tang, "Real-time data-driven dynamic scheduling for flexible job shop with insufficient transportation resources using hybrid deep Q network," Robotics and Computer-Integrated Manufacturing, vol. 74, 2022.
[48] I. H. Abdulqadder, D. Zou, I. T. Aziz, B. Yuan and W. Dai, "Deployment of Robust Security Scheme in SDN Based 5G Network over NFV Enabled Cloud Environment," IEEE Transactions on Emerging Topics in Computing, vol. 9, no. 2, pp. 866-877, 2021
[49] V. Gezer, J. Um, and M. Ruskowski, "An introduction to edge computing and a real-time capable server architecture," International Journal of Intelligent Systems, vol. 11, no. 1&2, pp. 105-114, 2018.
[50] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, "Internet of Things (IoT): A vision, architectural elements, and future directions," Future Generation Computer Systems, vol. 29, no. 7, pp. 1645-1660, 2013.
[51] D. Zhao, D. Liu, F. L. Lewis, J. C. Principe, and S. Squartini, "Special issue on deep reinforcement learning and adaptive dynamic programming," IEEE Transactions on Neural Networks and Learning Systems, vol. 29, no. 6, pp. 2038-2041, 2018.
[52] S. Roy et al., "Deep learning for classification and localization of COVID-19 markers in point-of-care lung ultrasound," IEEE Transactions on Medical Imaging, vol. 39, no. 8, pp. 2676-2687, 2020.
[53] E. Chalmers, E. B. Contreras, B. Robertson, A. Luczak, and A. Gruber, "Learning to predict consequences as a method of knowledge transfer in reinforcement learning," IEEE Transactions on Neural Networks and Learning Systems, vol. 29, no. 6, pp. 2259-2270, 2017.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊