零工式排程之深度強化學習的建構與優化

Construction and Optimization of Deep Reinforcement Learning for Job-shop Scheduling

陳冠蓁(KUAN-CHEN CHEN)

指導教授 ： 鍾文仁

中原大學/工學院/機械工程學系/碩士(2022年)

https://doi.org/10.6840/cycu202201400

摘要

為因應快速變動的製造需求與環境，工廠開始進入智慧製造的時代，模具業也在其中，尤其精密模具是由複雜零件所組成，且零件的種類繁多，製程的順序及工時也隨著零件的不同有所差異，對於加工排程目前多以人力和經驗進行初步規劃，再利用電腦的運算能力加入製程限制條件，達到有效的靜態全域排程，過去的研究成果已經能夠使用靜態排程方法如 FIFO(First In , First Out)、 EDD(Earliest Due Date)產生合理之排程結果，再利用 ACO(Ant Colony Optimization)、GA(Genetic Algorithm) 進行總工時優化，但靜態排程優化運算相當耗時，難以應用於加工的即時動態環境中。
因此，本研究試著以深度強化學習取代靜態演算法，來快速進行工單排程決策，本研究先以EDD結合GA與ACO取得工單排程優化結果，並透過此排程結果找出對排程決策較有影響力之6種參數作為狀態參數的輸入以及6種派工法則為決策標籤輸出，以此進行深度強化學習模型之訓練，本研究利用 Microsoft SQL Server Express資料庫做為數據儲存工具，搭配 Python 語法進行開發，經由強化學習來重複學習靜態排程的優化結果，藉此產生排程即時決策，有效優化靜態排程結果，隨然目前強化學習排程沒有達到GA演算法的最佳解，但是依然可對EDD結果再做3%的工時優化，且運算時間比GA演算法快約73%，有效縮短模具製造時間優化效率，以符合未來智慧工廠的排程需求。

關鍵字

零工式排程 ； 深度強化學習

並列摘要

In response to the rapidly changing manufacturing needs and environment, companies have begun to enter the era of smart manufacturing. In mold industry a precision molds are composed of complex parts and the sequence and working hours of the manufacturing process also vary with the parts. There are many differences in the process scheduling. At present, personnel and experience are used for preliminary planning for processing scheduling, and then the process constraints are added to achieve effective static global scheduling with computing. The researches before have been able to use static scheduling methods, for example, First In First Out(FIFO) and Earliest Due Date(EDD) are used to produce reasonable scheduling results. Also, the Ant Colony Optimization(ACO) and Genetic Algorithm(GA) can optimize the total man-hours. However, static scheduling optimization operations are equivalent time-consuming and difficult to apply to the immediate dynamic processing.
Therefore, this study tries to replace the static algorithm with deep reinforcement learning to quickly make the decisions of processing order. This study combines the EDD rules with ACO and GA to get the optimization result of scheduling and uses the result to find 6 most influential parameters in scheduling decisions as the input of state parameters and the 6 dispatching rules are used as the output of decision labels. And that is the Deep Reinforcement Learning model in this study. This study uses Microsoft SQL Server Express database as data storage tool, developed with Python to obtain the optimization results of static scheduling through Deep Reinforcement Learning, thereby generating real-time scheduling decisions, Although the current reinforcement learning scheduling has not reached the optimal solution of the GA algorithm, it is still possible to optimize the EDD results by 3% of the man-hour, and the operation time is about 73% faster than the GA algorithm, effectively optimizing static scheduling results to meet the scheduling requirements of smart factories and shorten the time of mold manufacturing.
Keywords: Job-shop Scheduling, Deep Reinforcement Learning, First-in-first-out Rule, Earliest Delivery Rule, Ant Colony Optimization

參考文獻

[1] Yan, B., Bragin, M. A., and Luh, P. B., 2018, "Novel Formulation and Resolution of Job-Shop Scheduling Problems", IEEE Robotics and Automation Letters, 3(4), pp. 3387-3393.

[2] Samarghandi, H., 2019, "Solving The No-Wait Job Shop Scheduling Problem with Due Date Constraints: A Problem Transformation Approach", Computers & Industrial Engineering, 136, pp. 635-662.

[3] Shen, L., Dauzère-Pérès, S., and Neufeld, J.S., 2018, "Solving the Flexible Job Shop Scheduling Problem with Sequence-Dependent Setup Times", European Journal of Operational Research, 265(2), pp. 503-516.

[4] Jensen, T. M., 2003, "Generating Robust and Flexible Job Shop Schedules Using Genetic Algorithms", IEEE Transactions on Evolutionary Computation, 7(3), pp. 257-288.

[5] Qing-Dao-Er-Ji, R., and Wang, Y., 2012, "A New Hybrid Genetic Algorithm for Job Shop Scheduling Problem", European Journal of Operational Research, 39(10), pp. 2291-2299.