以限制規劃求解彈性零工生產與搬運排程問題

彈性零工生產與搬運排程問題源於使用無人搬運車(以下簡稱AGV)搬運工件的彈性製造系統。此類型問題複雜度高，難以建立數學規劃求解模型，以往大多使用啟發式演算法求解。本研究針對此問題研擬限制規劃求解模型，期能求得問題的最佳解。已知各產品的加工作業順序已、加工作業的候選機台和對應的加工時間、各設施間的取貨點和卸貨點之間的距離、以及AGV運行的速度。求解目標是排定產品加工作業執行的順序，選定加工機台並派遣AGV搬運工件，排出能使產品完工時間最小的排程。本研究除了限制規劃求解模型的研擬外，也使用IBM ILOG CPLEX的CP Optimizer建構模型。為了驗證本模型的求解效能，以(李佳陽, 2019)文獻中使用的中小型Y群標竿和大型L群標竿問題為測試範例。求解結果與GA+啟發式演算法比較。測試結果顯示本求解模型能求得比GA+法更佳的解，降低產品完工時間並提升機台和AGV的稼動率。此外，因實務上產品訂單可能來自多個客戶，本研究另研擬目標函式為最小化產品總完工時間的求解模型，測試不同情境下兩種模型的求解結果分析，供使用者根據排程目標選用。

關鍵字

彈性零工生產與搬運排程問題；彈性製造系統；限制規劃； IBM ILOG CPLEX CP Optimizer ；無人搬運車

並列摘要

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.

並列關鍵字

Flexible Job and Material Delivery Scheduling Problem ； Flexible Manufacturing System ； Constraint Programming ； IBM ILOG CPLEX CP Optimizer ； AGV

參考文獻

Bilge, Ü., Ulusoy, G. (1995). A time window approach to simultaneous scheduling of machines and material handling system in an FMS. Operations Research, 43(6), 1058-1070. doi:10.1287/opre.43.6.1058

Google Scholar

Brailsford, S. C., Potts, C. N., Smith, B. M. (1999). Constraint satisfaction problems: Algorithms and applications. European Journal of Operational Research, 119(3), 557-581. doi:Doi 10.1016/S0377-2217(98)00364-6

Google Scholar

Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations research, 41(3), 157-183.

Google Scholar

Demir, Y., Kürşat İşleyen, S. (2013). Evaluation of mathematical models for flexible job-shop scheduling problems. Applied Mathematical Modelling, 37(3), 977-988. doi:https://doi.org/10.1016/j.apm.2012.03.020

Google Scholar

Dincbas, M., Hentenryck, P. V., Simonis, H., Aggoun, A., Graf, T., Berthier, F. (1988). The Constraint Logic Programming Language CHIP.

Google Scholar

主題瀏覽