應用數學規劃求解案例彈性零工型工廠排程問題

Applying mathematical programming to solve a flexible job shop scheduling problem: A case study

吳嘉祐(CHIA-YU WU)

指導教授 ： 陳平舜

中原大學/電機資訊學院/工業與系統工程學系/碩士(2022年)

https://doi.org/10.6840/cycu202201619

摘要

本研究針對彈性零工型工廠排程問題進行探討，根據目前工廠排程方式多由產線上生管人員進行人工排程，考慮到彈性零工型工廠的問題特徵和目標也不盡相同。因此，本研究動機在多訂單、多機台和多種產品，加工具無搶占、各階段為平行機和無訂單優先的特性下，目標求解最小總完工時間，使所有訂單在最短時間內出貨。改善排程人員因訂單不確定性和生產排程狀況多，導致排程耗時且結果未必為最佳解，為彈性零工型工廠排程問題建構數學模型取得最佳績效。本研究研究方法利用結構化將工廠的資料分類，建構一個包含不同類別表格的公司資料庫，從中萃取出排程時所需要的資料。本研究考慮工廠加工工件時的特性及工件與機台之間的關係，再利用數學規劃法撰寫限制式，建立一整數彈性零工型工廠排程數學模型。本研究採用IBM ILOG CPLEX 軟體進行求解，以驗證其排程結果的可行性。再者，本研究以個案公司生產排程為案例，根據實務資料做分析及討論，並分別測試改變訂單數量多寡和比較不同加工時間大小下，驗證本研究數學模型之可行性及有限求解時間(10,800秒)下，皆能求得最佳解或近似最佳解。最後，本研究歸納其實務管理意涵，以供其它公司作彈性零工型工廠排程之參考。

關鍵字

彈性零工型工廠排程 ； 零工型工廠排程 ； 數學規劃 ； 混合整數規劃 ； 案例研究

並列摘要

This research studied a flexible job shop scheduling problem, according to the current factory scheduling method, the production management personnel on the production line perform manual scheduling, considering that the problem characteristics and goals of flexible job shop factories are also different. Therefore, the motivation of this study is to solve the minimum total completion time under the characteristics of multiple orders, multiple machines and multiple products, no preemption of processing, parallel machines in each stage, and no order priority, so that all orders can be shipped in the shortest time. Improving the due to the uncertainty of orders and many production conditions, the production manager are time-consuming and the results of scheduling may not be the best solution, this study constructed mathematical model for the flexible job shop scheduling problem to achieve the best performance. The research method of this study use structuring to categorize factory data, build a company database with different types of tables, extracts the data needed for scheduling from it. This study considered the characteristics of processing the job in factory and relationship between job and machine, then use mathematical programming method to write constraints, establishing a mathematical model of integer flexible job shop factory scheduling. This study uses IBM ILOG CPLEX software to solve the problem, for verify the feasibility of scheduling results. Furthermore, this study takes the production scheduling of a case company as an example, analyze and discuss based on practical data and test the change of the number of orders and the comparison of processing time, respectively. To verify the feasibility of the mathematical model in this study and the limited solution time (10,800 seconds), the optimal solution or approximate optimal solution can be obtained. Finally, this study summarizes its practical management implications, which can be used as a reference for other company to schedule a flexible job shop factory problem.

並列關鍵字

flexible job shop scheduling ； job shop scheduling ； mathematical programming ； mixed integer programming ； case study

參考文獻

Beasley, J. E. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1069-1072.

Cheng, T. C. E., Kravchenko, S. A., & Lin, B. M. T. (2017). Preemptive parallel-machine scheduling with a common server to minimize makespan. Naval Research Logistics, 64(5), 388-398.

Drobouchevitch, I. G., & Strusevich, V. A. (2000). Heuristics for the two-stage job shop scheduling problem with a bottleneck machine. European Journal of Operational Research, 123(2), 229-240.

Feng, Y. L., Li, G., & Sethi, S. P. (2018). A three-layer chromosome genetic algorithm for multi-cell scheduling with flexible routes and machine sharing. International Journal of Production Economics, 196, 269-283.

Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237-267.