請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8362
標題: | 以限制規劃求解彈性零工生產與搬運排程問題 Constraint Programming Models For Flexible Job And Material Delivery Scheduling Problem |
作者: | Yun-Yuan Liu 劉昀沅 |
指導教授: | 楊烽正(Feng-Cheng Yang) |
關鍵字: | 彈性零工生產與搬運排程問題,彈性製造系統,限制規劃,IBM ILOG CPLEX CP Optimizer,無人搬運車, Flexible Job and Material Delivery Scheduling Problem,Flexible Manufacturing System,Constraint Programming,IBM ILOG CPLEX CP Optimizer,AGV, |
出版年 : | 2020 |
學位: | 碩士 |
摘要: | 彈性零工生產與搬運排程問題源於使用無人搬運車(以下簡稱AGV)搬運工件的彈性製造系統。此類型問題複雜度高,難以建立數學規劃求解模型,以往大多使用啟發式演算法求解。本研究針對此問題研擬限制規劃求解模型,期能求得問題的最佳解。已知各產品的加工作業順序已、加工作業的候選機台和對應的加工時間、各設施間的取貨點和卸貨點之間的距離、以及AGV運行的速度。求解目標是排定產品加工作業執行的順序,選定加工機台並派遣AGV搬運工件,排出能使產品完工時間最小的排程。本研究除了限制規劃求解模型的研擬外,也使用IBM ILOG CPLEX的CP Optimizer建構模型。為了驗證本模型的求解效能,以(李佳陽, 2019)文獻中使用的中小型Y群標竿和大型L群標竿問題為測試範例。求解結果與GA+啟發式演算法比較。測試結果顯示本求解模型能求得比GA+法更佳的解,降低產品完工時間並提升機台和AGV的稼動率。此外,因實務上產品訂單可能來自多個客戶,本研究另研擬目標函式為最小化產品總完工時間的求解模型,測試不同情境下兩種模型的求解結果分析,供使用者根據排程目標選用。 The Flexible Job and Material Delivery Scheduling Problem is derived from the flexible manufacturing system that transports the parts of products with Automated guided vehicle (hereinafter referred to as AGV). This type of problem is highly complicated, hence it’s difficult to establish the mathematical programming model. In the past, heuristic algorithms were mostly used to solve this problem. However, a constraint programming model developed in this paper in order to find the best solution of this problem. The processed sequence of each operation from each product, the candidate machines for each operation and the corresponding processing time, the distance between the pickup port and the delivery port of each facility, and the moving speed of AGVs are known. The goal is to schedule the processing order of each operation, select a candidate machine and dispatch an AGV to deliver the part that can minimize the largest completion time of the products. Aside from constructing the constraint programming model, our research also implemented the model with CP Optimizer of IBM ILOG CPLEX. With an aim to verify the effectiveness of the model, the small and medium scale Y group problems and the large-scale L group problems used in the academic literature (李佳陽, 2019) are tested as benchmarks. The solution is compared with the GA+ heuristic algorithm, and the result shows that this model can obtain a greater solution that reduces the largest completion time and improves the utilization rate of machines and AGVs. Since the production order may come from multiple customers in practice, this paper also developed another constraint programming model using the objective function of minimizing the total completion time of the products. Our research analyses the result of two models in different scenarios for users to choose according to their scheduling target. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8362 |
DOI: | 10.6342/NTU202002054 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 工業工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-2907202018485400.pdf | 2.05 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。