為了使整個供應鏈系統中的成本降低,實務上採行了許多的方法來減少存貨或是避免延遲達交,這些方法包括了共同料、彈性工廠、替代料及替代路徑等,其中前三項方法均有大量相關的探討,唯讀替代路徑的相關研究較少,故本研究希望能對替代路徑這樣一個能大幅減少供應鏈成本的機制做一探討。 本研究主要探討在有替代路徑的情況下,整個供應鏈中多層上下游環境之生產規劃的問題。在滿足訂單為前提,且具產能及物料的限制下,本研究建構一整數線性規劃模型,目標在於使整個供應鏈系統的成本,包括生產成本、整備成本、存貨成本及延遲達交的懲罰成本總和最低。然而,當供應鏈中訂單數目增多、路徑及工廠增加、以及規劃時間拉長,會使得模式中零、壹變數的數量大幅增加,導致整數線性規劃模型的求解時間大幅度拉長,以至於不符合實用的需求。為了解決這樣的問題,本研究使用基因演算法(generic algorithm)為基礎,發展一套啟發式演算法來解決替代路徑的選擇問題,並運用拉式釋限法(Lagrangian relaxation)及前後移動法,來完成最後的生產規劃。這樣的方法,使我們能在短時間內求得近似最佳解。 為了比較本研究所提之不同方法,本研究針對了訂單數不同、或路徑情況不同共25種情境,分別對四種演算法,包括了線性規劃求解最佳解、使用ILOG之CPLEX演算法、及使用本研究所提之兩種演算法,共500個試驗結果來比較本研究所提的啟發式演算法在各種情境下的優劣,結果可以證明本研究所提之啟發式演算法確實能在大部分的情況下於短時間內得到相當好的解。此外,根據試驗過程中的發現,本研究並試着提出適用替代路徑的時機。
Due to higher variation of demand existed in supply chain, many approaches are proposed to lower the supply chain cost in a multi-echelon production environment. Among these approaches, alternative route is a popular way applied in the industry to overcome the limitation of capacity and the material supply. Unfortunately, only a few researches related to alternative route are studied. Thus, this thesis intends to look into the issues of alternative route and to develop an efficient mechanism for the industry when this approach is adapted. The production planning problem with alternative route can be formulated as an mixed integer linear programming model intending to minimize the total cost of the supply chain, including the production cost, setup cost, inventory cost and the shortage cost if the orders can’t be delivered on time. In addition to the constraints of limited capacity and supply of raw material, there are complex inter-link relationship existed between each pair of the downstream plants and the upstream plant under the multi-echelon production environment. As the number of customer orders and alternative routes increase, the integer programming model becomes intractable in terms of computation time. Therefore, a generic-algorithm based heuristic method is developed to determine the route for each order initially, followed by a Lagrangain relaxation method and a backward-forward method to obtain the near-optimal production schedules. To evaluate the performance of our heuristic algorithm, over 500 test problems under 25 scenarios are generated from field data. Also, our proposed algorithms are compared to the optimal solution and the results of ILOG CPLEX. We find that the average percentage error is only 0.013% away from the optimum and our algorithm can solve the problem in a very short period of time. Besides, our algorithm is more robust comparing with ILOG CPLEX method. Finally, some implications about when to use the alternative route are suggested.