零工式排程優化的強化學習

Reinforcement Learning for Job-shop Scheduling Optimization

陳台衛(TAI-WEI CHEN)

指導教授 ： 鍾文仁

中原大學/工學院/機械工程研究所/碩士(2020年)

https://doi.org/10.6840/cycu202000732

摘要

現今為因應快速變動的需求與環境，工廠開始進入智慧製造的時代，模具業也在其中，尤其精密模具是由複雜零件所組成，且零件由不同的工序與工時所加工而成，目前多以人力和經驗進行初步排程規劃，再利用電腦的運算能力加入限制條件，達到有效率的靜態全域排程，過去的研究成果已經能夠使用靜態排程方法如FIFO(First In , First Out)、EDD(Earliest Due Date)，再利用ACO(Ant Colony Optimization)、GA(Genetic Algorithm)優化排程結果。
其中ACO演算法會因為零件以及製程數量的不同而影響收斂速度，雖然製程數量少時影響不大，但製程數量大時可能會運算至幾小時，才能夠求得優化結果，其原因在於以往的ACO演算法尋找路徑時只有一種目標，而這個目標未必適合當前的排程，導致必須不斷嘗試不同結果，以至於優化效率不足。本研究所開發的強化學習(Reinforcement Learning)與蟻群演算法(Ant Colony Optimization)之整合應用，利用Microsoft SQL Server資料庫蒐集數據，搭配Python語法進行開發，且增加了三種搜尋路徑的目標，是為了能夠因應不同工單，透過強化學習的智慧，讓螞蟻在尋找路徑時有基礎的智慧，選擇最有利的目標前進，以減少搜尋最短路徑的時間，符合未來智慧工廠的排程需求，論文最後以實際工廠內的製程案例，驗證一般的蟻群演算法與本研究開發的強化學習蟻群演算法對於排程優化的效果比較，最後驗證結果為相較於一般的蟻群演算法其收斂次數能夠減少5%，且能夠有效優化EDD排程結果，達到量化結果的效用。

關鍵字

零工式排程優化 ； 蟻群演算法 ； 強化學習 ； 非監督式學習

並列摘要

Nowadays in response to the rapidly changing needs and environment, factories have entered the era of smart manufacturing, including mold industry. Especially precision molds are composed of complex parts, and the parts are processed by different processes and working hours. Preliminary scheduling planning are made by manually with experiences, and add restrictions to achieve efficient static global scheduling. In the previous research studies, the static scheduling methods such as FIFO (First In, First Out), EDD (Earliest Due Date) has been applied, and then use ACO (Ant Colony Optimization) and GA (Genetic Algorithm) to optimize scheduling results.
The ACO algorithm will be affected with the convergence speed due to the amount of parts and processes. When the amount of processes is less, the effect is not obviously. Once the processes are many, it may take several hours to calculate the optimization results. The reason is that the ACO algorithm has only one goal when searching for a path, and this goal may not be suitable for the current schedule, resulting in the need to constantly try different results, so that the optimization efficiency is insufficient. This study integrated application of Reinforcement Learning, Ant Colony Optimization and Microsoft SQL Server database to collect data and develops it with Python syntax to adds three search paths to the target. In order to be able to respond to different work orders and strengthen the wisdom of learning, so that ants have basic wisdom when searching for paths, and choose the most advantageous goal to move forward, so as to reduce the time to search for the shortest path and meet the scheduling needs of future smart factories. Using the actual factory process case to verify the effect of the general ant colony algorithm and the reinforcement learning ant colony algorithm developed in this research on scheduling optimization. The final verification result is the convergence times compared to the general ant colony algorithm can be reduced by 5%, and can effectively optimize the EDD scheduling results to achieve quantitative results.

並列關鍵字

job-shop scheduling optimization ； ant colony algorithm ； reinforcement learning ； unsupervised learning

參考文獻

參考文獻

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

[4] Dorigo, M., Maniezzo, V., and Colorni, A., 1996, "Ant System: Optimization by a Colony of Cooperating Agents", IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 26(1), pp. 29-41.