穩健最佳化於彈性製造系統之車數問題

Robust Optimization Model to Determine Number of Vehicles in FMS

詹碧文(Bih-Wen Chan)

指導教授 ： 林則孟

國立清華大學/工學院/工業工程與工程管理學系/碩士(2018年)

摘要

本研究提出穩健最佳化模型，在彈性生產系統(Flexible Manufacturing System, FMS)生產需求量具有隨機性下，找出適當的自動搬運車(Automated Guided Vehicle, AGV)車數。當車數較少時，所需之設置成本較少，但會造成未來無法搬運完成的工件數較多，即風險較大；然而，採用較多之車數時，需付出較大之設置成本，但未來無法搬運完成的數量較少，即風險較小，故此模型目標定為同時最小化平均成本與風險。
首先，本研究建立混合整數規劃模型，在給定生產需求量下，找出自動搬運車車數，以作為穩健最佳化模型之基礎。此模型以最小化成本為目標，其成本結構由設置成本、搬運成本及未搬運完成之懲罰成本三者組成。模型主要考量點有二，一為替代途程—在彈性生產系統中，加工工件有數種途程可選擇，途程決定工件運送到各個加工中心的順序，又因各加工中心彼此的距離不同，故替代途程的選擇會影響到所需的總搬運時間，進而影響所需的車數；二為限制取/放料點前之壅塞狀況—當同時有許多車輛須至同一站進行取料或放料，在前往此站之路上便會有許多等候的車輛，然而等候的空間有限，故在模型內限制單位時間內平均等候車數不能超過預設之上限。
本研究提出以時間序列模型及預測誤差之情境樹(scenario tree)，建立生產需求量情境，以投入穩健最佳化模型進行求解。然而，當使用之情境數量越多時，決策變數與限制式的數量隨之增多，求解時間呈指數型增加，故本研究使用Benders Decomposition Algorithm進行求解。最後，以隨機抽樣產生情景，評估使用穩健最佳化模型所得之車數，所產生不足或是剩餘的情況。透過此實驗，證實穩健最佳化模型所求得之最佳解，產生之不足及剩餘的總和最小，可有效掌控生產需求具有不確定性之情況。

關鍵字

彈性生產系統 ； 自動搬運車 ； 穩健最佳化模型

並列摘要

In this paper, a robust optimization (RO) model to determine number of automated guided vehicle (AGV) in flexible manufacturing system (FMS) environment is proposed. Since the amount of production demand is dynamic, less number of vehicles cost lower but with higher risk of large penalty cost for incomplete transportation in the future; more number of vehicles cost higher but with lower risk. Hence, the goal of RO model is to minimize the cost and the risk simultaneously.
Initially, we present a mixed integer programming (MIP) model to obtain the number of vehicles under given production demand. In consideration of the alternative routes and space limitations, the objective of MIP model is to minimize the cost comprising set-up cost of vehicles, weighted sum of transporting cost, and weighted sum of penalty cost for incomplete transportation demand.
Based on the MIP model, the RO model is formed as two-stage stochastic programming model. The fist-stage is to decide a feasible number of vehicles, and the second-stage is to allocate the capacity of the vehicles to the delivery demand in each scenario. The solve time for directly solving a large deterministic equivalent problem will increase exponentially when number of scenarios increases. Thus, the proposed RO model will be decomposed along by the scenarios and solved by using the Benders decomposition algorithm.
At last, we measure the probable cost for surplus and deficiency with the obtained number of vehicles through random sampling of the scenarios. The result shows that the solution obtained from the RO model truly has less sensitive to the uncertainties of production demand.

並列關鍵字

Flexible Manufacturing System ； Automated Guided Vehicle ； Robust Optimization

參考文獻

Amini, M. H., Kargarian, A., & Karabasoglu, O. (2016). ARIMA-based decoupled time series forecasting of electric vehicle charging demand for stochastic power system operation. Electric Power Systems Research, 140, 378-390.

Barnhart, C., & Schneur, R. R. (1996). Air network design for express shipment service. Operations Research, 44(6), 852-863.

Beamon, B. M., & Deshpande, A. N. (1998a). A mathematical programming approach to simultaneous unit-load and fleet-size optimisation in material handling systems design. The international journal of advanced manufacturing technology, 14(11), 858-863.

Beamon, B. M., & Deshpande, A. N. (1998b). Performance-based unit-load optimization in material handling systems design. Production Planning & Control, 9(7), 634-639.

Beisteiner, F., & Moldaschi, J. (1983). Strategies for the employment of vehicles in an automated guided transportation system. In Proceedings of the 2nd International Conference on Automated Guided Vehicle Systems, Stuttgart, W. Germany, North Holland: IFS.